c - 使用按位运算符反转无符号短 vector

Question

我要反转二进制

unsigned short gf_t  = 44 // = 00101100

C 语言中的 00110100。我将如何使用按位运算符来做到这一点？

pdta:我的电脑有 32 位模式。

Answer 1

如有疑问，请参阅 Bit Twiddling Hacks page .事实上，您可以在那里找到一个非常简单的算法来完成您想要的...

Reverse bits the obvious way

unsigned int v;     // input bits to be reversed
unsigned int r = v; // r will be reversed bits of v; first get LSB of v
int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end

for (v >>= 1; v; v >>= 1)
{   
  r <<= 1;
  r |= v & 1;
  s--;
}
r <<= s; // shift when v's highest bits are zero 

On October 15, 2004, Michael Hoisie pointed out a bug in the original version. Randal E. Bryant suggested removing an extra operation on May 3, 2005. Behdad Esfabod suggested a slight change that eliminated one iteration of the loop on May 18, 2005. Then, on February 6, 2007, Liyong Zhou suggested a better version that loops while v is not 0, so rather than iterating over all bits it stops early.

但是，那里也记录了几种绝妙的方法。您可以研究这些并尝试理解它们以进行学习:-)例如，这是一种特别有趣的形式...

Reverse an N-bit quantity in parallel in 5 * lg(N) operations:

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);

请注意，如果 sizeof(unsigned short) * CHAR_BIT 是 16，则适当的用法只需要前 4 次换位 -- 如下所示:

unsigned short v;

// swap odd and even bits
v = ((v >> 1) & 0x5555) | ((v & 0x5555) << 1);
// swap consecutive pairs
v = ((v >> 2) & 0x3333) | ((v & 0x3333) << 2);
// swap nibbles ... 
v = ((v >> 4) & 0x0F0F) | ((v & 0x0F0F) << 4);
// swap bytes
v = ((v >> 8) & 0x00FF) | ((v & 0x00FF) << 8);

话虽这么说，为什么不直接使用 uint16_t(如果可用)？

这是工作示例(参见 ideone ):

#include <stdio.h>
#include <assert.h>
#include <stdint.h>

inline uint16_t reverse(uint16_t v) {
  v = ((v >> 1) & 0x5555) | ((v & 0x5555) << 1); /* swap odd/even bits */
  v = ((v >> 2) & 0x3333) | ((v & 0x3333) << 2); /* swap bit pairs */
  v = ((v >> 4) & 0x0F0F) | ((v & 0x0F0F) << 4); /* swap nibbles */
  v = ((v >> 8) & 0x00FF) | ((v & 0x00FF) << 8); /* swap bytes */
  return v;
}

main() {
  uint16_t gf_t = 44;
  printf("%hu\n", reverse(gf_t));
}