JavaScript 循环太慢

Question

我正在处理 codewars 的任务，无法理解如何使这个函数在 <= 200000000000000 的大数字下更快地工作。该函数的目标非常简单 - 我只需要计算二进制中所有“1”的出现次数“左”和“右”(包括两者)之间的数字表示。

function countOnes(left, right) {
var sum=0;
for (var i=left; i<=right; i++){
    var h=i.toString(2);
    var len=h.length;
    for (var j=0; j<len; j++){
        if (h[j]==1){sum++;}
    }
}
return sum;
}

提前致谢

Answer 1

由于按位运算符被限制为 32 位(见备注)，此解决方案将此限制推至 2**53 -1，这是 JS Number.MAX_SAFE_INTEGER 的值br/>见https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/MAX_SAFE_INTEGER

const p32 = 2**32

function countOnes_John_MJojo(left, right )
  {
  let sum = 0
  for (let V=left; V<=right; V++)
    {
    for (let N=V;N; N&=N-1) sum++
    for (let N=Math.trunc(V/p32);N; N&=N-1) sum++
    } 
  return sum
  }

/- 历史:-\
\----------------/

使用按位运算符会快一点:
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators

->逻辑与
-> 逻辑右移

function countOnesBin( left, right )
  {
  let sum = 0
  for (let N=left; N<=right; N++)
    {
    let Bin = N
    for(let x = N.toString(2).length;x--;)
      {
      if ( Bin & 1 ) sum++ 
      Bin = Bin >>1
      } 
    } 
  return sum
  }

@CodeBling 建议这一个可能会更好!

function countOnes_CodeBling  (left, right)
  {
  let sum = 0
  for (let N=left; N<=right; N++)
    {
    for(let Bin = N; Bin > 0; Bin = Bin >> 1)
      { if ( Bin & 1 ) sum++  } 
    } 
  return sum
  }

这是最好的!我不知道这种可能性:感谢@John

function countOnes_John (left, right)
  {
  let sum = 0
  for (let V=left; V<=right; V++)
    {
    for (let N=V;N; N&=N-1) sum++
    } 
  return sum
  }