位元運算
 |
位操作是程序設計中對位數組或二進制數的一元和二元操作。在許多古老的微處理器上，位運算比加減運算略快，通常位運算比乘除法運算要快很多。在現代架構中，位運算的運算速度通常與加法運算相同（仍然快於乘法運算），但是通常功耗較小，因為資源使用減少。[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）.