计算整数二进制表示中各个1位的数目

编写一个函数,确定给定整数的二进制表示中各个1位的数目。

举例:给定一个数字是7,假设是8位操作系统,二进制表示为00000111,其中有3个1,则调用函数返回3

整体思路:循环统计,检测二进制表示中的最后一位,如果最后一位是1的时候计数器加1,然后把数字右移一位,直到整个数字全部移完。

代码:

1
2
3
4
5
6
7
8
9
10
function numOnesInBinary(number) {
let numOnes = 0;
while(number != 0) { // 直到数字全部移完
if((number & 1) === 1) { // 判断最后一位是1
numOnes++; // 计数器自增
}
number = number >>> 1; // 二进制右移1位
}
return numOnes;
}

上述算法已经很不错了,不过还有可以优化的部分。

一个数的二进制跟这个数减1的二进制相比,前半部分是相同的,只是翻转了最低位的1以及之后的各个位。例如有个数的二进制位01110000(十进制112),该值减去1以后的二进制是01101111(十进制111),可以看到前三位是相同的,后面的位数是想反的。一个数的二进制跟这个数减1的二进制相与(&)会发生什么呢?实际上就是该二进制去掉最后一个1,如01110000 & 01101111 = 0110000001100000实际上就是01110000去掉最后一个1的结果。

有了上面的知识,我们可以稍微改造一下代码:

1
2
3
4
5
6
7
8
function numOnesInBinary(number) {
let numOnes = 0;
while(number != 0) { // 直到不等于0
number = number & (number - 1); // 去掉二进制最后一位1
numOnes++; // 计数器自增
}
return numOnes;
}
-------------本文结束 感谢您的阅读-------------
0%