使用位黑客反转二进制数

Question

谁能解释一下二进制数是如何反转的。

unsigned rev = 0;
unsigned k = n;

while (k)
{
// add rightmost bit to rev 
    rev = (rev << 1) | (k & 1);
    k = k >> 1;     // drop last bit
            cout<<"k val is "<<bitset<8>(k)<<endl;
    cout<<"rev val is "<<{bitset<8>(rev)<<endl;
}

如果 n=9 则输出

k 值为 00000100
rev val 是 00000001
k 值是 00000010
rev val 是 00000010
k 值是 00000001
转速值为 00000100
k 值是 00000000
rev val 是 00001001
9 是回文

我指的是这里的问题 2：http://www.techiedelight.com/bit-hacks-part-6-random-problems/

据我所知，如果“|”为真，则只执行第一个表达式条件语句。因此，此处 rev<<1 仅在首次执行循环时为 false，而在 rest 时不为 false。因此，对于最后一个条件，rev 最终如何得到 1，因为 (k&1) 不会被执行。只有左移会被执行吗？

Answer 1

As far as I know, only first expression is executed if it is true for "|" condition statement.

的|运算符是按位或：它的值是对其两个操作数的位模式的或运算。它总是评估两个操作数，因为它需要它们的完整值。示例：3 | 5 等于 7。

||是一个逻辑或：如果任一操作数（作为一个完整的值）为真，则为真。如果第一个操作数为真，它不会评估第二个操作数。

代码正在使用 |逐位或一次建立一个答案。

Answer 2

变量rev用0初始化，它将包含结果。 while 循环迭代，而作为输入的 k 有任何设置位。循环体的第一条语句屏蔽掉 k 的最后一位并将其复制 rev，在该过程中（通过移位运算符）将其向左移动一位。在循环迭代中，输入和输出都被移位——输入向右移位，输出向左移位。

Answer 3

一个可能有用的可视化是堆栈：假设您的数字 n 由一堆二进制数字表示，最低有效数字位于堆栈的顶部。

一种常见的位反转算法然后迭代地从 n 堆栈中逐个弹出数字并将它们堆叠在另一个堆栈中（在您的情况下代表 rev）。

k = k >> 1; 从堆栈中弹出一个二进制数字 n （在您的代码中重命名为 k）
rev = (rev << 1) | (k & 1); 将二进制数字堆叠在 k 堆栈的顶部。

在代码中，pop/stack 操作被反转以避免临时操作。

最后，只要n栈中还有数字，就应该重复pop/stack这个操作。这是因为 while 条件只有 k，它测试 k 是否为 0（没有数字剩余）。

PS：你有一些低级算法可以在 Bit Twiddling Hacks website 上执行位反转。这些算法以性能为目标，因此可能不容易理解。

使用位黑客反转二进制数

Reversal of a binary number using bit hacks

c++

bit