9
\$\begingroup\$

For example, these are expected outputs:

3: 2, 1
4: 4
5: 4, 1
6: 4, 2
7: 4, 2, 1
8: 8
9: 8, 1
...
20: 16, 4
...
25: 16, 8, 1
...
36: 32, 4
...
50: 32, 16, 2

Up to the max of 32 being the largest subunit. So then we get larger:

100: 32, 32, 32, 4
...
201: 32, 32, 32, 32, 32, 32, 8, 1
...

What is the equation / algorithm to implement this most optimally in JavaScript? By optimal I mean the fastest performance, or fewest primitive steps for example, with the least amount of temporary variables, etc. I feel like my solution below is a "brute force" approach which lacks elegance and it seems like it could be optimized somehow. Ideally there would be no Math.floor or division as well, if possible to use some sort of bit magic.

log(20)
log(25)
log(36)
log(50)
log(100)
log(200)

function log(n) {
  console.log(generate_numbers(n).join(', '))
}

function generate_numbers(n) {
  const chunks = count_chunks(n)
  const sum = chunks.reduce((m, i) => m + i, 0)
  const result = new Array(sum)
  const values = [ 1, 2, 4, 8, 16, 32 ]
  let i = chunks.length
  let j = 0
  while (i--) {
    let x = chunks[i]
    while (x--) {
      result[j++] = values[i]
    }
  }
  return result
}

function count_chunks(n) {
  let chunks = [0, 0, 0, 0, 0, 0]
  if (n >= 32) {
    let i = Math.floor(n / 32)
    chunks[5] = i
    n = n - (i * 32)
  }
  if (n >= 16) {
    chunks[4] = 1
    n = n - 16
  }
  if (n >= 8) {
    chunks[3] = 1
    n = n - 8
  }
  if (n >= 4) {
    chunks[2] = 1
    n = n - 4
  }
  if (n >= 2) {
    chunks[1] = 1
    n = n - 2
  }
  if (n >= 1) {
    chunks[0] = 1
  }
  return chunks
}

\$\endgroup\$
  • 10
    \$\begingroup\$ You don't need an algorithm for that. Your computer already represents numbers exactly that way, called "binary". The only task left is to grab the bits out of the number representation. And maybe Javascript isn't the language best suited for such an access to the machine internals. \$\endgroup\$ – Ralf Kleberhoff Sep 15 at 12:47
  • \$\begingroup\$ What exactly is the desired result, i.e., what you really need? The printing? The result of generate_numbers? The result of count_chunks? And is the order of the numbers important or could they also be ascending? \$\endgroup\$ – superb rain Sep 15 at 12:53
  • \$\begingroup\$ How large is your typical/average input number? \$\endgroup\$ – superb rain Sep 15 at 13:15
  • 1
    \$\begingroup\$ What you're doing here is printing the decimal place-values of the binary representation of the integer. (Or in the array, isolating each set bit below your cutoff. And repeating the max value n >> bitpos times.) e.g. (-x) & (x) to isolate the lowest set bit. (x-1) & (x) to clear the lowest set bit. Repeat until no low bits are set: x & ((1<<bitpos) - 1) \$\endgroup\$ – Peter Cordes Sep 15 at 13:47
  • 4
    \$\begingroup\$ Except for the part where it stops at 32, this is called "writing the number in binary" \$\endgroup\$ – user253751 Sep 15 at 14:37
15
\$\begingroup\$

CertainPerformance's solution using .toString(2) is clever, but for a fast solution to such an elementary problem, simple bit manipulation and a while loop is the way to go:

function split(number, bits = 5) {
  let unit = 1 << bits;
  const result = new Array(number >> bits).fill(unit);
  while (unit >= 1) {
    unit >>= 1;
    if (number & unit) result.push(unit);
  }
  return result;
}

const numbers = [1, 2, 3, 4, 5, 6, 7, 30, 31, 32, 33, 20, 25, 36, 50, 100, 201];
numbers.forEach(n => console.log(n, '=', split(n).join(' + ')));

