32位字的镜像位

Question

你会怎么用C做的？(例如:如果我们必须镜像8位,则10110001变为10001101).某些处理器上是否有任何可以简化此任务的说明？

Answer 1

它实际上称为"位反转",通常在FFT加扰中完成.O(log N)方式是(最多32位):

uint32_t reverse(uint32_t x, int bits)
{
    x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1); // Swap _<>_
    x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2); // Swap __<>__
    x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4); // Swap ____<>____
    x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8); // Swap ...
    x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16); // Swap ...
    return x >> (32 - bits);
}

也许这个小的"可视化"有助于:
前3个任务的一个uint8_t例子,例如:

b7 b6 b5 b4  b3 b2 b1 b0
-> <- -> <-  -> <- -> <-
----> <----  ----> <----
---------->  <----------

好吧,如果我们正在做ASCII艺术,这是我的:

7 6 5 4 3 2 1 0
 X   X   X   X 
6 7 4 5 2 3 0 1
 \ X /   \ X /
  X X     X X
 / X \   / X \
4 5 6 7 0 1 2 3
 \ \ \ X / / /
  \ \ X X / /
   \ X X X /
    X X X X
   / X X X \
  / / X X \ \
 / / / X \ \ \
0 1 2 3 4 5 6 7

它有点像FFT蝴蝶.这就是它弹出FFT的原因.

Answer 2

天真的/缓慢/简单的方法是提取输入的低位并将其转移到另一个累积返回值的变量中。

#include <stdint.h>

uint32_t mirror_u32(uint32_t input) {
    uint32_t returnval = 0;
    for (int i = 0; i < 32; ++i) {
        int bit = input & 0x01;
        returnval <<= 1;
        returnval += bit;    // Shift the isolated bit into returnval
        input >>= 1;
    }
    return returnval;
}

对于其他类型，存储位数为sizeof(input) * CHAR_BIT，但这包括不属于该值的潜在填充位。固定宽度类型在这里是个好主意。

+=而 of使|=gcc 在 x86 上更有效地编译它（使用 x86 的移位加法指令 LEA）。当然，还有更快的位反转方法；请参阅其他答案。这个循环适用于小代码大小（没有大掩码），但在其他方面几乎没有优势。

不幸的是，编译器无法将此循环识别为位反转并将其优化为 ARMrbit或其他。（在 Godbolt 编译器浏览器上查看）