使用位移操作进行符号扩展

Question

根据这个问答，我试着验证了回答，所以我写了以下内容：

#include <stdio.h>

int main ()
{

        int t;int i;
        for (i=120;i<140;i++){
                t = (i - 128) >> 31;
                printf ("t = %X , i-128 = %X ,  ~t & i = %X , ~t = %X \n", t, i-128 , (~t &i), ~t);
        }

        return 0;
}

输出结果如下：

t = FFFFFFFF , i-128 = FFFFFFF8 ,  ~t & i = 0 , ~t = 0 
t = FFFFFFFF , i-128 = FFFFFFF9 ,  ~t & i = 0 , ~t = 0 
t = FFFFFFFF , i-128 = FFFFFFFA ,  ~t & i = 0 , ~t = 0 
t = FFFFFFFF , i-128 = FFFFFFFB ,  ~t & i = 0 , ~t = 0 
t = FFFFFFFF , i-128 = FFFFFFFC ,  ~t & i = 0 , ~t = 0 
t = FFFFFFFF , i-128 = FFFFFFFD ,  ~t & i = 0 , ~t = 0 
t = FFFFFFFF , i-128 = FFFFFFFE ,  ~t & i = 0 , ~t = 0 
t = FFFFFFFF , i-128 = FFFFFFFF ,  ~t & i = 0 , ~t = 0 
t = 0 , i-128 = 0 ,  ~t & i = 80 , ~t = FFFFFFFF 
t = 0 , i-128 = 1 ,  ~t & i = 81 , ~t = FFFFFFFF 
t = 0 , i-128 = 2 ,  ~t & i = 82 , ~t = FFFFFFFF 
t = 0 , i-128 = 3 ,  ~t & i = 83 , ~t = FFFFFFFF 
t = 0 , i-128 = 4 ,  ~t & i = 84 , ~t = FFFFFFFF 
t = 0 , i-128 = 5 ,  ~t & i = 85 , ~t = FFFFFFFF 
t = 0 , i-128 = 6 ,  ~t & i = 86 , ~t = FFFFFFFF 
t = 0 , i-128 = 7 ,  ~t & i = 87 , ~t = FFFFFFFF 
t = 0 , i-128 = 8 ,  ~t & i = 88 , ~t = FFFFFFFF 
t = 0 , i-128 = 9 ,  ~t & i = 89 , ~t = FFFFFFFF 
t = 0 , i-128 = A ,  ~t & i = 8A , ~t = FFFFFFFF 
t = 0 , i-128 = B ,  ~t & i = 8B , ~t = FFFFFFFF 

为什么在整数变量的情况下，任何负数的~t都等于-1 == 0xFFFFFFFF？

- 0x90

---

~0 == 0xFFFFFFFF 的意思是对数字0进行按位取反操作，得到的结果为十六进制数0xFFFFFFFF。~~x==x 的意思是对于任何整数x，对其进行两次按位取反操作，结果仍为原来的x。你只需翻转0和-1这两个数字的二进制位。假设使用32位整数。 - Aneri

为什么“-3>>31”会是“-1”，即“0xFFFFFFFF”？ - 0x90

标准规定右移负值是实现定义的。请阅读您编译器的文档以了解它在这种情况下的行为... - DCoder

@0x90 好的，请阅读我的答案，让我知道它是否有帮助。 - Grijesh Chauhan

@0x90 你在C++中使用哪些编译器，是否得到了相同的答案？ - Grijesh Chauhan

Answer 1

来源：在 C 语言中对负数进行右移

编辑：根据最新的草案标准第 6.5.7 节，负数的这种行为取决于实现：

表达式 E1 >> E2 的结果是将 E1 右移 E2 位。如果 E1 具有无符号类型或者 E1 具有带符号类型且值为非负数，则结果的值为 E1 / 2^E2 的整数部分。如果 E1 具有带符号类型且值为负数，则生成的值是实现定义的。

您的实现可能在使用二进制补码时执行算术右移。

---

运算符 >>，也称为带符号右移或算术右移，会将所有位向右移动指定的次数。重要的是，>> 会将左侧的符号位（最高有效位 MSB）填充到移位后的最左边的位。这被称为符号扩展，其作用是在对负数进行右移时保留符号。

