0 基礎知識
0.1 原碼與補碼
在計算機中,資料都是以
和
1
的形式存放,對于同一個比特串,我們以不同的方式去看待,可能就會得到完全不同的結果。下面以一個位元組的資料為例進行說明:
- 對于位元組資料
,如果我們以原碼的方式去看待,那這個位元組表示的資料為十進制01001001
;如果以補碼的方式去看待,那這個位元組表示的資料也是73
。因為在補碼中,最高位為符号位,而最高位為 的情況下,補碼與原碼表示形式一緻。73
- 對于位元組資料
,如果我們以原碼的方式去看待,那這個位元組表示的資料為十進制10101001
;如果以補碼的方式去看待,那這個位元組表示的資料為十進制169
。因為最高位為-87
的情況下,補碼表示的為負數。1
0.2 原碼與補碼轉換規則
在章節 0.1 中提到了位元組資料
10101001
,以補碼形式看待時,表示的是十進制資料
-87
,那麼
-87
的補碼是怎麼生成的呢?
- 第一步:求 |-87| = 87 的原碼表示,即
;01010111
- 第二步:對第一步中的原碼按位取反,即
;10101000
- 第三步:對第二步中得到的結果加一,即
。10101000 + 00000001 = 10101001
總結一下,如果需要求非負整數的補碼,直接求其原碼表示即可,因為此時原碼與補碼表示形式相同;如果需要求負整數的補碼,首先求其絕對值的源碼表示,然後對源碼按位取反再加一即可。
0.3 邏輯移位與算數移位的差別
所謂邏輯移位,就是将資料一律視為原碼表示,即非負數;而算數移位,是将資料視為補碼表示,此時最高位為符号位,移位過程中需要格外注意。
無論是邏輯移位還是算數移位,右移一位均相當于除以 2,左移一位相當于乘以 2;而且在計算機中,移位操作效率非常高,是以,在進階語言程式設計中,經常用移位操作來替代乘除法(乘數和除數均為 2 的整數次幂)。
1 移位規則
1.1 邏輯左移
低位覆寫高位,低位的空缺直接補零。例如:
-
左移 1 位變為10101010
;01010100
-
左移 3 位變為00010010
。10010000
1.2 邏輯右移
高位覆寫低位,高位的空缺直接補零。例如:
-
右移 1 位變為10101010
;01010101
-
右移 3 位變為00010010
。00000010
1.3 算數左移
算數左移與邏輯左移完全一緻,低位覆寫高位時,符号位也會被覆寫。
對于算數左移與邏輯左移完全一緻這句話的直覺了解可拆分為兩部分:
- 如果操作數的符号位為 0,那麼這個數是一個非負數,此時算數右移等價于邏輯左移很好了解;
- 如果操作數的符号位為 1,那麼這個數是一個負數,大家可能會遲疑:低位覆寫高位的操作是不是應該将符号位排除在外,因為覆寫符号位的話很可能操作數由負數變為非負數了?其實不然,覆寫的過程中符号位是跟着一起操作的,可以這樣了解,如果這個負數的絕對值較小,那麼這個數(補碼表示)的高位都應該為 1,此時次高位覆寫掉最高位(符号位)是沒問題的,結果依然為負數;如果這個負數的絕對值較大,那麼次高位一定為 0,大家想想,這個時候再左移一位,相當于對這個負數乘以 2,必定會小于補碼所能表示的最小負數,于是産生溢出,次高位的 0 覆寫掉符号位 1,結果變為非負數,這不也是理所應當的嘛!
1.4 算數右移
算數右移的規則稍微麻煩一點,需要視符号位而定。
- 如果符号位為 0,高位(包含符号位)覆寫低位,高位的空缺補零,此時算數右移等價于邏輯右移;例如,
算數右移 2 位變為01001011
。00010010
- 如果符号位為 1,高位(包含符号位)覆寫低位,高位的空缺補一;例如,
算數右移 2 位變為10010101
。11100101
2 用右移電路實作左移
如果在硬體中使用門電路實作了邏輯右移與算數右移電路,那麼邏輯左移與算數左移無需再行使用門電路搭建,可以接複用邏輯右移電路,再稍作處理即可。
從章節 1 中可知,邏輯左移與算數左移完全一緻,是以後面統稱為左移。
使用邏輯右移電路實作左移的步驟如下:
- 将待移位資料進行高低位反轉,即最高位與最低位交換、次高位與次低位交換…例如,
反轉後為10101010
;01010101
- 将反轉後的操作數輸入邏輯右移電路,進行移位操作;
- 将邏輯右移電路的輸出再次進行高低位反轉,所得即為左移操作結果。
下面是使用 Logisim2.7.1 繪制的電路實作: