Algorithm for dividing a number into largest "power of two" buckets? 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 &quot;brute force&quot; 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) =&gt; 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 &gt;= 32) {
    let i = Math.floor(n / 32)
    chunks[5] = i
    n = n - (i * 32)
  }
  if (n &gt;= 16) {
    chunks[4] = 1
    n = n - 16
  }
  if (n &gt;= 8) {
    chunks[3] = 1
    n = n - 8
  }
  if (n &gt;= 4) {
    chunks[2] = 1
    n = n - 4
  }
  if (n &gt;= 2) {
    chunks[1] = 1
    n = n - 2
  }
  if (n &gt;= 1) {
    chunks[0] = 1
  }
  return chunks
}
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 &lt;&lt; bits;
  const result = new Array(number &gt;&gt; bits).fill(unit);
  while (unit &gt;= 1) {
    unit &gt;&gt;= 1;
    if (number &amp; 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 =&gt; console.log(n, '=', split(n).join(' + ')));



In particular, you can indeed avoid division and Math.floor() by using the bitwise right shift operator &gt;&gt; instead: n &gt;&gt; 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 &amp; makes it easy to check whether an integer has a particular bit set: n &amp; 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 &lt;&lt; bits, prefixLength = number &gt;&gt; bits;
  let length = prefixLength, unit = maxUnit;
  while (unit &gt;= 1) {
    unit &gt;&gt;= 1;
    if (number &amp; unit) length++;
  }

  // allocate and fill the array
  const result = new Array(length).fill(maxUnit);
  let i = prefixLength; unit = maxUnit;
  while (unit &gt;= 1) {
    unit &gt;&gt;= 1;
    if (number &amp; 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 =&gt; 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.