下面是我的示例，以图解方式展示了这个过程（针对一个字节的情况）：
示例：

i = -5 >> 3;  shift bits right three time 

二进制补码表示法中的五是 1111 1011。内存表示：

 MSB
+----+----+----+---+---+---+---+---+
|  1 |  1 | 1  | 1 | 1 | 0 | 1 | 1 |   
+----+----+----+---+---+---+---+---+
   7    6   5    4   3   2   1   0  
  ^  This seventh, the left most bit is SIGN bit  

以下是关于 >> 如何工作的说明？当您执行 -5 >> 3 时

                        this 3 bits are shifted 
                         out and loss
 MSB                   (___________)      
+----+----+----+---+---+---+---+---+
|  1 |  1 | 1  | 1 | 1 | 0 | 1 | 1 |   
+----+----+----+---+---+---+---+---+
  | \                 \  
  |  ------------|     ----------|
  |              |               |
  ▼              ▼               ▼
+----+----+----+---+---+---+---+---+
|  1 |  1 | 1  | 1 | 1 | 1 | 1 | 1 |
+----+----+----+---+---+---+---+---+
(______________)
 The sign is        
 propagated

注意：左侧三位是1，因为在每次移位时符号位被保留，每个位都向右移动。我写了 “符号被传播” 是因为这三位全都是由符号位（而非数据）所导致。

[答案]
在您的输出中，

前八行

      ~t is 0
==>    t is FFFFFFFF 
==>    t is -1

（注：-1 的二进制补码是 FFFFFFFF，因为 1 的二进制补码是 00000001，1 的反码是 FFFFFFFE，而 2 的补码等于它的反码加 1，即 FFFFFFFE + 00000001 = FFFFFFFF。）

所以在循环的前八次中，t 的值始终为 -1。是的，为什么呢？

在 for 循环中。

