解法1

我们希望算法的复杂度只和二进制中1的个数有关。

如何只对二进制数中的1进行操作呢？

给定一个数: a = 0xxxxxx100000
b = a - 1 = 0xxxxxx011111
c = a & b = 0xxxxxx000000

可以看到1被消除了，因此每进行这样一次操作，消耗二进制数中的一个1，利用这种操作，当c等于0的时候，我们就可以得到二进制数中1的个数。

代码如下:

private static int numOne(int v){
        int num = 0;
        while(v!=0){
            v &= (v-1);
            num++;
        }
        return num;
    }

扩展问题1

给定两个正整数A和B，问把A变为B需要改变多少位？

问题分析

原问题等价于正整数A和B中二进制表示中有多少位是不同的。

解决方法

C = A XOR B; // C的二进制数中1表示A和B对应的二进制位是不同的。
res = numOne(C); // 统计C中1的个数