In particular, you can indeed avoid division and Math.floor() by using the bitwise right shift operator >> instead: n >> k is a fast and compact way of calculating Math.trunc(n / 2**k) for any integer n and any non-negative integer k. Also, the bitwise AND operator & makes it easy to check whether an integer has a particular bit set: n & k evaluates to a non-zero value if and only if n and k have any set bits in common.


Ps. To make this code even faster, at the cost of some extra complexity, we can precalculate the length of the result array so that we don't need to use .push():

function split(number, bits = 5) {
  // precalculate the length of the result array
  const maxUnit = 1 << bits, prefixLength = number >> bits;
  let length = prefixLength, unit = maxUnit;
  while (unit >= 1) {
    unit >>= 1;
    if (number & unit) length++;
  }

  // allocate and fill the array
  const result = new Array(length).fill(maxUnit);
  let i = prefixLength; unit = maxUnit;
  while (unit >= 1) {
    unit >>= 1;
    if (number & unit) result[i++] = unit;
  }
  return result;
}

const numbers = [1, 2, 3, 4, 5, 6, 7, 30, 31, 32, 33, 20, 25, 36, 50, 100, 201];
numbers.forEach(n => console.log(n, '=', split(n).join(' + ')));

According to a quick benchmark, the preallocating version is about 40% faster than the one using .push() (and both are several times faster than the other solutions posted so far).


Pps. It turns out that, maybe a bit counter-intuitively, just building the entire output array one element at a time using .push() may be the simplest and fastest solution, at least for inputs that aren't too huge. The credit for this solution goes to superb rain, so I'll just link to their answer for it, but I've added it to my benchmark above. It seems to perform about as well in the benchmark (for all numbers from 0 to 999) as my fastest solution on Firefox, and outperforms all my solutions on Chrome.

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ I'm not sure I'm doing it right (I'm not familiar with js), can you check out mine at the bottom here? It seems to be faster than yours. \$\endgroup\$ – superb rain Sep 15 at 13:37
  • \$\begingroup\$ Does JavaScript not have a popcount intrinsic? Naively looping over every bit-position doesn't seem great. (Although I guess for bits=5 only looking at the low 5 bits, it's ok). If you fill the array backward, you can just isolate the lowest set bit one at a time, and clear it. (There are bithacks for both of those things) So you don't need an if in the loop, and only have to loop as many times as there are set bits in the low chunk. \$\endgroup\$ – Peter Cordes Sep 15 at 13:37
  • 2
    \$\begingroup\$ @superb rain yours goes slowest if you add a single large number to the test (I added a 2 milllion) since yours goes through the while loop so many times \$\endgroup\$ – Rick Sep 15 at 14:04
  • 2
    \$\begingroup\$ @Rick Sure, if the numbers get huge, it might lose. But the OP's largest example is 201 and Ilmari's largest is 999 (I think). Plus if they stop at 32, maybe that's a sign that they won't go much much higher. And it's precisely why I asked the OP "How large is your typical/average input number?". Why do you claim it doesn't add numbers less than 32? It does. \$\endgroup\$ – superb rain Sep 15 at 14:29
  • 2
    \$\begingroup\$ @superb rain good points. I was thinking that your solution is O(n) when it could be O(1) but since generating the array must be O(n) anyway, all of the solutions are going to be O(n). Looks like yours is faster till around 1500. \$\endgroup\$ – Rick Sep 15 at 14:50
9
\$\begingroup\$

Using Ilmari Karonen's answer as template, but not using Array and fill and filling a bit differently. On Ilmari's benchmark, it's the fastest for me (I got 7901 ops/s vs 6343 ops/s of their fastest, done with Chrome).

function split(number) {
  const result = [];
  for (let unit = 32; unit > 0; unit >>= 1) {
    while (number >= unit) {
      result.push(unit);
      number -= unit;
    }
  }
  return result;
}

