JavaScript loop is too slow

Question

I'm working on a task on codewars and cannot understand how to make this function work faster for large numbers <= 200000000000000. The goal of the function is very simple - I just need to count all '1' occurrences in binary representations of numbers between 'left' and 'right' (including both).

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;
}

Thanks in advance

I'm pretty sure that amount of iterations will inevitably be slow, but I'm looking forward to be proven wrong — Ayrton, Oct 29 '19 at 18:05
The trick on such tasks is most often to *not do what the question describes*. You usually don't have to go over all possible combinations at all. — Jonas Wilms, Oct 29 '19 at 18:07
Hint: Use a look-up table and attack the number in chunks of 16 bits where you already know the counts for those. — tadman, Oct 29 '19 at 18:07
Does this answer your question? [How to count 1 bits in an integer in JavaScript](https://stackoverflow.com/questions/52007167/how-to-count-1-bits-in-an-integer-in-javascript) — Barmar, Oct 29 '19 at 18:09
The first thing to do is some research to see if anyone's done this before (the answer is almost always "yes" [thanks @Barmar]). If not, check to see if someone's done parts of the process before -- for example, finding all instances of a substring within a string could probably be done faster than looping over all of the characters. — Heretic Monkey, Oct 29 '19 at 18:22
[Related: OEIS A000788](https://oeis.org/A000788). FYI if you find a formula faster than O(n) here, the solution would be to calculate `a(right) - a(left - 1)` — Patrick Roberts, Oct 29 '19 at 18:31
Does this answer your question? [Efficiently count the number of bits in an integer in JavaScript](https://stackoverflow.com/questions/43122082/efficiently-count-the-number-of-bits-in-an-integer-in-javascript) — benvc, Oct 29 '19 at 22:21
I have done some test on https://jsbench.me/ and it is the faster one — Mister Jojo, Oct 30 '19 at 11:02

Mister Jojo · Answer 1 · 2019-10-29T23:30:03.753

1

As Bitwise operators are limited to 32bits (see remarks) this solution push this limit to 2**53 -1 which is the value of JS Number.MAX_SAFE_INTEGER
see 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
  }

/- history : -\
\--------------/

A little bit faster is using Bitwise operators:
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators

-> logical AND
-> Logical Right shift

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
  }

as @CodeBling suggest this one could be better !

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
  }

this one is the best! I did not know the possibility: Thanks to @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
  }

edited Oct 29 '19 at 23:30

answered Oct 29 '19 at 18:37

Mister Jojo

20,093
6
21
40

I think we're missing an end condition on the second loop? – Codebling Oct 29 '19 at 18:44
no, this (reverse) loop stop when x is zero, last argument stay empty – Mister Jojo Oct 29 '19 at 18:46
Right, x _is_ the condition, sorry! – Codebling Oct 29 '19 at 18:47
Couldn't you also loop with `for(let Bin = N; Bin > 0; Bin = Bin >> 1) if ( Bin & 1 ) sum++` ? It would avoid the costly `toString` – Codebling Oct 29 '19 at 18:49
@CodeBling ! nice one ! – Mister Jojo Oct 29 '19 at 18:54
Since the OP needs it to work with numbers beyond the int32 range, bitwise operators are out of the question. – georg Oct 29 '19 at 20:57
Much faster to do... for (;N;N&=N-1) {sum++;} in replacement to Code Bling for next loop suggestion. Why would this be faster? If there are X bit set then this would loop exactly X times regardless where the bits lies in N. Proof of concept: https://jsfiddle.net/ebLyj0rd/1/ – John Oct 29 '19 at 21:27
@John it's really very clever, I did not know this property on binary numbers. Is there a mathematical proof of this? – Mister Jojo Oct 29 '19 at 21:58
1

Not sure where I picked this up (Maybe from Program Now magazine in 90s) but stuck in my head ever since I first came across it many years ago. If you do console.log(N.toString(2)) and console.log((N-1).toString(2)) you can see why this works when you AND these 2 numbers together it eliminate the lowest set bit. Also, bit-level operations are limited to 32 bit so >> won't work as expected on numbers larger than 32 bits. – John Oct 29 '19 at 23:03
@georg I have added a new solution solution for numbers beyond int32 ( and < int53) which is fine for the OP ask ( and still with the use of bitwise operators ;-) – Mister Jojo Oct 29 '19 at 23:36
@John Yes, I did some tests to check myself (and also to understand how it works) and it makes perfect sense that it works. The only problem is that now, it's also stuck in my head. (I also changed the code to work beyond 32bits) – Mister Jojo Oct 29 '19 at 23:43

score 0 · Answer 2 · answered Oct 29 '19 at 18:30

0

You could avoid the second iteration using a split function and adding the amount of chunks minus one to your sum:

function countOnes(left, right) {
  var sum=0;
  for (var i=left; i<=right; i++){
    var h=i.toString(2);
    sum += h.split('1').length -1;
  }
  return sum;
}

It would be still slow, but a lot faster than your original code.

answered Oct 29 '19 at 18:30

Silvano González

371
3
12

Have you actually benchmarked this across multiple browsers or are you just assuming it's faster? – Patrick Roberts Oct 29 '19 at 18:32
1

I would guess that `.split` will internally be an `O(n)` operation as well, so you're not changing this from `O(n^2)`. Although it might be faster than a loop, since it's going to use native implementation. Still, it also might *not* be faster as it might fragment the memory too much and cause a lot of GC cycles. All in all, I don't see this as a clear improvement. – VLAZ Oct 29 '19 at 18:37

JavaScript loop is too slow

2 Answers2