位反转与位运算

Question

我正在尝试在一个字节中进行位反转。我使用以下代码：

static int BitReversal(int n)
{
    int u0 = 0x55555555; // 01010101010101010101010101010101
    int u1 = 0x33333333; // 00110011001100110011001100110011
    int u2 = 0x0F0F0F0F; // 00001111000011110000111100001111
    int u3 = 0x00FF00FF; // 00000000111111110000000011111111
    int u4 = 0x0000FFFF;
    int x, y, z;
    x = n;
    y = (x >> 1) & u0;
    z = (x & u0) << 1;
    x = y | z;

    y = (x >> 2) & u1;
    z = (x & u1) << 2;
    x = y | z;

    y = (x >> 4) & u2;
    z = (x & u2) << 4;
    x = y | z;

    y = (x >> 8) & u3;
    z = (x & u3) << 8;
    x = y | z;

    y = (x >> 16) & u4;
    z = (x & u4) << 16;
    x = y | z;

    return x;
}

它可以反转比特（在32位机器上），但有一个问题，例如输入为10001111101，我想得到10111110001，但这种方法会反转整个字节，包括前导0。输出是10111110001000000000000000000000。是否有一种方法只反转实际数字？我不想将其转换为字符串并进行反转，然后再次转换。是否有任何纯数学方法或位操作方法？

此致，

最好的问候，

- Yongwei Xing

---

我了解您的方法：它无法编译，因为您在示例中使用了u4，但未对其进行定义。 - Ritsaert Hornstra

添加 int u4 = 0x0000FFFF; - user287792

这不是原因，我只是想念那个。 - Yongwei Xing

我正在尝试对一个字节进行位反转。然后使用大小为16的映射表，没有什么能比得上它的速度。 - Redu

Answer 1

使用类似的方法获取最高位数，并将结果位向右移动33-＃bits，就可以得到所需结果！

- Ritsaert Hornstra

Answer 2

一种简单的方法是不断右移直到最右边出现1：

if (x != 0) {
    while ((x & 1) == 0) {
        x >>= 1;
    }
}

注意：您应该将所有变量切换为unsigned int。如所写，每次右移都可能产生不必要的符号扩展。

- John Kugelman

---

你应该检查插入的值是否为零，因为你可能会陷入无限循环。 - Ritsaert Hornstra

要注意有符号右移运算符对符号位的影响，它是实现定义的。也许提问者最好将代码切换为使用无符号整数：没有理由用有符号整数，也不值得麻烦。 - Steve Jessop

Answer 3

尝试使用 Integer.reverse(int x);

- Rahul Dhupia

Answer 4

一种方法是找到数字n中的前导符号位数，将n左移该数字，然后通过上述算法运行它。

- user445161

---

这是错误的：1000（高位3）变为<< 3，因此为10000000，反过来是0x02000000，而不是1！ - Ritsaert Hornstra

@Ritsaert：1000有24个前导符号位，因此您需要将其向左移动24位，而不是3位。 - Chris Dodd

Answer 5

它假设所有32位都是有效的并将整个内容反转。你可以尝试通过找到最高位1来让它猜测有效位数，但这不一定准确，所以我建议你修改函数，使其接受第二个参数指示有效位数。然后在反转位之后，只需将它们向右移动。

- JC Ford