位运算的妙用之二进制1的个数

Frey December 26, 2017 [算法] #C语言

求出一个正整数转换成二进制形式中数字"1"的个数
题目:求出一个正整数转换成二进制形式中数字"1"的个数
如:
int 型数值为 80
转化成二进制形式:80 = 00000000 00000000 00000000 01010000
因此 1 的个数为 2

1.普通解法

一位一位判断

    int bitCount1(int n) {
        int count = 0;
        while (n != 0) {
            if (n & 0x01 == 1)
                count++;
            n = n >> 1;
        }
        return count;
    }

2.大神的解法

    int bitCount2(int n) {
        n = n - ((n >> 1) & 0x55555555);//n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
        n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
        n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
        n = n + (n >> 8);               //n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);
        n = n + (n >> 16);              //n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);
        return n & 0x0000003f;          //return n;
    }

参考文章

1.https://www.jianshu.com/p/25c75149e7a2