n&(n-1)计算比特位1的个数的原理

时间:2022-06-03 22:36:20

n&(n-1)统计二进制比特中1的个数

unsigned int bitOneCount(unsigned int n)
{
    unsigned int count = 0;
while(0 < n) { n &= (n--); count++; }
return count; }

蓝色的是n的初始值,黑色的是当前最新的n-1,也就是上一行的值减1,红色的是n的当前最新值(n&=(n-1));最后n为0时停止计算每次循环引用计数加1

通过下面的演算,我们发现每次循环过后n最右边的比特1总是要和比它减1的数相与(例如:100b & 011b = 000b),其结果是n最后一个比特和该比特右边的都会变成0,也就是最后一个比特消失;

因为任何一个只有1个比特1的数和比它小1的数进行&结果为这几个比特全0;但是左边的则保留,因为左边的并没有发生比特变化。

01100110
01100101  循环完一次,引用计数++


01100100
01100011  循环完一次,引用计数++


01100000
01011111  循环完一次,引用计数++


01000000
00111111  循环完一次,引用计数++;


00000000  n>0不成立,不再进入循环

我们看到共有4次递增,引用计数初始为0,所以计算出比特1的个数为4,与真实结果相符。