0

我想反转二进制

unsigned short gf_t  = 44 // = 00101100

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

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

4

4 回答 4

6

如有疑问，请参阅Bit Twiddling Hacks 页面。事实上，在那里你可以找到一个非常简单的算法来做你想做的事情......

以明显的方式反转位

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

2004 年 10 月 15 日，Michael Hoisie 指出了原始版本中的一个错误。Randal E. Bryant 在 2005 年 5 月 3 日建议删除一个额外的操作。Behdad Esfabod 建议在 2005 年 5 月 18 日删除一个循环的迭代。然后，在 2007 年 2 月 6 日，Liyong Zhou 提出了一个更好的循环版本而 v 不是 0，因此它不会迭代所有位，而是提前停止。

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

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

请注意，如果sizeof(unsigned short) * CHAR_BITis 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));
}
于 2012-09-10T19:07:21.330 回答
5

您可以这样做（v是一个 16 位数字）：

v = ((v >> 1) & 0x5555) | ((v & 0x5555) << 1);
v = ((v >> 2) & 0x3333) | ((v & 0x3333) << 2);
v = ((v >> 4) & 0x0F0F) | ((v & 0x0F0F) << 4);
v = ((v >> 8) & 0x00FF) | ((v & 0x00FF) << 8);
  • 第一行交换奇偶位
  • 第二行交换连续对
  • 第三行交换四位组
  • 最后一行交换两个字节

你可以在这里找到更多这样的技巧。这是带有此代码片段的 ideone 的链接。

如果您试图理解这一点，请编写示例中使用的“幻数”的二进制表示：

  • 0x5555是0101010101010101
  • 0x3333是0011001100110011
  • 0x0F0F是0000111100001111
  • 0x00FF是0000000011111111

该&操作清除了“不需要的”位；移位将所需部分重新定位在掩蔽操作打开的“零间隙”上，最后|重新组合这两个部分。

于 2012-09-10T19:09:20.517 回答
1

通常你and输入 1 来获得它的 LSB。Or结果。将结果左移一点，输入右移一点。重复总共 32 次迭代。

于 2012-09-10T19:05:46.743 回答
0

二进制是 0000000000101100 - 有 16 位短。

// 包括转到这里

int main() {

无符号短 gf_t = 44; cout << 十六进制 << gf_t << endl;

unsigned short gf_r = 0;
for ( int iter = 0; iter < sizeof(short) * 8; ++iter )
{
unsigned short tmp = gf_t;
tmp = tmp & 1;
gf_r = (gf_r << 1 ) | tmp;
gf_t = gf_t >> 1;
}

cout << hex << gf_r << endl;

}

于 2012-09-10T19:29:43.767 回答