无符号整数的 C 位反转

Question

我正在使用位运算符将无符号整数转换为二进制，并且目前使用integer & 1来检查位是1还是0，并输出，然后右移1位以除以2。但是位以相反的顺序返回（颠倒），因此我想在开始之前反转整数的位顺序。

是否有一种简单的方法来实现这个目标？

示例： 例如，如果给我一个无符号整数10 = 1010

while (x not eq 0) 
  if (x & 1)
    output a '1'
  else 
    output a '0'
  right shift x by 1

这段代码返回了0101，但是这个结果是不正确的...因此我考虑在循环之前反转原始位的顺序，但我不确定如何实现？

- user1139103

---

您应该发布一些代码以使其更清晰（无恶意）。 - user973572

可能重复了 [C中比特反转的最佳算法（从MSB->LSB到LSB->MSB）] (https://dev59.com/vnRB5IYBdhLWcg3wAjXR) - Ciro Santilli OurBigBook.com

Answer 1

颠倒一个字中的各位比特位有些麻烦，直接按相反的顺序输出这些位更加容易。例如：

void write_u32(uint32_t x)
{
    int i;
    for (i = 0; i < 32; ++i)
        putchar((x & ((uint32_t) 1 << (31 - i)) ? '1' : '0');
}

这是反转位序的典型解决方案：

uint32_t reverse(uint32_t x)
{
    x = ((x >> 1) & 0x55555555u) | ((x & 0x55555555u) << 1);
    x = ((x >> 2) & 0x33333333u) | ((x & 0x33333333u) << 2);
    x = ((x >> 4) & 0x0f0f0f0fu) | ((x & 0x0f0f0f0fu) << 4);
    x = ((x >> 8) & 0x00ff00ffu) | ((x & 0x00ff00ffu) << 8);
    x = ((x >> 16) & 0xffffu) | ((x & 0xffffu) << 16);
    return x;
}

- Dietrich Epp

---

请您能否给我第二部分的进一步解释（或者给我一个短语，以便我可以在谷歌上搜索）。这对我来说毫无意义，我的位表示知识显然比我想象的还要差。提前致谢。 - Tomas Pruzina

@AoeAoe：这是一个位操作技巧。如果你想理解它的工作原理，我建议将数字用二进制写出来。每一行都会交换一半位数的位置，并且核心中的五行可以按任意顺序编写。 - Dietrich Epp

以下是翻译的内容： 这里是解释：让我们把块大小b中的所有位分成组，从b=1开始。现在交换每个相邻块。将块大小加倍并重复此过程。继续直到块大小为字长的一半。对于32位，这需要进行5个步骤。每个步骤都可以写成((x & mask) << b) | ((x & mask') << b)。因此，通过5条语句，我们可以反转32位整数。 - Shital Shah

Answer 2

你可以选择从左到右移位，即将最高有效位向最低有效位移动一个单位，例如：

unsigned n = 20543;
unsigned x = 1<<31;
while (x) {
    printf("%u ", (x&n)!=0);
    x = x>>1;
}

- iabdalkader

---

@SethCarnegie 不是x>>1，而是因为x=1<<31，所以我们从最高位到最低位或从左到右移动以颠倒位的顺序。 - iabdalkader

啊，我把“x”和“n”搞混了。 - Seth Carnegie

Answer 3

你可以从高位到低位循环遍历比特位。

#define N_BITS (sizeof(unsigned) * CHAR_BIT)
#define HI_BIT (1 << (N_BITS - 1))

for (int i = 0; i < N_BITS; i++) {
     printf("%d", !!(x & HI_BIT));
     x <<= 1;
}

在IT技术中，!!也可以写成!=0或者>> (N_BITS - 1)。

- Fred Foo

---

不是吗？!!(x) == x吗？双重否定抵消，==0将为真，即如果它为0，则为1，因此打印位翻转。 - iabdalkader

@mux：不，双重否定只有在0和1时才会被取消。你说的==0是对的，应该是!=0，抱歉。 - Fred Foo

哦，我现在明白了，类似于!(!(512)) = !(0) = 1，谢谢，我把它归咎于太多的离散 :) ... - iabdalkader

Answer 4

你可以像输出一样反转位，而是将它们存储在另一个整数中，然后再次执行：

for (i = 0; i < (sizeof(unsigned int) * CHAR_BIT); i++)
{
  new_int |= (original_int & 1);
  original_int = original_int >> 1;
  new_int = new_int << 1;
}

或者你可以做相反的，移位你的掩码：

unsigned int mask = 1 << ((sizeof(unsigned int) * CHAR_BIT) - 1);
while (mask > 0)
{
  bit = original_int & mask;
  mask = mask >> 1;
  printf("%d", (bit > 0));
}

如果你想要移除前导0，你可以等待1被打印出来，或者进行初步的遍历：

unsigned int mask = 1 << ((sizeof(unsigned int) * CHAR_BIT) - 1);
while ((mask > 0) && ((original_int & mask) == 0))
  mask = mask >> 1;
do
{
  bit = original_int & mask;
  mask = mask >> 1;
  printf("%d", (bit > 0));
} while (mask > 0);

这样做可以将掩码放在要打印的第一个1上，忽略前导0。

但是请记住：使用printf可以轻松地打印整数的二进制值。

- Eregrith

---

只需记得将 sizeof 乘以 8，你的第一个解决方案就没问题了。（第二个会溢出，但经过一些修正，它也可以工作） - asaelr

更好的做法是乘以 CHAR_BIT。 - Paul R

@user1139103 我在我的答案中添加了前导0的删除，改为使用do/while循环以保留最后一个0。你也可以在第一个while中使用while ((mask > 1) ...，并将第二个while保持为while (mask > 0)。 - Eregrith

原始整数 original_int & 掩码 mask 要么是 0，要么是一个大于等于 1 的数字，具体取决于位的位置，而不是 0/1 吗？ - iabdalkader

@Eregrith 我不确定为什么，但它对于奇数没有输出任何内容。 - user1139103

Answer 5

反转整数中的位的最佳方法是：

1. 它非常高效。
2. 它只运行到最左边的位为1时。

代码片段

int reverse ( unsigned int n )
{
    int x = 0;
    int mask = 1;
    while ( n > 0 )
    {
        x = x << 1;
        if ( mask & n )
            x = x | 1;
        n = n >> 1;
    }
    return x;
}

- DecPK

Answer 6

在现代处理器上，带有高速缓存的情况下，Dietrich Epp的第二个答案可能是最好的选择。然而，在典型的微控制器上，情况并非如此，以下方法不仅更快，而且更灵活、更紧凑（用C语言实现）：

// reverse a byte
uint8_t reverse_u8(uint8_t x)
{
   const unsigned char * rev = "\x0\x8\x4\xC\x2\xA\x6\xE\x1\x9\x5\xD\x3\xB\x7\xF";
   return rev[(x & 0xF0) >> 4] | (rev[x & 0x0F] << 4);
}

// reverse a word
uint16_t reverse_u16(uint16_t x)
{
   return reverse_u8(x >> 8) | (reverse_u8(x & 0xFF) << 8);
}

// reverse a long
uint32_t reverse_u32(uint32_t x)
{
   return reverse_u16(x >> 16) | (reverse_u16(x & 0xFFFF) << 16);
}

代码很容易翻译成Java、Go、Rust等语言。当然，如果你只需要打印数字，最好的方法是按相反的顺序打印（参见Dietrich Epp的答案）。

- user103185

Answer 7

您可以使用以下的 reverse 函数来反转一个 无符号32位整数 并返回：

unsigned int reverse(unsigned int A) {
    unsigned int B = 0;
    for(int i=0;i<32;i++){
        unsigned int j = pow(2,31-i);
        if((A & (1<<i)) == (1<<i)) B += j; 
    }
return B; 
}

记得包含数学库。愉快编程 :)

- Prateek Oraon

---

为避免 1 << 31 的未定义行为，您应该使用 if((A & (1U<<i)) == (1U<<i)) B += j;。此外，请使用 unsigned int j = 1U << (31 - i); 而不是浮点算术。 - chqrlie

Answer 8

我认为问题是在询问如何不以相反的顺序输出。

有趣的回答（递归）：

#include <stdio.h>

void print_bits_r(unsigned int x){
    if(x==0){
       printf("0");
       return;
    }
    unsigned int n=x>>1;
    if(n!=0){
       print_bits_r(n);
    }
    if(x&1){
        printf("1");
    }else{
        printf("0");
    }
}


void print_bits(unsigned int x){
    printf("%u=",x);
    print_bits_r(x);
    printf("\n");
}

int main(void) {
    print_bits(10u);//1010
    print_bits((1<<5)+(1<<4)+1);//110001
    print_bits(498598u);//1111001101110100110
    return 0;
}

预期输出：

10=1010
49=110001
498598=1111001101110100110

顺序版本（先挑选高位）：

#include <limits.h>//Defines CHAR_BIT
//....
void print_bits_r(unsigned int x){
    //unsigned int mask=(UINT_MAX>>1)+1u;//Also works...
    unsigned int mask=1u<<(CHAR_BIT*sizeof(unsigned int)-1u);
    int start=0;
    while(mask!=0){
        if((x&mask)!=0){
            printf("1");
            start=1;
        }else{
            if(start){
                printf("0");
            }
        }
        mask>>=1;
    }
    if(!start){
       printf("0");
    }    
}

- Persixty

Answer 9

似乎很愚蠢将整数值的位顺序反转，然后从低端拾取位，当保持不变并从高端拾取位时，它是微不足道的。

您想将整数转换为文本表示形式，在这种情况下是二进制。计算机经常将整数转换为文本，最常见的是十进制或十六进制。

一个简单的内置解决方案是：

printf('%b', 123);  // outputs 1111011

但这在C中并不是标准的。(参见是否有printf转换器以二进制格式打印？)

数字是从最高位(或位)开始写的，因此反复取最低有效位(或位)只完成了一半的工作。您需要收集这些数字并以相反的顺序组装或输出它们。

要将值123显示为10进制，您需要：

• 将123除以10，得到12余数3。
• 将12除以10，得到1余数2。
• 最后将1除以10，得到0余数1。(0是停止点。)
• 将余数(3、2、1)以相反的顺序显示，以显示"123"。

我们可以在123之前放任意数量的零，但这是不恰当的，因为它们没有贡献。更大的数字需要更长的字符串（“123”，“123000”，“123000000”）。采用这种方法，你不知道需要多少位数，直到计算出最高位数，因此在计算所有数字之前不能输出第一位数。

或者，你可以先计算最高位数。这看起来有点复杂。特别是在除了二进制以外的其他进制中。再次以123为例：

• 将123除以1000，余数为123。
• 将123除以100，余数为23。
• 将23除以10，余数为3。
• 最后，将3除以1，余数为0。（0是停止点。）
• 按照相同顺序显示商（0、1、2、3），跳过前导零，以显示“123”。

你可以按照计算顺序输出数字，但需要从足够大的除数开始。对于uint16，除数是10000；对于uint32，除数是1000000000。

要以二进制方式显示值123，使用第一种方法：

• 将123除以2，得到余数1。
• 将61除以2，得到余数1。
• 将30除以2，得到余数0。
• 将15除以2，得到余数1。
• 将7除以2，得到余数1。
• 将3除以2，得到余数1。
• 最后，将1除以2，得到余数1。（0是停止点。）
• 以相反的顺序显示余数（1、1、0、1、1、1、1），以显示“1111011”。

（通过右移1位来实现除以2。）

第二种方法按顺序产生数字（位）。

• 将123除以256，得到商0余数123。
• 将123除以128，得到商0余数123。
• 将123除以64，得到商1余数59。
• 将59除以32，得到商1余数27。
• 将27除以16，得到商1余数11。
• 将11除以8，得到商1余数3。
• 将3除以4，得到商0余数3。
• 将2除以2，得到商1余数1。
• 最后，将1除以1，得到商1余数0（0是终止点）。
• 按照相同的顺序显示商（0,0,1,1,1,1,0,1,1），跳过首位的零，以显示"1111011"。

（可以使用比较实现这些除法。比较值可以通过除以2生成，也就是右移1个比特。）

任何一种解决方案都可能需要进行修改，以防止数值0显示为空（即“”或空字符串），而不是“0”。

- user751630

Answer 10

unsigned int rev_bits(unsigned int input)
{
    unsigned int output = 0;
    unsigned int n = sizeof(input) << 3;
    unsigned int i = 0;

    for (i = 0; i < n; i++)
        if ((input >> i) & 0x1)
            output |=  (0x1 << (n - 1 - i));

    return output;
}

- user1596193

---

0x1 << 31 has undefined behavior. You should write output |= 1U << (n - 1 - i); - chqrlie