将 32 位整数移动超过 32 次时出现意外结果

Getting unexpected results when shifting a 32-bit integer more than 32 times

我想澄清为什么某些位移会做一些我不期望的事情。

我开发了一个函数 setBitsVersion1,它使用常规 int 基本类型将 32 位整数数组中的位设置为 1。所以这意味着位位置 [0, 31] 用于数组中的第一个整数,位位置 [32, 63] 用于数组中的第二个整数等。例如,位置 10 是第一个整数的位置 10,但位置 35 实际上是第二个整数中的位置 3。因此,如果 bitPosition 为 35,则 line 4 将变为 a[1] = a[1] | one << 3,从而将位设置为位置 3。此函数的行为符合预期,您可以在打印整数时在输出中看到,打印的整数是正确的,因为二进制 2^3 位置的位已设置。

然而,下一部分是我感到困惑的地方。我编写了第二个实现 setBitsVersion2,它删除了行 line 3,因此原始的 bitPosition 永远不会被修改为特定索引处的正确位位置。因此,再次使用 35,该行将变为 a[1] = a[1] | one << 35。据我了解,左移 32 位或更多位是未定义的行为。我不太确定我希望打印什么,但我绝对不会期望它将位设置在位置 3 因为 1 << 35 不是 1 << 3 并且移动 35 次是未定义的行为.也许我会期望整数为零,因为过去当我将整数移动 32 次或更多次时,它最终会变成 0。无论如何,我只是对为什么要这样做感到困惑 1 << 35产生相同的结果 1 << 3 因为我预计它不会工作并希望得到解释。

如果我使用的 machine/compiler 类型相关,那么我在使用 Microsoft Visual Studio 2019 的 Windows 计算机上。不过,我也对其进行了测试在 Linux 上使用 gcc 得到了相同的结果。

代码

#include <stdio.h>

void setBitVersion1(int* a, int bitPosition);
void setBitVersion2(int* a, int bitPosition);
void printArray(int* a, int size);

int main(int argc, char* argv[]) {
    printf("Correct implementation - setBitsVersion1 - results are correct and what is expected\n");
    int a1[5] = { 0 };
    int a1Size = sizeof(a1) / sizeof(*a1);
    setBitVersion1(a1, 35);
    setBitVersion2(a1, 67);
    printArray(a1, a1Size);
    printf("\n\n");

    printf("Incorrect version - setBitsVersion2 - still produces the same results?\n");
    int a2[5] = { 0 };
    int a2Size = sizeof(a2) / sizeof(*a2);
    setBitVersion1(a2, 35);
    setBitVersion2(a2, 67);
    printArray(a2, a2Size);

    return 0;
}

void setBitVersion1(int* a, int bitPosition) {
    int one = 1;                                // line 1
    int index = bitPosition / 32;               // line 2
    bitPosition = bitPosition % 32;             // line 3
    a[index] = a[index] | one << bitPosition;   // line 4
}

void setBitVersion2(int* a, int bitPosition) {
    int one = 1;
    int index = bitPosition / 32;
    a[index] = a[index] | one << bitPosition;
}

void printArray(int* a, int size) {
    for (int i = 0; i < size; i++)
        printf("%d\n", a[i]);
}

输出

Correct implementation - setBitsVersion1 - results are correct and what is expected
0
8
8
0
0


Incorrect version - setBitsVersion2 - still produces the same results?????
0
8
8
0
0

1 << 35可以产生1 << 3,因为移位32位值的机器指令在移位量字段中只有5位。当使用 35(二进制 100011)时,处理器只看到五位(00011),即 3,因此它移动 3 位。当然,其他行为也是可能的;编译器可能会在编译时使用更复杂的软件自行计算移位,或者可能会使用具有不同行为的不同指令。

It's my understanding that left shifting 32 bits or more is undefined behavior. I'm not exactly sure what I would expect to print, but I definitely wouldn't [have] expected it to set the bit at position 3 because 1 << 35 is not 1 << 3 and shifting by 35 times is undefined behavior.

当然,您“不会期望”它会将位设置在位置 3 或做任何其他特别的事情,因为 C 标准不会给您任何期望。要有期望,您必须有一些期望的理由,例如 C 标准中关于它应该如何表现的声明或熟悉编译器的编写方式或处理器指令的知识。当你没有理由时,要警惕期待某些事情发生——甚至期待某些事情不会发生。

more is undefined behavior. I'm not exactly sure what I would expect to print, but I definitely wouldn't of expected it to set the bit at position 3 because 1 << 35 is not 1 << 3 and shifting by 35 times is undefined behavior.

这正是您处理未定义行为的方式。不错

why doing 1 << 35 produces the same results 1 << 3 since I would've expected it not to work

未定义的行为意味着您没有期望,而不是它“不会工作”。它可能以不可预测的方式“工作”,它可能崩溃,它可能产生 nasal demons。没人知道。

您可以检查您的特定编译器程序集输出以了解您使用的特定选项,并且您可以发现,例如使用godbolt,您的编译器在x86_64 恰好使用 sal edx, cl 汇编指令进行左移。请记住,没有任何形式的保证,并且在未定义行为的情况下,任何事情 都可能发生。正如您所指出的-您不能“期望”。

来自 https://c9x.me/x86/html/file_module_x86_id_285.html 我可以阅读:

The count is masked to 5 bits, which limits the count range to 0 to 31

因此,即使一个大于 31 的值存储在 CL 寄存器中,它仍然被标记为 5 位 在这个特定的体系结构上

请注意,编译器,例如不同的编译器选项,尤其是 undef 不同的优化级别,或者不同版本的编译器 可能 生成不同的指令来执行转移。


你应该使用 uint32_t.

您正在使用 int 类型来表示任何类型的位值模式。你的 setBitVersion1 有未定义的行为,标准说 https://port70.net/~nsz/c/c11/n1570.html#6.5.7p4 :

The result of E1 << E2 is .... If E1 has a signed type and nonnegative value, and E1 x 2^E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

one << bitPositionbitPosition = 31 导致... 2^31,这大于 int 可以表示 INT_MAX = 2^31 - 1。这是未定义的行为 - 您的代码对于 bitPosition 小于或等于 30.

实际上是安全的

intunsiggned int 类型有 至少 16 位。他们在一些用于小型微控制器的编译器上有 16 位。

使用 intX_t 类型来表示特定数量的类型。使用 << >>.

的无符号类型