算法: 如何计算一个二进制数含1的个数

一个很简单的问题，估计很多人看到之后已经有了自己的思路。

不过这不一定是个最好的思路。

普通方法这里就不说了，说说今天看到的一个算法，觉得自己想不到，所以写在这里。

怎么解决呢？

很简单的一段程序

int num = 0;
 while(v) {
 v &= v-1
 num++;
 }

最后的num值就是个数。也就是说算法时间复杂度就是1的个数！

怎么理解呢？

如果某一位上有1，而后面的都是0，会怎么样呢。比如1010000,这个数减一之后，后面的五位都会取反，变为1001111

再与一下！变为1000000

看到了吗？直接把一个1变为0了，也就是这次操作后有一个1。

接着往下走，继续把1000000减一，再与一下，最后变为0000000

总结，1010000有两个1，经过两次操作，变成了0！

反过来，经过两次操作，变成0，那就是有两个1！

有兴趣可以实现下~
还可以用数学方法证明一下~