由于在上面看到一道题，我就想把它记录下来，以便自已以后能用到并且能记得更加清晰。 题目是判断一个32位无符号整数的二进制位为1的个数。 首先是第一种方法： int count_one_bits(unsigned int value) { int ones; for ( ones = 0; value != 0; value >>= 1) { if ( (value & 1) != 0) ones += 1; } return ones; } 这个方法相信有经验的程序员都能看出来的，是通过移位来测出为1的位数。因为题目是规定了无符号32位数，根据无符号数的 移位法则，无符号数的右移位是在最左边的位补0（有符号数的移位涉及了补位），此条语句 value >>= 1 就是用于向右移动一位。for语句中的第二条是个判断是否等于0，因为当右移了32次的时候。此时的二进制数全被补的0给占了，所以等于0跳出循环。if ( (value & 1) != 0) 判断语是 一个逻辑与判断该位是否为1，为1则ones+1。但是我个人觉得这条语句的执行效率有低它必须是把32个位全部为0的时候才算跳出循环。 以下是另外一个程序： int count_one_bits(unsigned int sum) { int cnt = 0; while (sum) { sum &= sum - 1; cnt++; } return cnt; }
这个程序就是效率就比较好，因为其的运算次数只与1的个数有关。相对来说就是sum比sum - 1 在最低位加上了一个1。
这个1就是关键性的一步，每次进行算法都会消去它，使得那一次都会获得这个正数有一个1，使cnt可以加上1。举个例子
比如7(0111) & 6(7 - 1)(0110) = 6(0110)。每次执行的时候都会消去最右边的那个1直到逻辑与操作为0。
最后还是要感谢一篇博客：http://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html
转载请注明原文地址: https://ju.6miu.com/read-670954.html
