创意十进制数位顺序表（Kernighan二进制位计数法）

如何快速计算一个二进制整数所包含1的位数，下面我们就来说一说关于创意十进制数位顺序表?我们一起去了解并探讨一下这个问题吧!

创意十进制数位顺序表

如何快速计算一个二进制整数所包含1的位数。

很多人的第一直觉就是，除2取余法，如下所示：

count := 0 for n>0 { if n%2==1 { count } n/=2 }

那么除了这种方式以外，是否还有其他的方式能够快速计数1的个数呢？

Brian Kernighan法就是这其中一种非常巧妙的算法，其原理为：

将 n 和 n-1 进行位与运算，其结果相当于把 n 的二进制表示形式当中最后一个1去除。

count := 0 for n>0 { n &= n-1 count }

这种方式相比第一种方式更加快速，其计算此处和 n 的实际包含1的位数相关。

那么 Brian Kernighan法为什么可以成立？可以这么理解：

假设有一个整数n，那么可以知道其最后一个1的位置。 根据二进制减法，将该数字减去1之后，其二进制表达式相当于n的最后一个1去除，并把之后的0全部改成1 于是得到如下两个整数，进行位与操作之后，可以计算得到其结果，实际效果相当于把n的最后一个1去除。 xxxx 1000 xxxx 0111 ----------- xxxx 0000