JavaScript function to check how many bits are required to encode a number?

Question

I have the following problem. Here is sample input/output data:

i: 0, o: 1 (0)
i: 1, o: 1 (1)
i: 2, o: 2 (10)
i: 3, o: 2 (11)
i: 4, o: 3 (100)
i: 5, o: 3 (101)
i: 6, o: 3 (110)
i: 7, o: 3 (111)

However, that is just using the smallest number of bits to encode the number. I want something slightly different, having a hard time wrapping my head around it. I want the output to be a power of 2.

i: 0, o: 2 (00)
i: 1, o: 2 (01)
i: 2, o: 2 (10)
i: 3, o: 2 (11)
i: 4, o: 4 (0100)
i: 5, o: 4 (0101)
i: 6, o: 4 (0110)
i: 7, o: 4 (0111)
i: 8, o: 4 (1000)
...
i.... o: 8
...
i.... o: 16
...

How do I write a function that takes an integer in JavaScript, and returns to me o for that number? One that is doing it efficiently and not converting things to strings and using random JS helper functions :)

I think the second sequence is just the first sequence rounded up to the nearest power of 2. — Asad Saeeduddin, Jun 25 '20 at 22:36
Uh, `1` would be a power of `2` as well. Why don't you want that? — Bergi, Jun 25 '20 at 23:38

Bergi · Accepted Answer · 2020-06-26T00:36:02.437

If you're into bit fiddling, you could find the position of the MSB then find the next power of 2 (with an exceptional case for the two values below 2).

We can also find a closed form:

const bits = x => Math.floor(1+Math.log2(x))
const npot = x => Math.pow(2, Math.ceil(Math.log2(x)))
const f = x => x < 2 ? 2 : npot(bits(x))

However, given the small number of powers of two in range, it's much easier and faster to just use a condition ladder:

const f = x => {
  if (x < 2**2) return 2;
  if (x < 2**4) return 4;
  if (x < 2**8) return 8;
  if (x < 2**16) return 16;
  if (x < 2**32) return 32;
  return 64;
}

(When working with bigints, use a loop for that…)

score -1 · Answer 2 · answered Jun 25 '20 at 23:21

If your intention is to write the function, if there is no correlation between the inputs you might have to iterate through the 64 bits one at a time using the binary operators. And if you want just the 2nd use case check if it already a power of 2 or not, and do vice versa. To check for power of 2. n~(n-1) == 0

P.S in mobile so mind the bad editting.

JavaScript function to check how many bits are required to encode a number?

2 Answers2