1. 优化做法

有个不错的规律,对于一个整数n,运算结果n & (n - 1)可以消除而今中从右向左出现的第一个1。比如二进制数011,减去 1 是010,做与运算的结果就是010

利用这个性质,可以逐步剔除原数二进制中的1。每次剔除,统计量count都加 1;直到所有的1都被移除,原数变成0

/**
 * @param {Number} n
 */
function numberOf1(n) {
  let count = 0;

  while (n) {
    ++count;
    n = n & (n - 1);
  }

  return count;
}

/**
 * 测试代码
 */

console.log(numberOf1(3));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2. 如何判断 2 的整次方

如果一个数是 2 的整次方,那么只有一个二进制位为 1。所以,n & (n - 1)如果不是 1,说明二进制表示中有多个 1,那么就不是 2 的整次方;否则,就是得。

/**
 * 判断是否是2的整次方
 * @param {Number} n
 */
function is2Power(n) {
  if (n <= 0) {
    throw new Error("Unvalid param");
  }

  return !(n & (n - 1));
}

console.log(is2Power(128));
1
2
3
4
5
6
7
8
9
10
11
12
13

3. 求多少个不同的二进制位

题目:输入两个整数 m 和 n,计算需要改变 m 的二进制表示中的多少位才能得到 n。翻译过来就是:m 和 n 二进制位上有多少个不同的数。

思路:

  1. m 和 n 进行异或操作,不同的位都变成了 1
  2. 利用前面的思路统计 1 的个数
/**
 * 求解二进制表示中有多少位不相同
 * @param {Number} a
 * @param {Number} b
 */
function getDiffBytes(a, b) {
  let count = 0,
    n = a ^ b;

  while (n) {
    ++count;
    n = n & (n - 1);
  }

  return count;
}

/**
 * 测试代码
 */

console.log(getDiffBytes(1, 1));
console.log(getDiffBytes(3, 1));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23