for (i=120;i<140;i++){
     t = (i - 128) >> 31;

前八次i的值为i = 120, 121, 122, 123, 124, 125, 126 ,127，这八个值都小于128。所以(i - 128) = -8, -7, -6, -5, -4, -3, -2, -1。因此，在前八次中，表达式t = (i - 128) >> 31将一个负数向右移位。

t =   (i - 128)  >> 31
t =  -ve number  >> 31

因为在您的系统中，int占4个字节= 32位，所有最右侧31位都会被移除并丢失，并且由于符号位的传播，负数的所有位值变为1。 (如上图所示，对于一个字节)

因此，前八次：

    t =  -ve number  >> 31 ==  -1 
    t = -1
  and this gives 
    ~t = 0

因此，对于 ~t 的前八次输出结果均为0。

对于剩下的最后几行：

      ~t is FFFFFFFF
==>   ~t is -1   
==>    t is 0 

对于剩余的最后几行，在for循环中：

for (i=120;i<140;i++){
     t = (i - 128) >> 31;

i的值为128、129、130、132、133、134、135、136、137、138、139，所有这些值都大于或等于128。符号位为0。

因此，对于剩余的最后几行，(i - 128) >=0，并且所有这些MSB符号位都为0。因为你再次将其右移31次，除了符号位被移出和符号位0外，所有位都会被填充为0，数值变成了0。

我认为如果我再写一个正数的例子会更好。所以我们拿5 >> 3来举例，五是一个字节，表示为0000 0101。

                        this 3 bits are shifted 
                         out and loss
 MSB                   (___________)      
+----+----+----+---+---+---+---+---+
|  0 |  0 | 0  | 0 | 0 | 1 | 0 | 1 |   
+----+----+----+---+---+---+---+---+
  | \                 \  
  |  ------------|     ----------|
  |              |               |
  ▼              ▼               ▼
+----+----+----+---+---+---+---+---+
|  0 |  0 | 0  | 0 | 0 | 0 | 0 | 0 |
+----+----+----+---+---+---+---+---+
(______________)
 The sign is        
 propagated

再次看到我写的是符号扩展，所以最左边的三个零是由于符号位。

因此，这就是运算符>>带符号右移的作用，并且保留左操作数的符号。

- Grijesh Chauhan

---

实际上，这个答案对于C++来说是错误的。>>符号是填充还是零填充取决于具体实现。 - James Kanze

@JamesKanze 好的，只适用于C++，OP使用ptintf，头文件也是.h并标记为C，所以我认为答案在这里是正确的。是的，但链接的问题来自C++和Java。我的答案对于Java也是正确的。所以我认为我不应该删除我的答案。 - Grijesh Chauhan

@JamesKanze 如果运算符被重载，您是正确的，但在关于分支预测的原始问题中，>> 意味着天真的那一个。 - 0x90

不，C++ 在这里只是复制了 C，并且 C 标准非常明确。如果左操作数具有带符号类型并且为负，则结果是实现定义的。（我相信原因是并非所有处理器都具有算术右移指令。） - James Kanze

@JamesKanze 是的，你说得对，我不知道这一点。我刚刚找到了一个链接。谢谢 :) - Grijesh Chauhan

Answer 2

为什么t = (i - 128) >> 31对每个数字都会得出0或-1？

当一个非负的32位整数向右移动31个位置时，所有非零位都被移出，最高位被填充为0，因此结果为0。

通常情况下，当一个负的32位整数向右移动31个位置时，最高位不会被填充为0，而是被设置为该数的符号位，因此符号会传播到所有位并且在二进制补码表示中，所有位都为1相当于-1。其净效应类似于重复将该数字除以2，但有一个小细节...结果向负无穷舍入而不是向0舍入。例如，-2>>1==-1，但是-3>>1==-2和-5>>1==-3。这被称为算术右移。

当我说“通常情况下”时，我的意思是C标准允许负值的右移具有多种不同的行为。此外，它允许用符号的非二进制补码表示。通常，然而，您有二进制补码表示和我上面所示/解释的行为。

- Alexey Frunze

Answer 3

因为t要么是0，要么是-1，所以~t总是-1或0。

这是由于（实现定义的）(i - 128) >> 31行为，它本质上是复制（假设32位整数）（i-128）的最高位。如果i > 128，则结果在最高位为零。如果i小于128，则结果为负数，因此最高位被设置。

由于~t是“所有位相反的t”，因此如果t为零，则可以预期t始终为0xffffffff。

- Mats Petersson

---

这里的重点是移位是算术移位而不是逻辑移位，因为您声明它为 int 而不是 u32 或 unsigned int。 - 0x90

Answer 4

>> 运算符，即右移运算符，在大多数编译器中是算术右移，意味着除以2。

因此，如果例如 int i ==-4 (0xfffffffc)，那么 i>>1 == -2 (0xfffffffe)。

话虽如此，我建议您检查代码的汇编。
例如，x86 有两个单独的指令 - shr 和 sar，分别表示逻辑移位和算术移位。
通常，编译器对于无符号变量使用 shr（逻辑移位），对于有符号变量使用 sar（算术移位）。

---

以下是使用gcc -S生成的C代码和相应的汇编代码：

a.c:

int x=10;
unsigned int y=10;

int main(){
    unsigned int z=(x>>1)+(y>>1);
    return 0;
}

a.s:

    .file   "a.c"
.globl x
    .data
    .align 4
    .type   x, @object
    .size   x, 4
x:
    .long   10
.globl y
    .align 4
    .type   y, @object
    .size   y, 4
y:
    .long   10
    .text
.globl main
    .type   main, @function
main:
    pushl   %ebp
    movl    %esp, %ebp
    subl    $16, %esp
    movl    x, %eax
    sarl    %eax ; <~~~~~~~~~~~~~~~~ Arithmetic shift, for signed int
    movl    y, %edx
    shrl    %edx ; <~~~~~~~~~~~~~~~~ Logical shift, for unsigned int
    addl    %edx, %eax
    movl    %eax, -4(%ebp)
    movl    $0, %eax
    leave
    ret
    .size   main, .-main
    .ident  "GCC: (Ubuntu/Linaro 4.5.2-8ubuntu4) 4.5.2"
    .section    .note.GNU-stack,"",@progbits

- anishsane

Answer 5

C和C++的规则是，对负值进行右移位运算的结果是由实现定义的。因此，请阅读您编译器的文档。您得到的各种解释都是有效的方法，但这些方法都不是语言定义所规定的。

- Pete Becker