3

我需要实现一个函数，它使用 java 将一个值分解为 2 的幂。

例如：14= 8 + 4 + 2

我需要找到值被分解的两个幂。对于上面的例子，我需要 2,3,1 作为输出。我怎么能实现呢？

4

4 回答 4

9

利用 Java 使用的二进制表示。我不知道您希望 2 的幂采用什么形式，但是您可以通过移位和逐位&1 来逐位循环遍历这些位以测试每个位。每个 1 位代表总和中 2 的幂。

例如：

List<Integer> powers = new ArrayList<Integer>();
n = . . .; // something > 0
int power = 0;
while (n != 0) {
    if ((n & 1) != 0) {
        powers.add(1 << power);
        // or, if you just need the exponents:
        // powers.add(power);
    }
    ++power;
    n >>>= 1;
}
于 2012-11-04T07:41:08.720 回答
8

由于整数已经表示为 2 的幂，并且 Java 有一组位的集合，我将使用这两个。

public static void main(String[] args) {
    System.out.println(bitsSet(14));
}

public static BitSet bitsSet(long num) {
    BitSet bitSet = new BitSet();
    for (int i = 0; i < 64; i++)
        if (((num >>> i) & 1) != 0)
            bitSet.set(i);
    return bitSet;
}

印刷

{1, 2, 3}
于 2012-11-04T07:47:08.837 回答
2

为此，您通常使用按位运算，即移位 (<<,>>,>>>) 和按位与 (&) 运算符，因为计算机中整数的内部表示已经是二进制的，即你需要什么。

在二进制表示中，每个整数值都是 2 的幂的组合：1、2、4、8、16、32、...

所以，十进制的 14 是二进制的 1110：8 + 4 + 2 + 0。

如果您追求一些不错的通用算法，您可能希望开始将十进制数分解为 10 的幂，然后将您的解决方案扩展到其他基数，例如 2。

于 2012-11-04T07:47:21.207 回答
1

您可以简单地从该值中减去 2 并继续减去后续更高的幂。

int x = 0;
int value = args[0];
for (i=0, (value - Math.pow(2, i)) >= 0, i++) {
    value = value - Math.pow(2, i);
    x++;
}
for (i=0, i<x, i++) {
    System.out.println("addent: " + Math.pow(2, i);
}
于 2012-11-04T07:53:45.113 回答