Decomposing A Value Into Results Of Powers Of Two

Is it possible to get the integers that, being results of powers of two, forms a value? Example: 129 resolves [1, 128] 77 resolves [1, 4, 8, 64] I already thought about using Mat

Solution 1:

The easiest way is to use a single bit value, starting with 1 and shift that bit 'left' until its value is greater than the value to check, comparing each bit step bitwise with the value. The bits that are set can be stored in an array.

functionGetBits(value) {
  var b = 1;
  var res = [];
  while (b <= value) {
    if (b & value) res.push(b);
    b <<= 1;
  }
  return res;
}

console.log(GetBits(129));
console.log(GetBits(77));
console.log(GetBits(255));

Since shifting the bit can be seen as a power of 2, you can push the current bit value directly into the result array.

Example

Solution 2:

You can adapt solutions from other languages to javascript. In this SO question you'll find some ways of solving the problem using Java (you can choose the one you find more elegant).

decomposing a value into powers of two

I adapted one of those answers to javascript and come up with this code:

var powers = [], power = 0, n = 129;// Gives [1,128] as output.
while (n != 0) {
    if ((n & 1) != 0) {
        powers.push(1 << power);
    }
    ++power;
    n >>>= 1;
}
console.log(powers);

Fiddle

Solution 3:

1. Find the largest power of two contained in the number.
2. Subtract from the original number and Add it to list.
3. Decrement the exponent and check if new 2's power is less than the number.
4. If less then subtract it from the original number and add it to list.
5. Otherwise go to step 3.
6. Exit when your number comes to 0.

Solution 4:

I am thinking of creating a list of all power of 2 numbers <= your number, then use an addition- subtraction algorithm to find out the group of correct numbers. For example number 77: the group of factors is { 1,2,4,8,16,32,64} [ 64 is the greatest power of 2 less than or equal 77]

An algorithm that continuously subtract the greatest number less than or equal to your number from the group you just created, until you get zero.

77-64 = 13 ==> [64]

13-8 = 7 ==> [8]

7-4 = 3 ==> [4]

3-2 = 1 ==> [2]

1-1 = 0 ==> [1]

Hope you understand my algorithm, pardo my bad english.

Solution 5:

function getBits(val, factor) {
    factor = factor || 1;
    if(val) {
        return (val % 2 ? [factor] : []).concat(getBits(val>>1, factor*2))
    }
    return [];
}

alert(getBits(77));