假设我有一个整数 I,想要获取二进制形式的 1 的计数。
我目前正在使用以下代码。
Number(i.toString(2).split("").sort().join("")).toString().length;
有没有更快的方法来做到这一点?我正在考虑使用按位运算符。有什么想法吗?
注意:
i
不超过 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
递归非常好但慢方式:
function count1(n, accumulator=0) {
if (n === 0) {
return accumulator
}
return count1(n/2, accumulator+(n&1))
}
console.log(count1(Number.MAX_SAFE_INTEGER));
但是如果你想要一个非常快的(比 T.J. Crowder 答案更快)):
count1s=(n)=>n.toString(2).replace(/0/g,"").length
console.log(count1s(Number.MAX_SAFE_INTEGER));
注意:其他一些解决方案不适用于位整数(> 32 位) 这两个做!
现在,如果我们只考虑 32 位数字,最快的方法是这样的:
function bitCountBigInt (n) {
n = BigInt(n)
let bits = 0
while (n !== 0n) {
bits += Number(n & 1n)
n >>= 1n
}
return bits
}
function count1s32(i) {
var count = 0;
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
i = (i + (i >> 4)) & 0x0f0f0f0f;
i = i + (i >> 8);
i = i + (i >> 16);
count += i & 0x3f;
return count;
}
console.log(count1s32(0xffffffff));
53 位比较:
32 位比较:
基准在这里! (因为 jsperf 经常宕机)。
function log(data) {
document.getElementById("log").textContent += data + "\n";
}
benchmark = (() => {
time_function = function(ms, f, num) {
var z;
var t = new Date().getTime();
for (z = 0;
((new Date().getTime() - t) < ms); z++) f(num);
return (z / ms)
} // returns how many times the function was run in "ms" milliseconds.
// two sequential loops
count1s = (n) => n.toString(2).replace(/0/g, "").length
// three loops and a function.
count1j = (n) => n.toString(2).split('').filter(v => +v).length
/* Excluded from test because it's too slow :D
function count1(n, accumulator=0) {
if (n === 0) {
return accumulator
}
return count1(n / 2, accumulator + (n & 1))
}
*/
function bitCountBigInt (n) {
n = BigInt(n)
let bits = 0
while (n !== 0n) {
bits += Number(n & 1n)
n >>= 1n
}
return bits
}
function countOnes(i) {
var str = i.toString(2);
var n;
var count = 0;
for (n = 0; n < str.length; ++n) {
if (str[n] === "1") {
++count;
}
}
return count;
} // two sequential loops ( one is the toString(2) )
function count1sb(num) {
i = Math.floor(num / 0x100000000);
// if (i > 0) {
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
i = (i + (i >> 4)) & 0x0f0f0f0f;
i = i + (i >> 8);
i = i + (i >> 16);
count = i & 0x3f;
i = num & 0xffffffff;
// }
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
i = (i + (i >> 4)) & 0x0f0f0f0f;
i = i + (i >> 8);
i = i + (i >> 16);
count += i & 0x3f;
return count;
}
function benchmark() {
function compare(a, b) {
if (a[1] > b[1]) {
return -1;
}
if (a[1] < b[1]) {
return 1;
}
return 0;
}
funcs = [
[count1s, 0],
[count1j, 0],
[count1sb, 0],
[countOnes, 0],
[bitCountBigInt, 0]
];
funcs.forEach((ff) => {
console.log("Benchmarking: " + ff[0].name);
ff[1] = time_function(2500, ff[0], Number.MAX_SAFE_INTEGER);
console.log("Score: " + ff[1]);
})
return funcs.sort(compare);
}
return benchmark;
})()
log("Starting benchmark...\n");
res = benchmark();
console.log("Winner: " + res[0][0].name + " !!!");
count = 1;
res.forEach((r) => {
log((count++) + ". " + r[0].name + " score: " + Math.floor(10000 * r[1] / res[0][1]) / 100 + ((count == 2) ? "% *winner*" : "% speed of winner.") + " (" + Math.round(r[1] * 100) / 100 + ")");
});
log("\nWinner code:\n");
log(res[0][0].toString());
<textarea cols=80 rows=30 id="log"></textarea>
基准测试将运行 10 秒。
执行
n = n & (n - 1)
操作时,您删除了数字中的最后 1 位。
据此,可以使用以下算法:
function getBitCount(n) {
var tmp = n;
var count = 0;
while (tmp > 0) {
tmp = tmp & (tmp - 1);
count++;
}
return count;
}
console.log(getBitCount(Math.pow(2, 10) -1));
考虑到您正在创建、排序和连接一个数组,如果它确实是您想要的更快,那么您可能最好采用无聊的方式:
console.log(countOnes(8823475632));
function countOnes(i) {
var str = i.toString(2);
var n;
var count = 0;
for (n = 0; n < str.length; ++n) {
if (str[n] === "1") {
++count;
}
}
return count;
}
(如果您需要支持过时的浏览器,请使用
str.charAt(n)
而不是 str[n]
。)
它不像l33t或简洁,但是我打赌它更快它快得多更快:
...在 Firefox、IE11 上也类似(IE11 程度较低)。
以下适用于任何数字:
var i=8823475632,count=0;while (i=Math.floor(i)) i&1?count++:0,i/=2
console.log(count); //17
将 i 更改为您想要的值或将其包装为函数
如果整数在 32 位以内,则以下工作
var i=10,count=0;while (i) i&1?count++:0,i>>=1
如果您想使用绝对的单衬解决方案,您可以看看这个。
countBits = n => n.toString(2).split('0').join('').length;
1.这里n.toString(2)将n转换为二进制字符串
2.split('0') 仅在以下位置将数组从二进制字符串中分割出来 0,因此返回 n
的二进制中仅存在 1 的数组3.join('') 连接所有 1 并生成一串 1
4.length 找到实际计算 n 中 1 的数量的字符串长度。
更多“有趣”的 1 行:
递归:递归计算每个位,直到没有更多位设置
let f = x => !x ? 0 : (x & 1) + f(x >>= 1);
功能:分割x的以2为底的字符串并返回位集的累积长度
g = x => x.toString(2).split('0').map(bits => bits.length).reduce((a, b) => a + b);
不断检查最后一位是否为1,然后将其删除。如果发现最后一位是 1,则会将其添加到结果中。
Math.popcount = function (n) {
let result = 0;
while (n) {
result += n % 2;
n = n >>> 1;
};
return result;
};
console.log(Math.popcount(0b1010));
对于 64 位,您可以将数字表示为两个整数,第一个是顶部 32 位,第二个是底部 32 位。要计算 64 位中的个数,您可以将它们分成 2 个 32 位整数,并添加第一个和第二个的 popcount。
您可以跳过
Number
、sort
和第二个toString
。使用 filter
仅考虑数组中的 1
(真值),然后检索使用 length
有多少个通过。
i.toString(2).split('').filter(v => +v).length
如果您只想计算位数,这是简单的解决方案!
const integer = Number.MAX_SAFE_INTEGER;
integer.toString(2).split("").reduce((acc,val)=>parseInt(acc)+parseInt(val),0);
const bitCount = (n) => (n.toString(2).match(/1/g) || []).length;
function bitCount(n) {
let count = 0;
while(n) {
count += n & 1;
n >>= 1;
}
return count;
}
Brian Kernighan
算法 function bitCount(n) {
let count = 0;
while(n) {
n &= (n-1);
count ++;
}
return count;
}
测试:
bitCount(0) // 0
bitCount(1) // 1
bitCount(2) // 1
bitCount(3) // 2
或者,采用上述任何函数,生成一个值为 (0..255) 的数组,(保存数组)并对每个 8 位组进行查找。对于 n 位数字,需要 ceil((n-1)/8) 移位、and 和查表。