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

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

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

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

代码：

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 = 01100000，01100000实际上就是01110000去掉最后一个1的结果。

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

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的幂次方。

1
2
3

function isPowerOfTwo(n) {
    return n > 0 && (n & (n - 1)) === 0;
};