1. 优化做法

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @param {Number} n
*/
function numberOf1(n) {
let count = 0

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

return count
}

/**
* 测试代码
*/

console.log(numberOf1(3))

2. 如何判断 2 的整次方

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

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* 判断是否是2的整次方
* @param {Number} n
*/
function is2Power(n) {
if (n <= 0) {
throw new Error('Unvalid param')
}

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

console.log(is2Power(128))

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

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

思路:

  1. m 和 n 进行异或操作,不同的位都变成了 1
  2. 利用前面的思路统计 1 的个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 求解二进制表示中有多少位不相同
* @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))