數字在計算機中的表示：機器數、真值

• 機器數
  一個數在計算機中的二進制表示形式，叫做這個數的機器數。機器樹時帶符號的，在計算機中用一個數的最高位存放符號，正數為0，負數為1.
  比如：

  計算機字節長為8位，下面二進制就是機器數：
  十進制的 +3,轉換成二進制就是 00000011
  十進制的 -3,轉換成二進制就是 10000011
  

• 真值
  因為機器數第一位是符號位，所以機器數的形式值就不等于真正的數值。
  所以為了好區別，將帶符號位的機器數對應的真正數值稱為機器數的真值。
  比如：

  0000 0001 的真值 = +000 0001 = +1
  1000 0001 的真值 = -000 0001 = -1
  

對機器數進一步細化：原碼、反碼、補碼

• 原碼
  就是符號位加上真值的絕對值，即用第一位表示符號，其余位表示值。比如如果是8位二進制：

  [+1] 原碼 = 0000 0001
  [-1] 原碼 = 1000 0001
  

  第一位是符號位，因為第一位是符號位，所以8位二進制的取值范圍是：
  [1111 1111, 0111 1111]，即[-127, 127]

• 反碼
  正數的反碼是其本身，而負數的反碼是在其原碼的基礎上，符號位不變，其余各個位取反。比如：

  [+1] = [0000 0001]原 = [0000 0001]反
  [-1] = [1000 0001]原 = [1111 1110]反
  

  可見如果一個反碼表示的是負數，人腦無法直觀的看出來它的數值，通常要將其轉換成原碼再計算。

• 補碼
  在應用中，因為補碼能保持加減運算的統一，因此應用更廣，其表示方法是：

  • 正數的補碼就是其本身；
  • 負數的補碼是在其原碼的基礎上，符號位不變，其余各位取反，最后+1（即：在反碼的基礎上+1）

  [+1] = [0000 0001]原 = [0000 0001]反 = [0000 0001]補
  [-1] = [1000 0001]原 = [1111 1110]反 = [1111 1111]補
  

  對于負數，補碼表示方式也是人腦無法直觀看出其數值的，通常也需要轉換成原碼再計算其數值。

為何會有原碼、反碼和補碼

看個例子，計算十進制的表達式: 1-1=0，首先看原碼的表示：

1 - 1 = 1 + (-1) = [00000001]原 + [10000001]原 = [10000010]原 = -2

如果用原碼表示，讓符號位也參與計算，顯然對于減法來說，結果是不正確的，這也是為何計算機內部不使用原碼表示一個數。

為了解決原碼做減法的問題就出現了反碼，此時計算十進制的表達式為: 1-1=0

1 - 1 = 1 + (-1)
= [0000 0001]原 + [1000 0001]原
= [0000 0001]反 + [1111 1110]反 
= [1111 1111]反 = [1000 0000]原 
= -0

可以看到用反碼計算減法結果的真值部分是正確的，但是"0"的表示有點奇怪，+0和-0是一樣的，而且0帶符號是沒有任何意義，而且要浪費[0000 0000]原和[1000 0000]原兩個編碼來表示0。于是補碼的出現，解決了0的符號以及兩個編碼的問題:

1-1 = 1 + (-1)
= [0000 0001]原 + [1000 0001]原 
= [0000 0001]補 + [1111 1111]補 
= [0000 0000]補 = [0000 0000]原

這樣0用[0000 0000]表示， 而以前出現問題的-0則不存在了，而且可以用[1000 0000]表示-128：

(-1) + (-127)
= [1000 0001]原 + [1111 1111]原 
= [1111 1111]補 + [1000 0001]補 
= [1000 0000]補

-1-127的結果應該是-128，我們正好可以用[1000 0000]來表示-128，這樣使用補碼表示的范圍為[-128, 127]，這一點也比原碼的[-127,127]好。

拓展一下，對于編程中常用到的32位int類型，可以表示范圍是: [-2^31, 2^31-1] ，這也是我們在應用中經常見到的定義方式。

為何計算機中的按位運算使用的是補碼？

對于計算機中的按位運算，包括與操作（AND）、或操作（OR）、異或操作（XOR）等，使用補碼表示是最為常見的，因為補碼可以統一處理正數和負數，而且在進行數值運算時能夠保持一致性。