const numbers = [1, 2, 3, 4, 5, 6, 7, 30, 31, 32, 33, 20, 25, 36, 50, 100, 201];
numbers.forEach(n => console.log(n, '=', split(n).join(' + ')));

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Interesting. I originally benchmarked my code on Firefox, and there your solution loses to my second one (with precalculated array length) even on the 0 to 999 benchmark. But on Chrome it's slightly faster. I guess Chrome has a more optimized implementation of Array.prototype.push. \$\endgroup\$ – Ilmari Karonen Sep 15 at 15:21
  • 2
    \$\begingroup\$ @IlmariKaronen I tried a few times in Firefox as well, mine was always slightly faster (about 4500 ops/s vs 4400 ops/s). By how much does mine lose in your Firefox? \$\endgroup\$ – superb rain Sep 15 at 17:13
  • 3
    \$\begingroup\$ Not by much, just a few percent, and it also varies. I also ran your benchmark about a dozen times and the biggest difference I saw was about 6%, while on a couple of runs they were close enough that JSBench declared them both winners, and on one run yours was actually faster by about 2%. Anyway, given that your code is nearly as fast as mine on FF and faster on Chrome, while also being considerably simpler, I'm happy to upvote it. \$\endgroup\$ – Ilmari Karonen Sep 15 at 17:25
  • \$\begingroup\$ Wouldn't while (number > 0) { result.push( number & (-number) ); number = number & (number-1); } still be faster (but with reverse order output)? \$\endgroup\$ – Hagen von Eitzen Sep 16 at 14:46
  • \$\begingroup\$ @HagenvonEitzen I don't know whether it would be faster, but it wouldn't do the 32 limit. But yes, that's exactly why I asked whether the order matters. \$\endgroup\$ – superb rain Sep 16 at 14:52
6
\$\begingroup\$

With toString(2), you can get the binary representation of a number. You can take the input modulo 32 to get the last 5 characters of that, which will determine which of the 16, 8, 4, 2, 1 numbers need to be included. Then, from what's left (which can be gotten by flooring the input over 32), just divide by 32 to figure out how many 32s are needed at the beginning:

const format = (num) => {
  const arr = new Array(Math.floor(num / 32)).fill(32);
  const finalBits = [...(num % 32).toString(2)];
  const { length } = finalBits;
  const finalItems = finalBits
    .map((char, i, finalBits) => char * (2 ** (length - i - 1)))
    .filter(num => num)
  console.log(arr.concat(finalItems));
};
[1, 2, 3, 4, 5, 6, 7, 30, 31, 32, 33, 20, 25, 36, 50, 100, 201].forEach(format);

That's the version that I'd prefer. Without iterating through the final elements multiple times, another option is:

const format = (num) => {
  const arr = new Array(Math.floor(num / 32)).fill(32);
  const { length } = arr;
  Array.prototype.forEach.call((num % 32).toString(2), (char, i, finalBits) => {
    if (char === '1') {
      arr.push(2 ** (finalBits.length - i - 1));
    }
  });
  console.log(arr);
};
[1, 2, 3, 4, 5, 6, 7, 30, 31, 32, 33, 20, 25, 36, 50, 100, 201].forEach(format);

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Generic solution

You could refactor and shorten your code with recursion:

function binary_buckets(n, power=1){
  if (n === 0) {
    return [];
  }
  const powers = binary_buckets(Math.floor(n / 2), power*2);

  if (n % 2 === 1){
    powers.push(power);
  }

  return powers;
}

console.log(binary_buckets(125653));
// [ 65536, 32768, 16384, 8192, 2048, 512, 128, 64, 16, 4, 1]

This is basically just a standard recursive algorithm in order to convert a number to binary.

Specific solution

You can then declare another function to stop at 32:

function binary_buckets(n, power=1){
  if (n === 0) {
    return [];
  }
  const powers = binary_buckets(Math.floor(n / 2), power*2);

  if (n % 2 === 1){
    powers.push(power);
  }

  return powers;
}

function small_binary_buckets(n){
  const tmp = new Array(Math.floor(n / 32)).fill(32);
  return tmp.concat(binary_buckets(n % 32));
}

console.log(small_binary_buckets(125));
// [ 32, 32, 32, 16, 8, 4, 1 ]
console.log(small_binary_buckets(17));
// [ 16, 1 ]

It might not be the fastest solution, but it's at least concise and readable.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.