将一个值分解为两个幂的结果

Question

是否可以得到整数，作为二的幂的结果，形成一个值？

Example: 
129 resolves [1, 128]
77 resolves [1, 4, 8, 64]

我已经考虑过使用 Math.log 并使用按位比较器执行 foreach。还有其他更漂亮的方案吗？

Answer 1

最简单的方法是使用单个位值，从 1 开始并移动该位 'left' 直到其值大于要检查的值，将每个位步长与该值逐位比较。设置的位可以存储在数组中。

function GetBits(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));

由于移动位可以看作是2的幂，所以可以直接将当前位值压入结果数组。

Example

Answer 2

求出该数中包含的最大的2次方。
从原始数字中减去并将其添加到列表中。
减少指数并检查新的 2 的幂是否小于该数字。
如果小于则从原始数字中减去它并将其添加到列表中。
否则转第3步
当你的数字为0时退出。

Answer 3

我正在考虑创建一个 2 个数的所有幂 <= 你的数的列表，然后使用加减算法找出正确数字的组。例如编号 77：这组因数是 { 1,2,4,8,16,32,64} [ 64 是 2 小于或等于 77 的最大幂]

一种算法，不断从您刚创建的组中减去小于或等于您的数字的最大数字，直到得到零。

77-64 = 13 ==> [64]

13-8 = 7 ==> [8]

7-4 = 3 ==> [4]

3-2 = 1 ==> [2]

1-1 = 0 ==> [1]

希望你能理解我的算法，原谅我的英语不好。

Answer 4

您可以将其他语言的解决方案改编为 javascript。在这个 SO 问题中，您将找到一些使用 Java 解决问题的方法（您可以选择您认为更优雅的方法）。

decomposing a value into powers of two

我将其中一个答案改编为 javascript 并提出了这段代码：

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

Answer 5

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

alert(getBits(77));

将一个值分解为两个幂的结果

Decomposing a value into results of powers of two

javascript

math