【4.15】求二进制数中1的个数【每日一题】

本文主要是介绍【4.15】求二进制数中1的个数【每日一题】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

此题主要考查位运算，当然不会用位运算的人可能会这么写：

1.可能是最笨的方法了

int numOfOne(unsigned num) {int count = 0;while (num) {count += num % 2;num /＝ 2;}return count;
}

使用位运算的原因是位运算比乘法要快，这是与计算机的硬件实现相关的。下面是使用位运算中的一种比较弱多解法，好处是逻辑清楚，易懂。

2.用位运算来代替方法1中的除法和取模运算

int numOfOne(unsigned num) {int count = 0;while (num) {count += num & 1;num >>= 1;}return count;
}

方法2中的方法已经比方法1中的方法好很多了，但是有没有更好的方法呢？下面是编程之美中给出的方法

3.只用一次位运算

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

这个方法中，每次循环仅用了一次位运算，从这里已经比方法2省了一次位运算，另外，我们可以发现如下规律：

1. 当n不为0时，n-1总是从把n中最后一个1（二进制位）改为0（二进制位），同时将其后的所有位置0，而与此同时对于前面的所有位，n与n-1每一位均相同，因此&操作并不会改变前面所有位数的值。这样n & (n - 1)的最终效果是把n的最后一个1置0，因此我们给count加1
2. 在每次循环时，总是找到n的最后一个1去操作，因此跳过了n所有二进制位中后面的连续的多个0位，可以有效减少循环执行次数

这篇关于【4.15】求二进制数中1的个数【每日一题】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---