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