位运算应用-统计一个数二进制表示中1的个数

给出如下PHP代码

function f($data){

    $cnt = 0;
    while($data){
        $data &= $data-1;
        $cnt++;
     }

  return $cnt;
}

原理解释：

一个等于2的n次方的数，二进制表1000......，即除了第n位（下标从0开始）为1，其余位皆为0，这个数减1后则为0111......，即除了第n位为0外，其余位皆为1，这样data &（data-1）则等于0，一次就消去了一个1。

而一般的数如6 = 0110，某位有1则为2的某次方，即a = 2的2次方 + 2的1次方。则用 data &（data-1）这个去计算，数从右至左一次消去一个1，累计可以得出1的个数。

举个例子

十进制数：11257
其二进制表示为：10101111111001
调用函数f计算1的总数目:10

参考

1、位运算--求一个 数二进制中1的个数
2、位运算--统计一个数的二进制序列中1的个数
3、剑指offer—算法之位运算（二进制中1的个数）