位元運算
 |
位元運算是程式設計中對位陣列或二進位數的一元和二元操作。在許多古老的微處理器上，位元運算比加減運算略快，通常位元運算比乘除法運算要快很多。在現代架構中，位元運算的運算速度通常與加法運算相同（仍然快於乘法運算），但是通常功耗較小，因為資源使用減少。[1]
位元運算符[編輯]
下面的解釋中，任何位元的表示都從右側（最低位）開始計數，向左進。舉個例子，二進位值0001（十進位1）除第一位（即最右邊）每位上都是0。
反相（NOT）[編輯]
反相是一元運算子，對一個二進位數的每一位執行邏輯反操作。使數位1成為0，0成為1。例如：
NOT 0111（十進位7） = 1000（十進位8）
NOT 10101011 (十进制 171) = 01010100 (十进制 84)
結果等於該值的二補數減一。如果使用二補數算術，則 NOT x = -x − 1。
對於無符號整數，數的按位元二補數是其在無符號整數範圍的中點另一邊的「鏡像」。例如，對於8位元無符號整數，NOT x = 255 - x，可以在圖上將其視覺化為一條向下的線，相當於把從 0 到 255 遞增的範圍，「翻轉」到從 255 到 0 遞減的範圍。一個簡單而有說明性的使用例子是反轉灰度圖像，其中每個像素儲存為無符號整數。
許多程式設計語言（包括C語言家族），反相運算子用波浪線"~"表示。值得注意的是此運算子與「邏輯非（!）」運算子不同。在C++中，邏輯非將數位整體看做一個布林類型——將真值轉化為假，將假值轉化為真；而C語言將0轉化為1，將非零值轉化為0。「邏輯非」並不是一個位元運算。
按位元或（OR）[編輯]
按位元或處理兩個長度相同的二進位數，兩個相應的二進位中只要有一個為1，該位的結果值就為1。例如
0101（十進位5） OR 0011（十進位3） = 0111（十進位7）
在C類程式設計語言中，按位元或運算子是"|"。這一運算子需要與邏輯或運算子（||）區別開來。
按位元或能夠將每一位看做旗標；在二進位數中的每一位可以表示不同的布林變數。應用按位元或操作可以將二進位數的某一位設為1。例如
0010（十進位2）
能夠看做包含4個旗標的組合。第1，2，4旗標為0；第3個旗標為1。利用按位元或可以將第1個旗標設定為1，而其他旗標不變。
0010（十進位2） OR 1000（十進位8） = 1010（十進位10）
這一技巧通常用來儲存程式中的大量布林變數。
按位元互斥或（XOR）[編輯]
按位元互斥或運算，對等長二進位模式或二進位數的每一位執行邏輯互斥或操作。操作的結果是如果某位不同則該位為1，否則該位為0。例如
0101 XOR 0011 = 0110
在類C語言中，按位元互斥或運算子是"^"。
組合語言的程式設計師們有時使用按位元互斥或運算作為將暫存器的值設為0的捷徑。用值的自身對其執行按位元互斥或運算將得到0。並且在許多架構中，與直接載入0值並將它儲存到暫存器相比，按位元互斥或運算需要較少的中央處理單元時鐘周期。
按位元互斥或也可以用於在位元集合中切換旗標。給出一個位元模式，
0010
第一和第三位能夠通過按位元互斥或運算使用同時切換。
0010 XOR 1010 = 1000
這一技巧可用於操作表示布林變數的位元模式。
按位元與（AND）[編輯]
按位元與處理兩個長度相同的二進位數，兩個相應的二進位都為1，該位的結果值才為1，否則為0。例如：
0101 AND 0011 = 0001
此操作可以被用來檢查一個特定的位是1還是0。例如，給定一個二進位模式0011（十進位3），我們用按位元與和一個僅在第二位為1的二進位模式來確定第二位是否為1：
0011 (十进制 3) AND 0010 (十进制 2) = 0010 (十进制 2)
因為結果0010是非零的，所以我們知道原模式中的第二位是1。這通常被稱為位遮罩。（類似的，使用紙膠帶覆蓋不應更改的部分或不感興趣的部分。在這種情況下，0 值會遮蔽不感興趣的位。）
按位元與可用於清除暫存器的選定位（或旗標），其中每個位代表一個單獨的布林狀態。 這種技術是一種使用儘可能少的記憶體來儲存大量布林值的有效方法。
例如，0110（十進位 6）可以被認為是一組四個旗標，其中第一個和第四個旗標是清除 (0)，第二和第三個旗標是設定 (1)。 第三個旗標可以通過按位元與僅在第三位具有零的模式來清除：
0110 (十进制 6) AND 1011 (十进制 11) = 0010 (十进制 2)
因為這條性質，通過查詢最低位的值檢查一個二進位數的奇偶性變得容易。用以上的例子：
0110 (十进制 6) AND 0001 (十进制 1) = 0000 (十进制 0)
因為6按位元與1是0，6可以被2整除，所以6是偶數。
在類C語言中，按位元與用'&'表示。
數學等價物[編輯]
假設，對於非負整數，按位元運算可以被寫成如下形式：
![{\displaystyle {\begin{aligned}\operatorname {NOT} x&=\sum _{n=0}^{\lfloor \log _{2}(x)\rfloor }2^{n}\left[\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}+1\right){\bmod {2}}\right]=2^{\left\lfloor \log _{2}(x)\right\rfloor +1}-1-x\\x\operatorname {AND} y&=\sum _{n=0}^{\lfloor \log _{2}(x)\rfloor }2^{n}\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}\right)\left(\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\right)\\x\operatorname {OR} y&=\sum _{n=0}^{\lfloor \log _{2}(x)\rfloor }2^{n}\left(\left[\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}\right)+\left(\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\right)+\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}\right)\left(\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\right)\right]{\bmod {2}}\right)\\x\operatorname {XOR} y&=\sum _{n=0}^{\lfloor \log _{2}(x)\rfloor }2^{n}\left(\left[\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}\right)+\left(\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\right)\right]{\bmod {2}}\right)=\sum _{n=0}^{\lfloor \log _{2}(x)\rfloor }2^{n}\left[\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor +\left\lfloor {\frac {y}{2^{n}}}\right\rfloor \right){\bmod {2}}\right]\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b40ce3a54314ea1b00f1bbb4118ee20b3a56d35b)
所有二元邏輯運算子的真值表[編輯]
這是兩位 P 和 Q 的按位元等效運算：
| p | q | 矛盾0 | 邏輯或非1 | 逆非蘊含2 | 非p3 | 實質非蘊涵4 | 非q5 | 邏輯互斥或6 | 邏輯與非7 | 邏輯與8 | 邏輯互斥或非9 | q10 | 實質條件11 | p12 | 逆命題13 | 邏輯或14 | 恆真式15 | ||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ||
| 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | ||
| 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | ||
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | ||
| 按位元
等效 |
0 | NOT (p OR q) |
(NOT p) AND q |
NOT p |
p AND (NOT q) |
NOT q |
p XOR q | NOT (p AND q) |
p AND q | NOT (p XOR q) |
q | (NOT p) OR q |
p | p OR (NOT q) |
p OR q | 1 | |||
移位[編輯]
移位是一個二元運算子，用來將一個二進位數中的每一位全部都向一個方向移動指定位，溢位的部分將被捨棄，而空缺的部分填入一定的值。在類C語言中，左移使用兩個小於符號"<<"表示，右移使用兩個大於符號">>"表示。
位定址[編輯]
如果暫存器的寬度（通常為 32 甚至 64）大於最小可定址單元（通常稱為位元組）的位數（通常為 8），則移位元運算會促使從位元組到位的定址策略。因此，進位制的標準數位書寫中，取「左」和「右」方向，使得左移增加數位的值，右移減少數位的值——如果先讀取左側數位，這就是大端位元組序。忽略暫存器兩端的邊界效應，算術和邏輯移位元運算的行為相同，移動 8 位將位元型樣轉移 1 個位元組位置，方式如下：
算術移位[編輯]
在算術移位中，溢位兩端的位都被丟棄。算術左移中，右側補上0；算術右移中，左側補上符號位（二補數中的最高位），以保持原數的符號不變。
這個例子使用一個8位元暫存器，解釋為二補數：
00010111 (十进制 +23) LEFT-SHIFT = 00101110 (十进制 +46)
10010111 (十进制 −105) RIGHT-SHIFT = 11001011 (十进制 −53)
在第一種情況下，最左邊的數位被移到暫存器的末尾，新的 0 被移到最右邊的位置。 在第二種情況下，最右邊的 1 被移出（可能進入了進位標誌），一個新的 1 被複製到最左邊的位置，保留了數位的符號。 多個移位有時會縮短為一個移位，減少了幾位。 例如：
00010111 (decimal +23) LEFT-SHIFT-BY-TWO = 01011100 (decimal +92)
算術左移n位等價與乘以2n (前提值沒有整數溢位）。一個二補數的值算術右移n 位等價與除以2n 下取整。如果二進位數被視為一的二補數，則相同的右移運算會導致除以2n 和向零捨入。
邏輯移位[編輯]
應用邏輯移位時，移位後空缺的部分全部填0。因此，邏輯左移和算術左移完全相同。
但是，由於邏輯右移將值 0 位插入最高位，而不是複製符號位，因此它適用於無符號二進位數，而算術右移適用於有符號二補數二進位數。
0001（十進位1） << 3（左移3位） = 1000（十進位8）
1010（十進位10） >> 2（右移2位） = 0010（十進位2）
迴圈移位[編輯]
另一種移位是迴圈移位。
旋轉[編輯]
在此操作中，有時稱為迴圈無進位，位被「旋轉」，就好像暫存器的左端和右端連接在一起一樣。 在左移期間移入右側的值是從左側移出的任何值，右移操作時反之亦然。 如果需要保留所有現有位，這很有用，並且它經常用於數位密碼學中。
進位旋轉[編輯]
進位旋轉是一種旋轉操作的變種，其中移入（在任一端）的位是進位標誌的舊值，移出的位（在另一端）成為進位標
志的新值。
一個簡單的進位旋轉可以類比邏輯和算術移位，只需提前設定好進位標誌。比如，如果進位標誌是0，那麼x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE是邏輯右移一位；如果進位標誌里是符號位的拷貝，那麼x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE是算術右移一位。因為這些原因，一些微控制器像低階PIC微控制器只有旋轉和進位旋轉，並不擔心算術或邏輯移位。
當對大於處理器的本機字長的數位執行移位時，進位旋轉特別有用，因為如果一個大數儲存在兩個暫存器中，從第一個暫存器的一端移出的位必須在另一端進入第二個暫存器。使用迴圈進位時，該位在第一次移位期間「儲存」在進位標誌中，準備在第二次移位期間移入而無需任何額外準備。
在高階語言中[編輯]
類C語言和Python[編輯]
在類C語言和Python中，邏輯移位元運算符是左移「<<」和右移「>>」。移位的位置數作為運算子的第二個參數給出。例如，
x = y << 2;
將x賦值為y左移兩位的結果，其等價於乘以四。
移位可能導致實現定義的行為或未定義行為，因此在使用它們時必須小心。 在 C 和 C++ 中，移位大於或等於字大小的位數是未定義的行為。[2]右移負值是實現定義的，但良好的編碼實踐不建議這樣做；[3]如果結果無法在結果類型中表示，則左移有符號值的結果是未定義的。[4]
在 C# 中，當第一個運算元是整形或長整形時，右移是算術移位。 如果第一個運算元是無符號整形或無符號長整形，則右移是邏輯移位。[5]
Java[編輯]
JAVA中有一個特有的無符號右移運算子「>>>」。此操作將忽略運算元的符號，同樣的還有「>>>=」。
JavaScript[編輯]
JavaScript使用按位元運算將兩個或多個數位中的每一個求值為 1 或 0。[6]
Pascal[編輯]
在 Pascal 及其所有方言中（如 Object Pascal 和 Standard Pascal），邏輯左移運算子和右移運算子分別是「shl」和「shr」。 即使對於有符號整數， shr 的行為也類似於邏輯移位，並且不會複製符號位。 要移動的位置數作為第二個參數給出。 例如，下面將 y 左移兩位的結果賦值給 x：
x := y shl 2;
其他[編輯]
應用[編輯]
位元運算是必要的，尤其是在裝置驅動程式、低階圖形、通訊協定包組裝和解碼等低階編程中。
儘管機器通常具有執行算術和邏輯運算的有效內建指令，但所有這些運算都可以通過以各種方式組合按位元運算子和零測試來執行。[7]例如，這裡是古埃及乘法的虛擬碼實現，展示了如何僅使用位移和加法將兩個任意整數 a 和 b（a 大於 b）相乘：
c ← 0
while b ≠ 0
if (b and 1) ≠ 0
c ← c + a
left shift a by 1
right shift b by 1
return c
另一個例子是加法的虛擬碼實現，展示了如何使用按位元運算子和零測試計算兩個整數 a 和 b 的和：
while a ≠ 0
c ← b and a
b ← b xor a
left shift c by 1
a ← c
return b
參考[編輯]
- ^ CMicrotek Low-power Design Blog. CMicrotek. [2015-08-12]. （原始內容存檔於2015-08-20）.
- ^ Arithmetic operators - cppreference.com. en.cppreference.com. [2016-07-06]. （原始內容存檔於2022-08-08）.
- ^ INT13-C. Use bitwise operators only on unsigned operands. CERT: Secure Coding Standards. Software Engineering Institute, Carnegie Mellon University. [2015-09-07]. （原始內容存檔於2016-04-22）.
- ^ JTC1/SC22/WG14 N843 "C programming language" （頁面存檔備份，存於網際網路檔案館）, section 6.5.7
- ^ Operator (C# Reference). Microsoft. [2013-07-14]. （原始內容存檔於2017-07-06）.
- ^ "JavaScript Bitwise" （頁面存檔備份，存於網際網路檔案館）. W3Schools.com.
- ^ Synthesizing arithmetic operations using bit-shifting tricks. Bisqwit.iki.fi. 2014-02-15 [2014-03-08]. （原始內容存檔於2014-03-08）.