今天带来根据数字二进制下 1 的数目排序，题目本身不难，主要分享一下如何统计二进制里1的个数。

我们有两种思路，一种是遍历每一位，把是1的记一下。一种是通过消除最后一个1，看消除多少次，第二种可能需要理解一下。

先带来一下第一种求1个数的代码：

int bitCount(int n) {
    int count = 0; // 计数器
    while (n > 0) {
        if((n & 1) == 1)  count++;  // 当前位是1，count++
        n >>= 1 ; // n向右移位
    }
    return count;
}

再带来第二种的完整代码:

class Solution {
public:
    static bool cmp(int a, int b) {  // 添加 static 关键字
        return count_one(a) != count_one(b) ? count_one(a) < count_one(b) : a < b;
    }
    
    static int count_one(int a) {  // count_one 也需要是静态的
        int cnt = 0;
        while (a) {
            a &= (a - 1);
            cnt++;
        }
        return cnt;
    }
    
    vector<int> sortByBits(vector<int>& arr) {
        sort(arr.begin(), arr.end(), cmp);
        return arr;
    }
};

可以看到第一种就是一位位比较。而第二种举例子会更好理解。比如我现在拿出一个数10,10的二进制为1010，10-1为9，9的二进制是1001。可以看到只有最后一个1后面的数字会变化，而相与后变成1000，为数字8，数字9就比10少一个1。每进行一次这样的操作，就统计一下，就能统计出二进制里有多少个1。这个原理也很简单，因为最后一个1，它之后要不是0，要不就没有数字，为一个1XXXX的形式，减1就会变成01111的形式，1前面的部分不会受影响，相与后这部分会变成00000。