c++ - 以明显的方式反转位

Question

我看到了链接http://pvtridvs.net/pool/bithacks.html#BitReverseObvious并在此处发布代码:

unsigned int v;         // reverse the bits in this
unsigned int t = v;     // t will have the reversed bits of v
int i;

for (i = sizeof(v) * 8 - 1; i; i--)
{
  t <<= 1;
  v >>= 1;
  t |= v & 1;
}

有人能解释一下为什么这个看似简单的算法有效吗？我在纸上测试了一些最简单的例子，比如 4 位 0011 等，它可以工作，但我只是不明白为什么这 3 行移位和按位操作可以实现它。

Answer 1

它将位从 v 的低位“移出”并“移入”到 t 的低位。将变量视为位堆栈。您正在从 v 中弹出位并将它们插入 t。从一个列表弹出并插入另一个最初为空的列表是反转任何列表的一种简单方法。初始化只是将最低阶位初始“推”到结果上。这个技巧节省了一只小狗并插入(即右移和左移)。例如。对于一个字节，只需要再进行 7 次弹出推送。