為什麼0取反再右移任意位得出數總是-1？

01-06

C語言

對有符號的整數類型（如 int）進行右移，在標準中是由平台自行定義的，不過一般是使用二補數表示有符號整數，而右移是算術右移（arithmetic right shift），即是會用原來的最高位（MSB）來填補右移後左面的空位。

字面量 0 的類型為 int，取反後全部位為 1，作為有符號整數是 -1，算術右移後也不變。

如果用字面量 0u，結果就不一樣了。

圖源：https://en.m.wikipedia.org/wiki/Arithmetic_shift#/media/File%3ARotate_right_arithmetically.svg

我想補充的是，單次移位數不能&>=bit數，否則是UB

最近正好在看CSAPP（Computer System: A Programmer"s Perspective，中文譯本為深入理解計算機系統），就來回答一下叭w~

首先簡單介紹一下機器中整數(int)的存儲形式：絕大多數情況下，不管是32位機器還是64位機器，int都是4個位元組（32位）。其中最高位(MSB, the Most Significant Bit) $x_{31}$ 視作符號位，符號位為0則為非負數，符號位為1則為負數。

用向量的形式表示計算機中字元的儲存，則可以表示為 $[x_{31},x_{30},x_{29},...x_{2},x_1,x_0]$ ,對應表示的整數為 $-x_{31}cdot2^{31}+sum_{i=0}^{30}{x_icdot2^i}$ .所以，int可以表示的最大數 $T_{Max}=[0111...111]=2^{31}-1$ ,最小數 $T_{Min}=[1000...0000]=-2^{31}$ 。

0作為整數(Integer），在機器中的表示形式為000....000（32個0），取反後為1111...1111。根據上述計算公式可得二進位碼1111...1111即代表整數-1。

那麼為什麼右移任意位依然是-1呢？

右移有兩種形式：邏輯右移(logical right shift)和算數右移(arithmetic right shift)。

邏輯右移是將左邊空位補0。所以將int右移k位便得到 $[0,...,0,x_{31},x_{30},...,x_k]$ 。

算數右移是將左邊空位補上MSB位。所以將int右移k位便得到 $[x_{31},...x_{31},x_{31},x_{30},...x_k]$ 。通俗的講法即非負數右移補0，負數右移補1。

C標準並沒有規定應該使用哪一種右移方式，不過絕大部分情況下使用的是算數右移。而1111...1111右移任意位依然是1111...1111，所以結果總是-1。

沒記錯的話C語言中右移一個負數，左邊補0還是1是implementation defined，不過就算從算數角度說，0取反右移也是1啊：

不考慮實際條件的限制，0等於是……0000000000（無窮個0），取反後是……111111111111（無窮個1），無窮個1右移還是無窮個1，也就是-1嘛

為啥無窮個1是-1呢，計算0-1，不夠減，往前借位，還不夠借，無限借下去，想像一下最後「假裝」借到了，就變成無窮1了，或者無窮個1加一，無限進位過去，就是0了

註：差不多是這個道理，但上面的某些「證明」別當真，哈哈

你如果是按位取反，～0就變成了111111...1，右移一般補符號位，也就是還是111...1，也就是補碼的-1了。

如果你是邏輯取反，！0就是1，右移就是0了。

那得看類型吧，signed類型是算數右移，補最高位，unsigned是邏輯右移補0

這不是深入理解計算機系統第二章的內容嗎。看下補碼就會了吧

對於位運算而言，運算對象可以是帶符號的，也可以是無符號的。如果運算對象是帶符號的且它的值為負，那麼位運算如何處理運算對象的「符號位」依賴於機器。

左移運算符&<&<在右側插入值為0的二進位位。右移運算符&>&>的行為依賴於左側運算對象的類型：如果是無符號的，在左側插入值為0的二進位位；如果是帶符號的，在左側插入符號位的副本或值為0的二進位位，如何選擇視具體環境而定。

去看看《程序員的數學》

有如下代碼：

int main()

{

int a=0;

int b=(~a)&>&>2;

return 0;

}

X64的反彙編：

main:

.LFB0:

.cfi_startproc

pushq %rbp #棧指針

.cfi_def_cfa_offset 16

.cfi_offset 6, -16

movq %rsp, %rbp

.cfi_def_cfa_register 6

movl $0, -8(%rbp) #壓棧，創建64位整形變數int a，並把0賦值給a

movl -8(%rbp), %eax #總共做了兩件事：1.把棧指針所指地址的值賦給eax寄存器，也就是a的值 2.然後壓棧，創建64位整形變數 int b,

notl %eax #取反

sarl $2, %eax #算數右移

movl %eax, -4(%rbp) #只把低32位的值賦給b

movl $0, %eax

popq %rbp

.cfi_def_cfa 7, 8

ret

.cfi_endproc

.LFE0:

.size main, .-main

.ident "GCC: (Ubuntu 5.4.0-6ubuntu1~16.04.4) 5.4.0 20160609"

.section .note.GNU-stack,"",@progbits

ARM aarch32 的反彙編

00000008 &:

8: e1a0c00d mov ip, sp

c: e92dd800 stmdb sp!, {fp, ip, lr, pc}

10: e24cb004 sub fp, ip, #4 ; 0x4

14: e24dd008 sub sp, sp, #8 ; 0x8

18: e3a03000 mov r3, #0 ; 0x0 #賦給r3 0值

1c: e50b3010 str r3, [fp, #-16] #壓棧，創建int a變數

20: e51b3010 ldr r3, [fp, #-16] #讀取a的值

24: e1e03003 mvn r3, r3 #取反

28: e1a03143 mov r3, r3, asr #2 #算數右移動

2c: e50b3014 str r3, [fp, #-20] #壓棧，創建int b ,並把右移後的a賦值給它

30: e3a03000 mov r3, #0 ; 0x0

34: e1a00003 mov r0, r3

38: e24bd00c sub sp, fp, #12 ; 0xc

3c: e89da800 ldmia sp, {fp, sp, pc}

ARM aarch64

main:

sub sp, sp, #16

str wzr, [sp,12]

ldr w0, [sp,12]

mvn w1, w0 #和aarch32類似，還是取反

asr w0, w1, 2 #算數右移

str w0, [sp,8]

mov w0, 0

add sp, sp, 16

ret

.size main, .-main

.ident "GCC: (GNU) 4.9.x-google 20140827 (prerelease)"

.section .note.GNU-starck,"",%progbits

以上三個架構的反編譯均是取反然後算術右移，可見算數右移應該是C語言右移標識符的標準了，應該不存在特例。

算術右移是符號位保持不變，每右移一位，左邊都補一位符號位，即符號位是0，左邊就補0，符號位是1，左邊就補1，以8位為例，0b00000000,取反(取反操作沒有符號位的說法)後變成0b11111111，右移後永遠都是0b11111111,這是變數b所在的內存地址所存的實際的值，是個補碼(或者說被程序當成補碼)，在用printf顯示時會自動轉換成原碼，即補碼取反再加一，變成0b10000001,永遠是-1