在C语言中反转位模式

Question

我正在将一个数字转换为二进制，并需要使用putchar输出每个数字。

问题是我得到的顺序是相反的。

有没有办法在对其进行操作之前反转数字的位模式？

例如，int n具有特定的位模式 - 如何反转这个位模式？

- leo

---

展示给我们一些代码，至少是伪代码。帮你完成作业并不适合我们。 - dirkgently

这个回答解决了你的问题吗？C语言中高效的位反转算法（从MSB->LSB到LSB->MSB）。 - phuclv

Answer 1

有很多方法可以做到这一点，其中一些非常快速。我不得不查找资料。

反转字节中的位

b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16; 

在5 * lg(N)操作中并行反转N位数量：

unsigned int v; // 32-bit word to reverse bit order

// swap odd and even bits
v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
// swap consecutive pairs
v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
// swap nibbles ... 
v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
// swap bytes
v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
// swap 2-byte long pairs
v = ( v >> 16             ) | ( v               << 16);

使用查找表反转字中的比特位

static const unsigned char BitReverseTable256[256] = 
{
#   define R2(n)     n,     n + 2*64,     n + 1*64,     n + 3*64
#   define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16)
#   define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 )
    R6(0), R6(2), R6(1), R6(3)
};

unsigned int v; // reverse 32-bit value, 8 bits at time
unsigned int c; // c will get v reversed

// Option 1:
c = (BitReverseTable256[v & 0xff] << 24) | 
    (BitReverseTable256[(v >> 8) & 0xff] << 16) | 
    (BitReverseTable256[(v >> 16) & 0xff] << 8) |
    (BitReverseTable256[(v >> 24) & 0xff]);

// Option 2:
unsigned char * p = (unsigned char *) &v;
unsigned char * q = (unsigned char *) &c;
q[3] = BitReverseTable256[p[0]]; 
q[2] = BitReverseTable256[p[1]]; 
q[1] = BitReverseTable256[p[2]]; 
q[0] = BitReverseTable256[p[3]];

请查看http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel以获取更多信息和参考资料。

- Adriaan

---

构建查找表的好方法 - max taldykin

Answer 2

将输入的位弹出并推到输出中。乘以2和除以2都是推和弹出操作。伪代码如下：

reverse_bits(x) {
    total = 0
    repeat n times {
       total = total * 2
       total += x % 2 // modulo operation
       x = x / 2
    }
    return total
}

如果你还没有见过取模运算符，请参考维基百科的modulo operation页面。

进一步的要点：

• 如果将2改为4或10，会发生什么？
• 这会影响n的值吗？n是什么？
• 如何使用位运算符（<<、>>、&）来代替除法和取模？这会使它更快吗？
• 我们能使用其他算法来使其更快吗？查找表能帮助吗？

- Mark Byers

---

+1 - 这正是我想说但无法快速简洁地打出来的。 - Grhm

如果速度太慢，x % 2 等价于 x & 1。 - Dave Jarvis

据我所知，这些优化在现今很少有帮助；编译器已经足够聪明，可以自行解决。相反地，对于现代机器来说，x ^= x; 可能实际上会更慢，因为一些芯片设计者（例如 Intel）习惯于将 x = 0 的汇编指令重新排列到比对应的异或操作更高的位置，以加快速度。 - dirkgently

你可能想用汇编语言编写一些代码。许多处理器都有好的、专门的位指令。其中一个有用的指令是旋转进位和旋转带进位。这使得进位位成为一个临时存储器。 - Thomas Matthews

@Adriaan：请看我的代码下面的注释。优化速度留作家庭作业练习。 ;) - Mark Byers

Answer 3

让我猜猜：您有一个循环，打印第0位（n&1），然后将数字向右移。相反，编写一个循环，打印第31位（n&0x80000000）并将数字向左移。在执行该循环之前，执行另一个循环，将数字左移，直到第31位为1；除非这样做，否则您将得到前导零。

反转也是可能的。像这样：

unsigned int n = 12345; //Source
unsigned int m = 0; //Destination
int i;
for(i=0;i<32;i++)
{
    m |= n&1;
    m <<= 1;
    n >>= 1;
}

- Seva Alekseyev

Answer 4

我知道：那不完全是C语言，但我认为这是一个有趣的答案：

int reverse(int i) {
  int output;
  __asm__(
     "nextbit:"
        "rcll $1, %%eax;"
        "rcrl $1, %%ebx;"
        "loop nextbit;"
        : "=b" (output)
        : "a" (i), "c" (sizeof(i)*8) );
  return output;
}

rcl指令将移位后的位放入进位标志中，然后rcr以相反的顺序将该位恢复到另一个寄存器中。

- olivecoder

---

这意味着x86，但这并不一定是真的。即使在x86上，它也比许多其他解决方案效率低下。 - phuclv

Answer 5

这里是我用来反转字节和四元组中的位的函数。

inline unsigned char reverse(unsigned char b) {
    return (b&1 << 7)
         | (b&2 << 5)
         | (b&4 << 3)
         | (b&8 << 1)
         | (b&0x10 >> 1)
         | (b&0x20 >> 3)
         | (b&0x40 >> 5)
         | (b&0x80 >> 7);
}

inline unsigned long wreverse(unsigned long w) {
    return ( ( w     &0xFF) << 24)
         | ( ((w>>8) &0xFF) << 16)
         | ( ((w>>16)&0xFF) << 8)
         | ( ((w>>24)&0xFF) );
}

- luser droog

---

这种类型的三元评估可能会非常缓慢，因此在高性能场景中应该避免使用。 - Richard J. Ross III

我想你是对的。我将使用移位操作来替换它。那个“最优”的答案让我感到害怕。 - luser droog

Answer 6

我猜你有一个整数，尝试将其转换为二进制？

"答案"是ABCDEFG，但你的"答案"是GFEDCBA？

如果是这样，我建议你仔细检查正在使用的计算机的字节序和"答案"所来自的计算机的字节序。

- Daniel