为什么这个 C 算术移位实现不起作用？

Question

我正在尝试编写一个 C 函数，它总是使用按位运算符找到无符号整数参数的算术右移。我设法编写了一个函数，它总是使用按位运算符找到有符号整数的逻辑右移，但同样的想法似乎并不适用于找到算术移位。

这是我现在的函数：

unsigned arith(unsigned x, int k) {
    unsigned x_arith = (int) x >> k;

    x_arith = x_arith | ((-1<<(sizeof(x_arith)*8)-k)) & ~(-1<<(sizeof(x_arith)*8));
    return x_arith;
}

解释：

(-1 << (sizeof(x_arith)*8-k))

创建一个全 1 的二进制文件，然后移动这些二进制文件，使第一个 1 与 x_arth 中最左边的 1 对齐。

& ~(-1 << (sizeof(x_arith)*8))

创建一个全 1 的二进制并将其移位，使第一个与 x_arth 中最左边的位对齐，然后翻转它，然后仅保留与上面的二进制相同的那些位。

这整个过程据说会创建一个掩码，其中 x_arith 需要有 1。最后，我 | （或）原始 x_arith 与此掩码得到我需要进行移位运算的 1 和 return 结果。

然而，结果仍然是一个合乎逻辑的转变。我尝试更改上面代码中的许多内容，但对我得到的奇怪数字感到非常沮丧。我做错了什么？

更新：上面发布的函数确实找到了算术移位。问题是我用 4 和 k=1 测试它，期望结果是 6，结果是 而不是 算术移位的工作原理。这是该函数的一个更好看的版本以供将来参考：

unsigned arith_shift(unsigned x, int k) {

    unsigned x_arith = (int) x >> k;

    int bits = sizeof(int) * 8;

    unsigned mask = k? ((~0 << (bits-k)) & ~(~0 << bits)): 0;

    return x_arith | mask;

}

请注意，对于全 1 的二进制数，您可以同时使用 -1 和 ~0。然而，这个函数可能在不同的机器上表现不同，因为左移 -1 的行为是未定义的（见 e0k 的回答）。

Answer 1

来自 C99 6.5.7 Bitwise shift operators 第 4 段：（强调我的）

The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has an unsigned type, the value of the result is E1 x 2^E2 , reduced modulo one more than the maximum value representable in the result type. 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.

您正在尝试使用 -1<<(sizeof(x_arith)*8) 而您的 E1 是 -1:

这不是 "a signed type and nonnegative value"（-1 是有符号负数）。
"and E1 x 2^E2 is representable" 子句仅在 "signed type and nonnegative value" 为真时适用。（有关更多讨论，请参阅 Is left and right shifting negative integers defined behavior?。）

因此，您的陈述属于可怕的 "undefined behavior" 类别，这意味着所有赌注都被取消了。但一切并没有丢失。

首先，你可以作弊。 CPU 的汇编语言通常有一个算术右移指令，所以你可以直接使用它。例如，使用 x86 指令 sar（算术右移）：

    int arith(int x, unsigned k) {
      asm volatile ("sar %1,%0" :"+r"(x) :"c"((unsigned char)k));
      return x;
    }

请注意，我稍微更改了您的函数签名。从语义上讲，右移的位数 k 永远不应该是负数。（如果你想左移，使用那个。）事实上，上面引用的段落之前的段落（#3）指出（指的是 << 和 >>）：

If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

所以k在任何情况下都不应为负数，我做到了unsigned。我将 x 更改为带符号的 int 以便可以使用负数对其进行测试和检查（更多内容见下文）。 return 类型已更改为匹配。

当然，这个汇编解决方案只适用于 x86 机器。通用的东西可能会更好。 Shift operator in C 的这个答案很好地总结了位移的数学原理。对于非负 x，算术右移 k 位与整数除以 2^{的结果相同k}。不同之处在于 x 为负，整数除法舍入为零，算术右移舍入为负无穷大。这导致

    int arith(int x, unsigned k) {
      if ( x >= 0 ) {
        // Same as integer division for nonnegative x
        return x/(1<<k);
      } else {
        // If negative, divide but round to -infinity
        return x/(1<<k) - ( x % (1<<k) == 0 ? 0 : 1 );
      }
    }

三元运算符是判断除法是否有余数。如果有就减一个1到"round down." 1<<k当然是简单的计算方法2^k .请注意，此版本要求 x 是有符号类型，否则 x >= 0 将始终计算为真。

Answer 2

你只需要创建一个最左边有 k 个 1 的掩码（如果数字是负数），这是通过算术移位完成的符号扩展：

unsigned mask = x > 0x8000 ? (0xFFFF << (16-k)): 0;

然后将掩码应用于逻辑移位结果

unsigned x_arith = mask | (x >> k);

注意：我假设 16 位无符号，否则你需要使用 sizeof() 进行调整，因为这是作业我把那位留给你

为什么这个 C 算术移位实现不起作用？

Why is this C arithmetic shift implementation not working?

c

bit-manipulation