• 統一性和一致性：補碼表示法允許我們用同一種方式處理正數和負數。在補碼中，負數的表示是通過正數的按位取反再加1來得到的。這就意味著無論是正數還是負數，在計算機內部都是用相同的機制進行表示和運算的，不需要針對正負數分別編寫不同的邏輯。
• 溢出處理：在進行二進制運算時，可能會出現溢出。使用補碼可以更方便地處理溢出情況。例如，當兩個正數相加得到負數的情況，或者兩個負數相加得到正數的情況，在補碼中能夠更自然地處理，無需額外的特殊邏輯。
• 零的表示：使用補碼表示法，零的表示是唯一的，即所有位都是0，不管是正數還是負數的零。這樣，進行與操作時，如果某一位是零，與任何數進行與操作都不會改變那一位的值。
• 簡化硬件邏輯：使用補碼可以簡化硬件邏輯設計。在計算機內部，進行補碼的加法、減法、與操作等都可以使用相同的電路結構，從而降低了硬件設計的復雜度。

綜上所述，補碼在計算機內部的數值表示和運算中具有很多優勢，可以統一處理正數和負數、簡化邏輯設計，并且處理溢出等情況更為方便。因此，在計算機中的位運算，如與操作，通常都是使用補碼表示來進行的。

位運算規則

位運算主要有：與、或、異或、取反、左移和右移。其中左移和右移統稱為移位運算，移位運算又分為算數移位和邏輯移位。

與、或、異或和取反

• 與運算符：& ，運算規則是：對于每個二進制位，兩個數對應的位都是1時，結果為1，否則結果為0。（都是1為1，否則是0）

  0 & 0 = 0
  0 & 1 = 0
  1 & 0 = 0
  1 & 1 = 1
  

• 或運算符：| ，運算規則是：對于每個二進制位，兩個數對應的為都是0時，結果為0，否則結果為1。（都是0為0，為否是1）

  0 | 0 = 0
  0 | 1 = 1
  1 | 0 = 1
  1 | 1 = 1
  

• 異或運算符：⊕（在代碼中用∧ 表示異或），運算規則是：對于每個二進制位，兩個數對應的位相同時，結果為 0，否則結果為 1。（相同為0，不同為1）

  0 ⊕ 0 = 0
  0 ⊕ 1 = 1
  1 ⊕ 0 = 1
  1 ⊕ 1 = 0
  

• 取反運算符：~ ，運算規則是：對一個數的每個二進制位進行取反操作，0變成1,1變成0。（每個位 0變1,1變0）

  ~0 = 1
  ~1 = 0
  

移位運算

• 左移運算符： <<，將全部二進制位向左移動若干位，高位丟棄，低位補 0。對于左移運算，算術移位和邏輯移位是相同的。

• 右移運算符： >>，將全部二進制位向右移動若干位，低位丟棄，高位的補位由算術移位或邏輯移位決定：

  • 算術右移時，高位補最高位；
  • 邏輯右移是，高位補0。

原始     0000 0110	6
右移一次：0000 0011	3 相當于除以2
左移一次：0000 1100	12 相當于乘以2

移位運算與乘除法的關系

觀察上面的例子可以看到，移位運算可以實現乘除操作。由于計算機的底層的一切運算都是基于位運算實現的，因此使用移位運算實現乘除法的效率顯著高于直接乘除法的。

左移運算對應乘法運算。將一個數左移 k位，等價于將這個數乘以 2^k。
例如，29 左移 2 位的結果是 116，等價于 29×4。當乘數不是 2 的整數次冪時，可以將乘數拆成若干項 2 的整數次冪之和，例如，a×6 等價于 (a<<2)+(a<<1)。對于任意整數，乘法運算都可以用左移運算實現，但是需要注意溢出的情況，例如在 8 位二進制表示下，29 左移 3 位就會出現溢出。

算術右移運算對應除法運算。將一個數右移 k 位，相當于將這個數除以 2^k。
例如，50 右移 2 位的結果是 12，等價于 50/4，結果向下取整。

從程序實現的角度，考慮程序中的整數除法，是否可以說，將一個數（算術）右移 k 位，和將這個數除以 2^k等價？
對于 0和正數，上述說法是成立的，整數除法是向 0 取整，右移運算是向下取整，也是向 0 取整。
但是對于負數，上述說法就不成立了，整數除法是向 0 取整，右移運算是向下取整，兩者就不相同了。例如，(?50)>>2 的結果是 ?13，而 (?50)/4 的結果是 ?12，兩者是不相等的。
因此，將一個數（算術）右移 k 位，和將這個數除以 2^k是不等價的。
算法出題這早就考慮到了這一點，因此在大部分算法題都將測試數據限制在正數和0的情況，因此可以放心的左移或者右移。

位運算常用技巧??

位運算的性質有很多，此處列舉一些常見性質，假設以下出現的變量都是有符號整數。

