假设我有一个整数I,并希望以二进制形式得到1的计数.
我目前正在使用以下代码.
- Number(i.toString(2).split("").sort().join("")).toString().length;
有更快的方法吗?我正在考虑使用按位运算符.有什么想法吗?
注意:我在32位限制范围内.
解决方法
您可以使用此
Bit Twiddling Hacks集合中的策略:
- function bitCount (n) {
- n = n - ((n >> 1) & 0x55555555)
- n = (n & 0x33333333) + ((n >> 2) & 0x33333333)
- return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24
- }
- console.log(bitCount(0xFF)) //=> 8
请注意,上述策略仅适用于32位整数(JavaScript中按位运算符的限制).
对于更大整数的更通用的方法将涉及单独计算32位块(感谢harold的灵感):
- function bitCount (n) {
- var bits = 0
- while (n !== 0) {
- bits += bitCount32(n | 0)
- n /= 0x100000000
- }
- return bits
- }
- function bitCount32 (n) {
- n = n - ((n >> 1) & 0x55555555)
- n = (n & 0x33333333) + ((n >> 2) & 0x33333333)
- return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24
- }
- console.log(bitCount(Math.pow(2,53) - 1)) //=> 53
您还可以使用正则表达式:
- function bitCount (n) {
- return n.toString(2).match(/1/g).length
- }
- console.log(bitCount(0xFF)) //=> 8