通过负数进行位移以翻转数字中的位

Question

按负数位移位是否有效？例如，如果我有以下代码：

#include <stdint.h>
uint32_t reverse_bits (uint32_t n)
{
    uint32_t result = 0;    
    for (int i = 0; i < 32; i++) 
    {
        uint32_t bit = n & (1 << i);
        bit <<= 31 - i * 2;
        result |= bit;
    }
    return result;
}

这是我可以期望在所有架构上工作的东西吗（特别是，当shift_amount < 0为真时，表达式x << shift_amt的结果等同于x >> -shift_amt）？

注意：这不是关于在负数上执行位移的行为的问题（即-1 << 1）。

以下是完整的测试程序：

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
uint32_t reverse_bits (uint32_t n)
{
    uint32_t result = 0;
    for (int i = 0; i < 32; i++)
    {
        uint32_t bit = n & (1 << i);
        bit <<= 31 - i * 2;
        result |= bit;
    }
    return result;
}
void print_bits (uint32_t n)
{
    for (int i = 0; i < 32; i++)
        putchar(n & (1 << i) ? '1' : '0');
    putchar('\n');
}
int main ()
{
    for (int i = 0; i < 5; i++)
    {
        uint32_t x = rand();
        x |= rand() << 16;
        print_bits(x);
        print_bits(reverse_bits(x));
        putchar('\n');
    }
}

- rsethc

---

您假定“unsigned long”为32位宽。 - wildplasser

是的，我会编辑示例代码，明确表示32位（或更宽）无符号整数类型。 - rsethc

好奇 - 你的编译器警告是什么？warning: left shift count is negative [-Wshift-count-negative]（当我使用<<= -1直接输入负数时）。 - Michael Dorgan

从实际测试中，我发现它绝对不能按预期工作，所以我想这就是关于X64的答案。 - rsethc

@rsethc：这是UB，做这个有什么意义呢？如果今天它能正常工作，gcc在以后的版本中很容易改变编译方式，如果假设计数始终为正数，则可以获得更多的优化可能性。只需使用if(shift < 0) x>>=-shift;，让gcc决定是否可以利用一些特定于架构的技巧来避免检查即可。顺便说一句，可能有更好的位反转算法。 - vgru

Answer 1

C标准声明，通过负数进行位移是明确未定义的行为，在§ 6.5.7段落3：中有规定：

如果右操作数的值为负数或大于或等于升级左操作数的宽度，则行为未定义。

强调为个人添加。

- Govind Parmar

---

我想这就是C标准中最清晰的描述了，尽管它是“未定义”的，但我想知道，如果给定一个特定的目标架构（即你知道你将要使用的是X86-64），编译器生成的实际移位指令是否会按照实际机器规格的意图执行。（即，虽然C将此行为留空为未定义，但X64或ARM是否具有更具体的行为定义？） - rsethc

如果它是未定义行为（UB），你不能依赖任何东西，即使它似乎能够工作。编译器的下一个版本可以随意更改它，那么你的代码中就会有一个非常难以找到的错误。 - Michael Dorgan

很容易检查是否为负数，如果需要的话，将其转换为正数方向。 - Michael Dorgan

...并且明确禁止按操作数的位宽进行超出位移。 - wildplasser

我希望负操作数会导致向后移位的原因是，这样我就不必根据操作数的符号（以及否定）来进行左移还是右移的分支。dbush的解决方案达到了这个目标，因为它仍然能够避免在循环内部分支。 - rsethc

@rsethc: 不，硬件中的移位指令通常不考虑有符号操作数。如果在汇编语言中向移位指令传递负值，则典型的行为是仅使用32位操作数的低五位。因此，只有0到31位的移位是可能的；负数移位是不可能的。 - Eric Postpischil

Answer 2

如前所述，将数值左移一个负值会触发未定义行为，根据C标准的6.5.7p3节规定。不要试图猜测何时可以使用负移位，改变你的代码使其不需要这样做。

在屏蔽掉所需位后，将其向右移回到第0位，然后将其移动到所需位置。此外，请确保将常量1更改为1ul，以避免将有符号值移入符号位或超出int的宽度。还请注意使用sizeof来避免硬编码魔术数字（例如32）。

unsigned long reverse_bits (unsigned long n)
{
    unsigned long result = 0;
    for (int i = 0; i < sizeof(unsigned long) * CHAR_BIT; i++)
    {
        unsigned long bit = ((n & (1ul << i)) >> i);
        unsigned long shift = (sizeof(unsigned long) * CHAR_BIT) - i - 1;
        result |= bit << shift;
    }
    return result;
}

- dbush

---

将值向个位移动确实是更为健壮的解决方法。然而，至于使用 sizeof，则是一种巧妙的方法，但通常我只想忽略类型长度中多余的字节，因为所有逻辑都基于 32 位宽度。 - rsethc

@rsethc，在[e-mail]上有一些非常出色的bitrev示例。 - wildplasser

还有一件我不太明白的事情是为什么1ul比1更好：因为它是正数，所以1ul和1除了可能具有不同的宽度（如果sizeof(long) != sizeof(int)）之外是等效的，尽管(int)1的宽度肯定足以解释任何有效的移位量。 - rsethc

哦，被移位的值的整数提升？ - rsethc

如果一个值的类型是有符号的，将一个位移动到符号位是未定义的行为，特别是当int为32位或更少时，1<<31。通过使用UL后缀，它强制该值成为unsigned long，以便我们不会将其移位到符号位。 - dbush