• 冪等律：a &a=a，a ∣ a=a（注意異或不滿足冪等律）；

• 交換律：a & b=b & a，a ∣ b=b ∣ a，a⊕b=b⊕a；

• 結合律：(a & b) & c=a & (b & c)，(a ∣ b) ∣ c=a ∣ (b ∣ c)，(a⊕b)⊕c=a⊕(b⊕c)；

• 分配律：(a & b) ∣ c=(a ∣ c) & (b ∣ c)，(a ∣ b) & c=(a & c) ∣ (b & c)，(a⊕b) & c=(a & c)⊕(b & c)；

• 德摩根律：～(a & b)=(～a) ∣ (～b)，～(a ∣ b)=(～a) & (～b)；

• 取反運算性質：?1=～0，?a=～(a?1)；

  ?1=~0 
  在計算機中，負數的表示通常使用二進制的補碼表示法。
  -1 = [1000 0001]原 = [1111 1110]反 = [1111 1111]補
  0 =  [0000 0000]原 = [0000 0000]反 = [0000 0000]補~0 = [1111 1111]補
  在這種特定情況下，-1與~0的二進制表示是相同的。
  

  ?a=~(a?1)
  假設a的二進制表示是：00000101（即十進制的5）。考慮等式的右邊：~(a - 1)
  那么(a - 1)的二進制表示就是00000100（即十進制的4）。
  對(a - 1)的每一位按位取反，得到：11111011。計算等式的左邊：-a
  首先取a的每一位按位取反，得到：11111010。
  然后再加1，得到：11111011，與等式右邊的結果相同。這個等式的成立是基于補碼運算和按位取反的性質。
  

• 與運算性質：a & 0=0，a & (?1)=a，a & (～a)=0；

  a & (?1)=a
  在二進制補碼表示中，-1 的所有位都是1，即所有位取反后加1。
  -1 = [1000 0001]原 = [1111 1110]反 = [1111 1111]補
  無論 a 的某一位是0還是1，在與 -1 進行與操作后，結果的對應位都會保持不變。
  

  a & (~a)=0
  對于任意整數 a，按位取反操作 ~a 將 a 的每一位取反（0 變 1，1 變 0）
  如果 a 的某一位是 0，那么 ~a 的對應位是 1，所以在 & 運算中結果位為 0。
  如果 a 的某一位是 1，那么 ~a 的對應位是 0，所以在 & 運算中結果位也為 0。
  

• 或運算性質：a ∣ 0=a，a ∣ (～a)=?1；

  a ∣ (~a)=?1
  對于任意整數 a，按位取反操作 ~a 將 a 的每一位取反（0 變 1，1 變 0）
  如果 a 的某一位是 0，那么 ~a 的對應位是 1，所以在 | 運算中結果位為 1。
  如果 a 的某一位是 1，那么 ~a 的對應位是 0，所以在 | 運算中結果位也為 1。
  

• 異或運算性質：a⊕0=a，a⊕a=0；

處理位操作時，還有很多技巧，不要死記硬背，理解其原理對解決相關問題有很大幫助。下面的示例中，1s和0s分別表示與x等長的一串1和一串0：

操作某個位的數據??

如何獲取、設置和更新某個位的數據，也有固定的套路。例如：

獲取

該方法是將1左移 i 位，得到形如00010000的值。接著對這個值與num執行”位與“操作，從而將 i 位之外的所有位清零，最后檢查該結果是否為零。不為零說明 i 位為1，否則 i 位為0。代碼如下：

func getBit(num int, i int) bool {return num & (1 << i) != 0
}

設置

setBit先將1左移 i 位，得到形如00010000的值，接著堆這個值和num執行”位或“操作，這樣只會改變 i 位的數據。這樣除 i 位外的位均為零，故不會影響num的其余位。代碼如下：

func setBit(num int, i int) int {return num | (1 << i)
}

清零

該方法與setBit相反，首先將1左移 i 位獲得形如00010000的值，對這個值取反進而得到類似11101111的值，接著對該值和num執行”位與“，故而不會影響到num的其余位，只會清零 i 位。

func clearBit(num int, i int) int {mark := ~(1 << i)return num & mark
}

更新

這個方法是將setBit和clearBit合二為一，首先用諸如11101111的值將num的第 i 位清零。接著將待寫入值 v 左移 i 位，得到一個 i 位為 v 但其余位都為0的數。最后對之前的結果執行”位或“操作，v為1這num的 i 位更新為1，否則為0：

func updateBit(num int, i int, v int) int {mark := ~(1 << i)return (num & mark) | (v << i)
}