统计一个数的二进制中 0, 1 个数

求二进制数中1的个数 - 博客园

普通法

n & 1 得到 n 的最后一个数字，然后移位判断每一位数字。

比如 n = 250，n & 1 的结果前7位都是0，所以 n & 1 = n 的最后一位数字

250   11111010
  1   00000001

// 普通法
int count1(unsigned int n) {
    int count = 0;
    while (n > 0) {
        if ((n & 1) == 1) count++; // 判断n的二进制最后一位是不是1
        n >>= 1; // 数据右移一位
    }
    return count;
}

int count0(unsigned int n) {
    int count = 0;
    while (n > 0) {
        if ((n & 1) == 0) count++; // 判断n的二进制最后一位是不是1
        n >>= 1; // 数据右移一位
    }
    return count;
}

快速法

快在不用逐个位比较，最后 count 值就是需要 while 循环的次数。原理如下：

n = n & (n - 1); // 1换0
n = n | (n + 1); // 0换1

比如 n = 7

n   7 0111
n-1 6 0110    n & (n - 1) = 0110
n+1 8 1000    n | (n + 1) = 1111

// 快速法
int count1(unsigned int n) {
    int count = 0;
    while (n > 0) { // 所有1都换成0跳出循环
        n = n & (n - 1); // 1换0
        count++;
    }
    return count;
}

int count0(unsigned int n) {
    int count = 0;
    while (n != 255) { // 所有0都换成1跳出循环
        n = n | (n + 1); // 0换1
        count++;
    }
    return count;
}

int main() {
    unsigned int a = 250;
    bitset<8> bs(a);
    cout << bs << endl; // 二进制
    cout << count1(a) << endl;
    cout << count0(a) << endl;
}

11111010
6
2