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

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

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

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

代码:

代码语言:javascript
复制
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的结果。

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

代码语言:javascript
复制
function numOnesInBinary(number) {
  let numOnes = 0;
  while(number != 0) { // 直到不等于0
    number = number & (number - 1); // 去掉二进制最后一位1
    numOnes++; // 计数器自增
  }
  return numOnes;
}

拓展

上述得出一个重要的结论number & (number - 1)的值就是number二进制去掉最后一个1的结果。利用这个结论我们还可以最很多事,比如有题目:

给你一个正整数 n,请你判断该正整数是否是 2 的幂次方。如果是,返回 true ;否则,返回 false。

比如,n=4的时候就返回ture,如果n=3的时候就返回false。

整体思路:由于一个正整数是2的幂次方,那么它的二进制一定是1后面好多0这种格式,比如4的二进制就是100,8的二进制就是1000。所以按照这个思路我们可以去掉最后一个1,如果结果是0的时候就说明这个正整数是2的幂次方。

代码语言:javascript
复制
function isPowerOfTwo(n) {
    return n > 0 && (n & (n - 1)) === 0;
};