Algorithm for dividing a number into largest "power of two" buckets?

Question

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
}

Answer 1

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.

Answer 2

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(' + ')));

Answer 3

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

Answer 4

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.