位元運算

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

Remove ads

數學等價物

假設 $x\geq y$ ，對於非負整數，按位元運算可以被寫成如下形式：

{\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}}

Remove ads

所有二元邏輯運算子的真值表

兩個二進制變數（英語：Binary data）有16種可能的真值函數；這定義了一個真值表。

這是兩位 P 和 Q 的按位元等效運算：

更多資訊 p, q ...

按位元等效		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
p	q	矛盾⁰	邏輯或非¹	逆非蘊含（英語：Converse nonimplication）²	非p³	實質非蘊涵⁴	非q⁵	邏輯異或⁶	邏輯與非⁷	邏輯與⁸	邏輯異或非（英語：Logical biconditional）⁹	q（英語：Projection (set theory)）¹⁰	實質條件¹¹	p（英語：Projection (set theory)）¹²	逆命題¹³	邏輯或¹⁴	恆真式¹⁵
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

關閉

Remove ads

移位

移位是一個二元運算子，用來將一個二進制數中的每一位全部都向一個方向移動指定位，溢位的部分將被捨棄，而空缺的部分填入一定的值。在類C語言中，左移使用兩個小於符號"<<"表示，右移使用兩個大於符號">>"表示。

位定址

如果暫存器的寬度（通常為 32 甚至 64）大於最小可定址單元（通常稱為位元組）的位數（通常為 8），則移位元運算會促使從位元組到位的定址策略。因此，進位制的標準數碼書寫中，取「左」和「右」方向，使得左移增加數碼的值，右移減少數碼的值——如果先讀取左側數碼，這就是大端位元組序。忽略暫存器兩端的邊界效應，算術和邏輯移位元運算的行為相同，移動 8 位將位元型樣轉移 1 個位元組位置，方式如下：

小端序：左移 8 個位置，位元組地址加 1；右移 8 個位置，位元組地址減 1。
大端序：左移 8 個位置，位元組地址減 1；右移 8 個位置，位元組地址加 1。

算術移位

在算術移位中，溢位兩端的位都被丟棄。算術左移中，右側補上0；算術右移中，左側補上符號位（英語：Sign bit）（二補碼中的最高位），以保持原數的符號不變。

這個例子使用一個8位元暫存器，解釋為二補碼：

   00010111 (十进制 +23) LEFT-SHIFT
=  00101110 (十进制 +46)

   10010111 (十进制 −105) RIGHT-SHIFT
=  11001011 (十进制 −53)

在第一種情況下，最左邊的數碼被移到暫存器的末尾，新的 0 被移到最右邊的位置。在第二種情況下，最右邊的 1 被移出（可能進入了進位標誌（英語：Carry flag）），一個新的 1 被複製到最左邊的位置，保留了數碼的符號。多個移位有時會縮短為一個移位，減少了幾位。例如：

   00010111 (decimal +23) LEFT-SHIFT-BY-TWO
=  01011100 (decimal +92)

算術左移n位等價與乘以2ⁿ (前提值沒有整數溢位）。一個二補碼的值算術右移n 位等價與除以2ⁿ 下取整。如果二進制數被視為一的二補碼，則相同的右移運算會導致除以2ⁿ 和向零捨入。

邏輯移位

應用邏輯移位時，移位後空缺的部分全部填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（英語：GNU Pascal）），邏輯左移運算子和右移運算子分別是「shl」和「shr」。即使對於有符號整數， shr 的行為也類似於邏輯移位，並且不會複製符號位。要移動的位置數作為第二個參數給出。例如，下面將 y 左移兩位的結果賦值給 x：

x := y shl 2;

其他

漢明權重，在密碼學中被使用
計數前導零（英語：Count leading zeros）

應用

位元運算是必要的，尤其是在裝置驅動程式、低階圖形、通訊協定包組裝和解碼等低階編程中。

儘管機器通常具有執行算術和邏輯運算的有效內建指令，但所有這些運算都可以通過以各種方式組合按位元運算子和零測試來執行。^[7]例如，這裏是古埃及乘法（英語：Ancient Egyptian multiplication）的偽代碼實現，展示了如何僅使用位移和加法將兩個任意整數 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

參考

[1]
CMicrotek Low-power Design Blog. CMicrotek. [2015-08-12]. （原始內容存檔於2015-08-20）.
[2]
Arithmetic operators - cppreference.com. en.cppreference.com. [2016-07-06]. （原始內容存檔於2022-08-08）.
[3]
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）.
[4]
JTC1/SC22/WG14 N843 "C programming language" （頁面存檔備份，存於互聯網檔案館）, section 6.5.7
[5]
Operator (C# Reference). Microsoft. [2013-07-14]. （原始內容存檔於2017-07-06）.
[6]
"JavaScript Bitwise" （頁面存檔備份，存於互聯網檔案館）. W3Schools.com.
[7]
Synthesizing arithmetic operations using bit-shifting tricks. Bisqwit.iki.fi. 2014-02-15 [2014-03-08]. （原始內容存檔於2014-03-08）.

[1] [1]
CMicrotek Low-power Design Blog. CMicrotek. [2015-08-12]. （原始內容存檔於2015-08-20）.

[2] [2]
Arithmetic operators - cppreference.com. en.cppreference.com. [2016-07-06]. （原始內容存檔於2022-08-08）.

[3] [3]
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）.

[:0-4] [4]
JTC1/SC22/WG14 N843 "C programming language" （頁面存檔備份，存於互聯網檔案館）, section 6.5.7

[5] [5]
Operator (C# Reference). Microsoft. [2013-07-14]. （原始內容存檔於2017-07-06）.

[6] [6]
"JavaScript Bitwise" （頁面存檔備份，存於互聯網檔案館）. W3Schools.com.

[7] [7]
Synthesizing arithmetic operations using bit-shifting tricks. Bisqwit.iki.fi. 2014-02-15 [2014-03-08]. （原始內容存檔於2014-03-08）.

[1]

[2]

[3]

[4]

[5]

[6]

[7]