这个反转比特顺序的函数是怎么回事？

Question

我很惭愧地承认，我对位和位操作的了解不够深入。本周末，我尝试通过编写一些“反转位顺序”和“计算ON位数”的函数来解决这个问题。我从这里中借鉴了一个例子，但当我按照下面的实现时，我发现我必须在循环时使用< 29。如果我使用< 32（就像在例子中），那么当我尝试打印整数（使用我编写的printBits函数）时，我似乎会丢失前三位。这对我来说毫无意义，有人能帮帮我吗？

感谢大家的帮助，我已经添加了注释以显示我所做的更改。

int reverse(int n)
{
    int r = 0;
    int i = 0;
    for(i = 0; i < 29; i++) //Should be i < 32
    {
        r = (r << 1) + (n & 1); //| instead of + to make it obvious I'm handling bits
        n >>=1;
    }

    return r;
}

这是我的printBits函数：

void printBits(int n)
{
    int mask = 0X10000000; //unsigned int mask = 0X80000000;
    while (mask)
    {
        if (mask & n)
        {
            printf("1");
        }
        else
        {
            printf("0");
        }
        mask >>= 1;
    }
    printf("\n");
}

还有一个可用的反转函数

int reverse2(int n)
{
    int r = n;
    int s = sizeof(n) * 7; // int s = (sizeof(n) * 8) -1

    for (n >>= 1; n; n >>=1)
    {
        r <<=1;
        r |= n & 1;
        s--;


    r <<= s;
    return r;
}

- MattyW

---

请记住，您的循环是从零开始的。因此32应该从0到31... - Tony The Lion

你能否发一下你的PrintBits函数，以防这也有问题？这可能会有所帮助。 :-) - Jaxidian

另外，跟进Tony的评论，这是一个整数，即带符号的整数，所以你会因为存储符号（+/-）而丢失一位。因此，现在循环是从0到30。也许你还会失去一次必要的迭代，因为对于n位，你需要循环n-1次。想想看——要翻转2位，你需要进行多少次移位？3位呢？等等… - Jaxidian

娱乐一下：asm("bswap %0" : "=r" (n) : "0" (n)); - evilpie

@evilpie 如果您在谈论x86指令，那么这并不会将比特位反转。 - Pascal Cuoq

Answer 1

int mask = 0X10000000;

在第28位放置1，你需要0X80000000。

- Potatoswatter

Answer 2

Print Bits有误，应该是0x80000000而不是0x10000000。

>>> bin (0x80000000)  
'0b10000000000000000000000000000000'  
>>> bin (0x10000000)  
'0b10000000000000000000000000000'

看到0x1...没有设置最高位。

- evilpie

Answer 3

您拥有:

int mask = 0x10000000;

这里有两个问题。首先，您没有设置高位，即使您设置了高位，它也（很可能）不起作用，因为编译器会在有符号的int上使用算术移位。

您需要更改掩码为：

unsigned int mask = 0x80000000;

对于算术右移，将0x80000000向右移位永远不会变成零，因为符号位会神奇地扩展到其他位。有关算术移位的更多详细信息，请参见此处。

- clstrfsck

Answer 4

使用位或符号|代替+。并且应该使用< 32。

- sblom

---

在这里，“+”和“|”将产生相同的结果。 - interjay

+ 或 | 在这里没有区别，而且 + 可能更清晰，那么为什么要使用 |？ - Chris Dodd

@Chris Dodd：使用|符号更清晰。你在处理位而不是算术运算，因此应该使用专门用于位操作的运算符。 - Ponkadoodle

你应该使用 | 强调你正在执行位运算。 - Dale Hagglund

我仍然认为+更清晰，因为你只是在添加一个单独的位，而不是对整个字进行按位操作。 - Chris Dodd

Answer 5

按照现有的写法，这将把n的低29位反转到r中。n的前三位将保留在n中（向下移动29位）而不返回。

如果您看到其他内容，我会怀疑您的printBits函数存在问题。

编辑

您的printBits函数打印n的低29位，所以一切都说得通。

- Chris Dodd