这个程序实际上是如何工作的？

Question

我写了一个递归方法，它将接受一个数字，return 2 的下一个幂。如果输入的数字是 2 的幂，它将映射到自身。这假定 n > 0

static int nextPower1(int n) {
    if(n == 0) {
        System.out.println("nextPower(" + n + ") = 2");
        return 2;
    } else if(n == 1) {
        System.out.println("nextPower(" + n + ") = 1");
        return 1;
    } else {
        int lastBit = n & 1;
        int secondLastBit = (n >> 1) & 1;
        int restOfTheBits = (n >> 2);

        int result = nextPower1(restOfTheBits << 1 | secondLastBit ^ lastBit);
        return result << 1;
    }

我不明白的是，如何对最后两位进行异或运算并设置倒数第二位 return 是正确的 2 的幂？这个按位技巧是如何工作的？

大编辑：

好的，我知道哪里出了问题，通过更新基本案例并将 XOR 更改为 OR，我认为它已修复。我把它放在一个循环中来测试它。循环检查从 Integer.MAX_VALUE 到 Integer.MAX_VALUE 的 2 的幂。它 return 将预期答案从 Integer.MIN_VALUE 编辑到至少 (1 << 30)，尽管在那之后它中断了。我怀疑是因为整数是有符号的。更新后的代码：

static int nextPower2(int n) {
    if(n == 3) {
        return 4;
    } else if(n < 4) {
        return 1 << (n >> 1);
    } else {
        return nextPower(((n >> 2) << 1) | ((n >> 1) & 1) | (n & 1)) << 1;
    }
}

Answer 1

此代码已损坏，它总是 returns 错误的答案，例如一个 1 后跟一个或多个零，后跟两个 1：1011、10011 等。（因为当它递归时，它将成对的 1 组合成一个 0，它来自该点使它与传入的 1000、10000 等无法区分）

（编辑：对于所有具有偶数个 1 位的值来说都是错误的 msb的权利。每对异或为 0，丢失必要的信息以获得正确的结果。 - AR.)

递归循环正在将最低有效位汇总到数字中作为卷起部分是否包含任何 1 的一种历史记录。隔离两个最低有效位只会让代码更难理解；它正在 otherBits = n >> 1; return nextPower1(otherBits ^ lastBit)

查看剩下的最后两位（最高有效位和卷起历史位），如果历史为零则最高有效位是唯一的设置位，它本身是 2 的下一次幂。如果历史位是一个，然而，那么下一个二的幂是下一个位的位置，一个过了 msb。（如果只有历史位正确工作；见下文）

代码看的不是最后两位，而是 msb 和历史位。如果为 1，则仅设置了 msb，history 为零，并且 returns 1（self）为 2 的幂。如果为 0，则历史位为设置和 returns 下一个更高的幂 (2)。随着递归展开，电源（1 或 2）移回原来的 msb 位置，产生 msb 或 2 的下一个更大的幂。

但是，由于历史不通过零传播，因此中断。

要修复，递归需要修复历史（使用 OR，而不是 XOR），并且最后不要将历史位混合到 msb 中，例如：

nextPower( int n ) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    if (n == 3) return 4;
    return nextPower((n >> 1) | (n & 1)) << 1;
}

（测试 (n==0) 以支持 n >= 0，代码明确不支持）

Answer 2

按如下方式修复代码使其工作（参见http://ideone.com/P5s4rd）：

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        int n;
        int result;
        for (n=0;n<=16;n++) {
            result = nextPower(n);
            System.out.println("Next power of " + n + " is " + result);
        }
    }

    static int nextPower(int n) {
        int result;
        result = nextPower1(n);
        if (n<=1 || result ==n)
            return result;
        else
            return result * 2;
    }


    static int nextPower1(int n) {
        if(n == 0) {
            return 1;
        } else if(n == 1) {
            return 1;
        } else {
            int lastBit = n & 1;
            int secondLastBit = (n >> 1) & 1;
            int restOfTheBits = (n >> 2);

            int result = nextPower1(restOfTheBits << 1 | secondLastBit ^ lastBit);
            return result << 1;
        }
    }
}

您得到以下输出：

Next power of 0 is 1 (0 <= 2 power 0)
Next power of 1 is 1 (1 <= 2 power 0)
Next power of 2 is 2 (2 <= 2 power 1)
Next power of 3 is 4 (3 <= 2 power 2)
Next power of 4 is 4 ...etc
Next power of 5 is 8
Next power of 6 is 8
Next power of 7 is 8
Next power of 8 is 8
Next power of 9 is 16
Next power of 10 is 16
Next power of 11 is 16
Next power of 12 is 16
Next power of 13 is 16
Next power of 14 is 16
Next power of 15 is 16
Next power of 16 is 16

这个程序实际上是如何工作的？

How does this program actually work?

java

binary

bit-manipulation

大编辑：