剑指 Offer 15 bitcount()的c++实现

剑指 Offer 15 bitcount()的c++实现

本文方法参考leetcode官方题解
  要求编写一个函数，输入是一个无符号整数n（以二进制串的形式），返回n的二进制表达式中 ‘1’ 的个数（也被称为 汉明重量).）。
例如

输入：n = 11 (控制台输入 00000000000000000000000000001011)
输出：3
解释：输入 00000000000000000000000000001011 中，共有三位为 '1'。

1.我的低效代码

从最低位开始，依次数有多少个”1“

int hammingWeight(uint32_t n) {
    int count=0;
    for(int i=0;i<32;++i){
        if(n!=n>>1<<1) ++count;
        n>>=1;
    }
    return count;
}

2.用位运算优化

只需要”1“的个数的循环次数

int hammingWeight(uint32_t n) {
    int ret = 0;
    while (n) {
        n &= n - 1;
        ret++;
    }
    return ret;
}

3.采用二路归并的思想

  为什么说是归并呢？以语句1为例，**(i >> 1) & 0x55555555)**的本质是取0 i32 0 i30 0 i28 …0 i6 0 i4 0 i2 ,然后用i减去这个数字，每两位
为一个片段来看就是，以第32、31位为例，(i32 i31） - （0 i32）得到的数字按两位为一段来看恰好是这两位的”1“的个数。如此语句1就完成了两位的归并。其他语句也是这么个意思，语句二是每4位中前两位与后两位直接相加，存储到这四位中。

int hammingWeight(uint32_t i) {
	i = i- ((i >> 1) & 0x55555555);//语句1
	i = (i & 0x33333333) + ((i >> 2) & 0x33333333);//语句2
	i = (i + (i >> 4)) & 0x0f0f0f0f;//语句3
	i = i + (i >> 8);//语句4
	i = i + (i >> 16);//语句5
	return i & 0x3f;//语句5
}

4.总结

  其实从1到3，都是更充分利用算力。碍于程序员利用算力的使用必须通过加减乘除，位运算，逻辑运算等方式，不能随心所欲地让某两位相加然后放到一个两位地寄存器中，所以算力的浪费基本不可避免。
  法1中只是简单的第i次循环里有效利用地算力仅是对第i位的计算，而且代码笨拙，浪费了大部分算力。法2中每次循环时会通过n-1的语句自动跳过32位末尾”0“的部分，直接对最后的1进行计数，算力浪费在前面未统计的”1“中，算法思想上浪费的算力较1更少；而且代码十分精简，执行上浪费的算力少。法3的思想更是重复利用算力，采用二路归并的方式，算法思想上是最好的。但是，执行上因为对数的 *** 作方式有限，不如法2简练。
  法2、法3各有优点，由此看出并非算法思想最好就一定是完美的，算法的执行实现需要考虑实际，例如具体可用的指令集等等。