專欄：算法

上一篇：（二）基礎運算

下一篇：（四）質數（素數）

目錄

• 1. 常見的位運算
• • 1.0 位運算與邏輯運算之間的關系
  • 1.1 按位與
  • 1.2 按位或
  • 1.3 按位取反
  • 1.4 按位異或
  • 1.5 移位
  • • 1.5.1 左移
    • 1.5.2 有符號右移（算術右移）
    • 1.5.3 無符號右移（邏輯右移）
• 2. 編程語言相關
• • 2.1 位運算操作符
  • 2.2 C運算符優先級
  • 2.3 整數類型之間的轉換
  • • 2.3.1 低級類型向高級類型轉換
    • 2.3.2 高級類型向低級類型轉換
    • 2.3.3 整型提升
    • • 2.3.3.1 整型提升后的不同
• 3. 常用的位運算操作
• • 3.1 二進制位 bit(n)
  • 3.2 數二進制形式輸出
  • • 3.2.1 itoa() 函數
    • 3.2.2 手動實現二進制格式的輸出
  • 3.3 對應位置位
  • 3.4 對應位清零
  • 3.5 對應位取反
  • 3.6 取二進制位
  • • 3.6.1 取二進制位
    • 3.6.2 取兩個二進制數不同的位
    • 3.6.2 取a為1，b為0的位
  • 3.7 位逆序
  • • 3.7.1 常規位逆序方法
    • 3.7.2 蝴蝶算法
    • • 3.7.2.1 8位二進制數逆序
      • 3.7.2.2 $N$ 位二進制數逆序
  • 3.8 位循環移動
  • 3.9 lowbit運算
  • • 3.9.1 lowbit概念
    • 3.9.2 lowbit運算的實現
    • 3.9.3 消去lowbit
  • 3.10 highbit運算
  • • 3.10.1 位的擴散
    • 3.10.2 利用異或取最高位
    • 3.10.3 highbit運算實現
    • 3.10.4 擴展：取比給定值大的二進制位
    • 3.10.5 擴展：取不小于給定值的二進制位
    • • 3.10.5.1 實現一
      • 3.10.5.2 實現二
• 4. 位運算的應用
• • 4.1 生成低N位掩碼
  • 4.2 生成從第M位開始的連續N位的掩碼
  • 4.3 取連續N位的值
  • • 4.3.1 先右移再取位，和先取位再右移有什么不同？
  • 4.4 設置某些位的值
  • 4.5 位連續翻轉
  • 4.6 lowbit應用：統計一個二進制數中為1的位數
  • 4.7 lowbit應用：判斷一個數是否是2的冪
  • 4.8 lowbit應用：將右邊第一組連續為1的二進制位變為0
  • 4.9 將右邊從最低位開始的連續為1的二進制位變為0
  • 4.10 將右邊從最低位開始的連續為0的二進制位變為1
  • 4.11 奇偶判斷
  • 4.12 對 $2^k$ 取模

??現代計算機中，幾乎都是二進制計算機，所有的數據都以二進制的形式存儲在設備中。位運算就是直接對存儲在內存中的數據的二進制位進行操作。
??在計算機中，每一個二進制位稱為1個bit，單位簡寫做 b。通常8個bit為一個單位，稱為 字節(byte)，單位簡寫作 B。

??一個字節不一定是8位，由硬件決定。但現在通用的標準中，一個字節等于8位。

??在C/C++中表示二進制數一般使用0x前綴表示的十六進制形式，和二進制數有一一對應的關系，如0x5A，表示二進制數 $01011010$。
??八進制屬于廢棄沒人用的狀態，八進制一個數占3位，和一個字節8位的現狀格格不入，而利于顯示二進制位的二進制格式卻缺失，不得不說這是一種設計上的缺陷。Python及Java等由類C編程語言在早年就添加了二進制字面量，C++中二進制字面量直到C++14標準才補上，以 0b 或 0B表示，如 0b01011010，但C語言標準一直沒有，只在GNU C編譯器上有相應的擴展語法，所以在代碼中以0b為前綴的數有可能編譯不過。

1. 常見的位運算

??在 $n$ 位二進制數中，我們一般稱最低位為第$0$位，最高位為$n?1$位，總右到左依次是第$0,1,2,?,n?1位$，如下圖所示：

??我們在計算時，一般使用的是 32位的int 類型(在個人計算機中，int一般為32位)，但為了便于將算法以圖形表示，下面一般使用8位的二進制數來展示，而不是使用32位，否則位數太多，圖形過小，不利于繪制和閱讀。

??在編程語言中，以下四個算術位運算最為常見：

與或非異或

運算符	&	|	~	^
英文表示的運算符	and	or	not	xor

1.0 位運算與邏輯運算之間的關系

??邏輯運算也叫布爾運算，以邏輯中的真和假作為運算單元(布爾值)進行運算，運算結果也是真或假。在二進制中，一般用 1 和0 分別表示真和假。

??位運算是將每個二進制位作為 布爾值，分別對一個或兩個二進制數中對應的二進制位做布爾運算。如果是對兩個數做運算，那么對應的兩個二進制位一共有 00, 01, 10, 11四種組合，如果只對一個數做運算，那么二進制位只有0和1兩種組合。對應位運算的結果仍然是布爾值，為 0 或 1。

??需要注意，位運算是針對 二進制 的運算，分別對每一個二進制位進行布爾運算操作。所以在手動進行 位運算計算 時，需要將數轉換成二進制的表示形式，再進行計算。如 3 & 5，先寫成二進制形式的 $0011$ 和 $0101$，右邊最低位對齊后再分別對相應位進行位運算。

1.1 按位與

??在 邏輯與 運算中，參與運算的兩個布爾值只有 0 和 1 兩種取值，只有當兩個布爾值都為1時，結果才得1，其余只要有一個值為0，結果就為0，類似乘的關系。邏輯與 的符號為 &&。

ab邏輯與結果

0	0	0 && 0	0
0	1	0 && 1	0
1	0	1 && 0	0
1	1	1 && 1	1

??特性，和 1 相與不變，和 0 相與 得 0：
$$\begin{array}{rl}x\&\&1& =x\\ x\&\&0& =0\end{array}$$

??按位與 則是對兩個二進制數的對應位分別做 邏輯與 運算，運算符號為 &。

??從上面可以看到，與1相與不變，與0相與會變為0?？梢岳眠@個特性將某些位清零，也可以取出某些位。

1.2 按位或

??在 邏輯或 運算中，參與運算的兩個布爾值只有 0 和 1 兩種取值，只有當兩個布爾值都為0時，結果才得0，其余只要有一個值為1，結果就為1，類似加的關系(不進位)，邏輯或的符號為 ||。

ab邏輯或結果

0	0	0 || 0	0
0	1	0 || 1	1
1	0	1 || 0	1
1	1	1 || 1	1

??特性，和 1 相或 得 1，和 0 相或不變：
$$\begin{array}{rl}x||1& =1\\ x||0& =x\end{array}$$

??按位或 則是對兩個二進制數的對應位分別做 邏輯或 運算，符號為 | 。

??從上面可以看到，與1相或會變為1，與0相或不變。可以利用這個特性將某些位置位(位的值變為1)。

1.3 按位取反

??在 邏輯非 運算中，布爾值只有 0 和 1 兩種取值，當布爾值為0時結果為1，當布爾值為1時結果為0，邏輯非的符號為 !。

a邏輯非結果

0	! 0	1
1	! 1	0

??按位取反 即對二進制數的的每個位做 邏輯非 運算，原來是0的位變為1，原來是1的位則變為0， 符號為 ~，也叫 按位非。

1.4 按位異或

??在 邏輯異或 運算 中，參與運算的兩個布爾值只有 0 和 1 兩種取值，只有當兩個布爾值不同時，結果才得1，其余結果為0，類似不等于的關系，邏輯異或在數學上一般用符號 $\oplus$ 表示。

??在編程語言中很少有 邏輯異或 的符號，運算中一般用不等于(!=)替代，前提是參與運算的兩個都是布爾值。

ab邏輯異或結果

0	0	0 $\oplus$ 0	0
0	1	0 $\oplus$ 1	1
1	0	1 $\oplus$ 0	1
1	1	1 $\oplus$ 1	0

??特性，和 1 異或 取反，和 0 異或不變：
$$\begin{array}{rl}x\oplus 1& =!x\\ x\oplus 0& =x\end{array}$$

??按位異或 則是對兩個二進制數的對應位分別做 邏輯異或 運算， 符號為 ^。

??從上面可以看到，與1異或會取反(由1變0，或由0變1)，與0異或不變?？梢岳眠@個特性將某些位取反。

??按位異或可以將某些位取反，而取反兩次則會變為原值：$$a\text{^}b\text{^}b=a$$

??利用這個特性可以將因進行了按位異或而被改變的數據還原。

1.5 移位

1.5.1 左移

??左移是將所有二進制位向左移動 $n$ 位(對于32位值 $n$范圍是$[0,31]$)。移動后，最左邊的 $n$ 個二進制位將因被移出邊界而丟棄，移動后最右邊空出來的二進制位補0。

??對于32位的int型值，如果移動位數超出 $32$ 位，將會被對$32$取模，如移動 $35$ 位，將變成移動 $3$ 位( $35\%32=3$)。所以左移$32$位并不會變為$0$，而是相當于移動 0 位，值不變。
??對于$64$位數，移動的位數則是對$64$取模。

??在沒有發生 溢出 和 環繞 的情況下，$n$ 左移一位后的值相當于 $2n$。$$n<<1=2n$$

溢出：指的是計算結果超出有符號數存儲的范圍。
環繞：指的是計算結果超出無符號數存儲的范圍。

??例如，0b0101左移一位變成0b1010，由5變成10。

1.5.2 有符號右移（算術右移）

??有符號整數左邊的最高位為符號位，代表著數的正負，負數最高位為1，正數和0的最高位為0。有符號數右移時，最右邊的位丟棄，最左邊的空位補上原來的最高位。有符號右移又叫 算術右移，在算術上相當于是值除以2的結果，C/C++中對有符號類型變量的右移是算術右移。

??如果移動位數超出 $32$ 位，將會被對$32$取模，如移動 $35$ 位，將變成移動 $3$ 位( $35\%32=3$)。所以右移$32$位并不會變為 $0$ 或 $?1$ ，而是相當于$1>>0$，值不變。對于更大的64位數，則是對64取模。

??對于有符號數來說，算術右移的結果等于原數除以2再向下取整(公式中，$?x?$為對$x$向下取整)：
$$n>>2=?\frac{a}{2}?$$??如負數 $?3>>1=?2$, 正數 $3>>1=1$。

??負數不斷進行算術右移，最終變為 $?1$， 而非負數最終變為 $0$。

1.5.3 無符號右移（邏輯右移）

??無符號數沒有符號位，所有位都作為二進制的數值位。右移時，最右邊的位丟棄，最左邊的位補0。無符號右移又叫 邏輯右移。C/C++中對無符號類型變量的右移是邏輯右移。

??如果移動位數超出 $32$ 位，將會被對$32$取模，如移動 $35$ 位，將變成移動 $3$ 位( $35\%32=3$)。所以右移$32$位并不會變為$0$，而是相當于$1>>0$，值不變。對于更大的64位數，則是對64取模。

??對于無符號數來說，算術右移的結果等于原數除以2再向下取整(公式中，$?x?$為對$x$向下取整)：
$$n>>2=?\frac{a}{2}?$$??如 $3>>1=1$。

??二進制數連續進行邏輯右移，最終變為 $0$。

2. 編程語言相關

2.1 位運算操作符

??位運算主要有以下幾種：

位運算C語言操作Java操作

按位與	a & b	a & b
按位或	a | b	a | b
按位異或	a ^ b	a ^ b
按位取反	~a	~a
左移	a << b	a << b
有符號右移	a >> b(當變量 a 為有符號類型時)	a >> b
無符號右移	a >> b(當變量 a 為無符號類型時)	a >>> b

2.2 C運算符優先級

??需要注意的是，除了一元運算符按位取反(~)外，其它位運算符的優先級都比較低，所以在計算時需要注意。除了加減和乘除、單目運算符和雙目運算符、賦值運算符與其它運算符這種非常明顯的優先級對比外，其它容易產生混淆的盡量用括號括起來，保證計算的順序，而不是依賴于運算符的優先級，否則當自己記錯或回憶不起時，就很容易影響到程序的正確性和可讀性。

表達式容易誤認為的運算順序實際運算順序

a & b != 0	(a & b) != 0	a & (b != 0)
1 << 2 + 1	(1 << 2) + 1	1 << (2 + 1)

2.3 整數類型之間的轉換

??C/C++ 中的整數類型有 char, short, int, long 和 long long，這里按類型的位數進行區分，類型的位數越高，那么取值范圍就越大，類型就越高級。
??這里的類型等級不區分是有符號還是無符號，如果要區分的話，同一個整數類型的無符號類型相當于比有符號類型高半個等級。
??當然，一個變量的類型無論是有符號還是無符號，其 存儲的二進制內容都是不變的，不同的對這些二進制位的解釋方法。無符號數把最高位作為一個普通的位，而有符號數把最高位作為符號位，相當于改變了最高位的權重。$n$ 位無符號數最高位權重是 $2^{n?1}$，而有符號數最高位權重是 $?2^{n?1}$。

??如一個八位的無符號數 $a$，二進制表示為$10000001$，最高位權重是128，最低位權重是1，因此值為 129。當把 $a$ 轉成有符號數時，二進制表示依然為 $10000001$，但此時最高位的含義已經發生了變化，相當于權重 $?128$，此時值為 $?127$。

2.3.1 低級類型向高級類型轉換

??在整數類型之間的轉換中，如果一個變量由 低級類型 向 高級類型 轉換，那么轉換時低位不變、高位根據變量 原先的類型 是無符號還是有符號使用不同的方式進行填補。

變量原先的類型高位填補方式

無符號類型	用 0 填補
有符號類型	用符號位進行填補

2.3.2 高級類型向低級類型轉換

??在整數類型之間的轉換中，如果一個變量由 高級類型 向低級類型轉換，那么二進制位將會被 截斷 ，高位丟棄，只保留低位作為轉換后的二進制內容。最后的值是多少則根據轉換后是有符號類型還是無符號類型對二進制位進行解析。
??如下圖所示，一個16位類型的值轉成8位類型，直接截取低8位作為轉換后的二進制內容 $10101101$，如果這個8位類型是無符號，那么數值為 173，如果是有符號類型，則是 -83。

??截斷的方式實際上相當于將原值看作無符號類型然后進行取模。取模后得到一個無符號的二進制數，再根據轉換后的類型是有符號還是無符號來確定最終的值。
??應該知道的是，無論是有符號類型還是無符號類型，各個二進制位上的值都是一樣的，只不過是賦予了最高位不同的含義。

2.3.3 整型提升

??在C/C++中，進行表達式計算時，各種整數類型會首先自動轉換成 int 型，如果 int 不足以表示的話，就需要提升為 unsigned int 類型，然后再執行表達式的運算。

??因為 int 代表著CPU的自然運算類型，一個8位二進制數存儲到32位寄存器中，高位也是會有數值的，所以會自然地擴展到32位。

??這意味著即使參與運算的所有整數類型變量的類型都比 int 類型低級，在運算時也會先提升至 int型再運算，最終結果為 int型。如下所示，兩個8位的 char 型的值 'A' 和 'B'進行運算時，會先轉換成32位的 int 再進行計算，整個表達式結果為 int 型。

'A' + 'B'; // 表達式類型為 int

??因此，雖然下面的表達式中三個變量都是 char 型，但是實際上發生兩次 由 char 向 int 的轉換，和一次由 int 向 char 的轉換。

char a = 'A', b = 'B'; char c = a + b; // a 和b 在運算時會先轉成 int，計算結果再由 int 轉成 char 賦值給 c .

2.3.3.1 整型提升后的不同

??那么，提不提升，結果有什么不同呢？在上面的表達式 char c = a + b中，提升和不提升最終結果不都是一樣的嗎？

??① 如果變量先進行了整數提升，運算后再轉換回原來的類型，那么結果是一樣的，因為對最終值進行了截斷，和原先溢出的結果是一致的。例如，char c = 'A' + 'B'，被提升成 int 型后又被轉換成 char 型，和不提升的結果是一致的。
??② 如果變量先進行了整數提升，但不轉換回原先的類型，那么結果就產生了不同。例如：

char a = 0xF0, b = 4;//a 和 b 被提升至int型再運算 bool c = ((a << b) == 0);printf("(a << b) = %#X, c = %d\n", (a << b), (int) c); // 輸出結果：(a << b) = 0XFFFFFF00, c = 0

??a 和 b 都是 8位的char 型變量，如果不提升，那么如果按照左移的計算，a 左移4位后應該變為0 （高位被移出丟棄，低位補0），但是 a 被提升成 int 型后再左移，結果大大不同，變成了 0XFFFFFF00。這是因為 a 由 char 轉換到 int ，變成0XFFFFFFF0，左移4位后為 0XFFFFFF00。所以 a << b 不等于 0， c 的值為 false。

3. 常用的位運算操作

3.1 二進制位 bit(n)

??通常位運算是對 int 型進行操作，而其他類型如 char, short 等會先提升為 int 再運算。

??一個字節共8位，最低位是第$0$位，最高位是第$7$位。如果是32位的 int 型，則最低位為第$0$位，最高位為第$31$位。

??第$n$位可以通過將 $1$ 左移 $n$ 位得到，如，第$7$位為 1U << 7。

??這里需要使用無符號的$1$是因為，如果有符號數的第31位為1時，擴展到更高的64位時高32位會被1填充，由 0x80000000變成 0xFFFFFFFF80000000，這就不符合要求了，所以生成的值類型應該是無符號數。當然，如果在使用時不考慮與64位的值進行運算，那么使用正常的有符號數即可。

inline unsigned int bit(unsigned int n) {return 1U << n; }

??或者以宏的形式進行定義：

#define bit(n) (1U << (n))

3.2 數二進制形式輸出

??在C語言中，printf()并不能直接將變量以二進制格式輸出。已有的八進制和十六進制格式對于查看二進制數并不直觀。為了可以方便查看二進制位的值，需要自行實現或者借助標準庫函數。

3.2.1 itoa() 函數

??標準庫函數itoa() 能夠將數值轉換成 2~36進制格式的字符串，函數在頭文件 <stdlib.h>中聲明。
??我們可以借助 itoa() 函數來生成二進制格式字符串，然后使用 printf()將其輸出。

#include <stdlib.h> #include <stdio.h>int a = 01237A; char buffer[33];//將 a 轉成二進制格式字符串，存放到buffer[]中 itoa(a, buffer, 2); //輸出字符串,前面帶0b前綴 printf("0b%s\n", buffer);

??itoa() 生成的字符串并不能固定位數，所以如果想輸出固定位數的二進制形式，可以在字符串前輸出相應個數的0，手動補齊位數。

// 輸出二進制數, value:值， nBit:二進制數的位數 void printfBinary(int value, unsigned int nBit) {char buffer[33];_itoa(value, buffer, 2);size_t len = strlen(buffer);//計算需要填充的空位數，如果設置的位數不比實際大，則填充數為0size_t fillNum = (nBit >= len) ? (nBit - len) : 0;printf("0b");//填充字符'0'while (fillNum-- > 0) {printf("0");}//輸出原字符串printf("%s", buffer); }

3.2.2 手動實現二進制格式的輸出

??將對應的二進制位提取出來并輸出，4個為一組，用空格間隔，增加可讀性。

void printBinary(unsigned int num, int nBit) {if (nBit > 32 || nBit <= 0)nBit = 32;for (unsigned int n = nBit; n-- > 0; ) {putchar((((num >> n) & 1) == 0) ? '0' : '1');if (n % 4 == 0)putchar(' ');} }

3.3 對應位置位

??置位即將二進制位置為1。

??利用位或運算 $x|1=1,x|0=x$ 的特性，將原數和對應位和1位或，其它位和0位或的二進制數位或，即可將對應位置位。
??例如，想要將第0位置為1，可以將原數與 0x01做位或運算

a | 0x01;

??如果是想將第 $n$ 位置1，則可以按如下操作

a = a | bit(n); //即 a = a | (1U << n);

??簡寫為

a |= bit(n);

??對多位同時置位，可以先將多個bit位或，然后再和原數位或。

a |= (bit(n1)| bit(n2) | bit(n3));

3.4 對應位清零

??清零即將二進制位變為0。

??若要將某一位清零， 可以利用位與運算 和1位于不變，和0位與得0 的特性，將原數與對應位為0，其它位為1 的二進制數位與即可。
??對應位為0，其它位為1的碼，可以通過將對應的二進制位取反得到 ~bit(n)，如第0位為0，其余位為1的碼：

~0x01 //假設為8位二進制數，0x01為 0000 0001，那么~0x01為 1111 1110

??將第 $n$ 位清零可以按如下操作：

a = a & ~bit(n);

??簡寫為

a &= ~bit(n);

??對多位同時清零，可以將多個bit位或。

a &= ~(bit(n1)| bit(n2) | bit(n3));

3.5 對應位取反

??對應位取反 是利用 按位異或運算 (和1異或取反、和0異或不變) 的特性來進行的。

??通過將原數 $a$ 與 對應位為1、其它位為0)的 $b$ 進行按位異或運算，將 $a$ 中對應位取反的同時，還保持其它位不變 。

??將二進制數的第 $n$ 位取反，只需要將原數與第 $n$ 位為1，其余為0的二進制數進行 按位異或運算 即可。

a = a ^ bit(n);

??簡寫為：

a ^= bit(n);

??對多個位同時取反，可以將多個二進制位用 位或 組合。

a ^= bit(n1) | bit(n2) | bit(n3);

3.6 取二進制位

3.6.1 取二進制位

??取位是利用位與運算 (和1位于不變，和0位與得0) 的特性來進行的，將對應位和1 位與來得到對應位的值。

(bit(n)為 1 << n，即第n位上為1，其余位為0的數)

//取第0位 a & bit(0)//取第3位 a & bit(3)

??如果想同時取多個位，可以通過將二進制數與對應位為1的數位與來得到對應位。這個數可以直接寫，也可以使用 位或運算來構造，如取第0位、第1位和第7位，寫成 bit(n0 異或的方式：

a & (bit(0) | bit(1) | bit(7)) //等價于 a & 0x83

示例：

//取低8位 a & 0xFF//取第8至第15位 a & 0xFF00//取高16位 a & 0xFFFF0000//取偶數位 a & 0x55555555

3.6.2 取兩個二進制數不同的位

??直接用按位異或即可取出兩個二進制數不同的位。

a ^ b

3.6.2 取a為1，b為0的位

??取a為1，b為0的位

a & (~b);

??或者先取差異位，再取位

(a ^ b) & a;

3.7 位逆序

3.7.1 常規位逆序方法

??步驟是不斷地取出原數$a$的最低位并將$a$右移，然后將另一個初始值為0的數$b$左移，并將從$a$取出的最低位放到$b$的最低位上。多次循環后，二進制位將被逆序，復雜度為$O(N)$。

//二進制位逆序 //nBit為原數的位數，函數會截取num的低nBit位，逆序后返回 int bitReverse(int num, unsigned int nBit) {if (nBit > 32)nBit = 32;int ans = 0;while (nBit-- > 0) {ans <<= 1;//將num的最低位取出放到ans的最低位上ans |= num & 1; num >>= 1; }return ans; }

3.7.2 蝴蝶算法

??蝴蝶算法是通過遞歸將二進制位左右分半并進行交換來完成逆序的，如下圖所示：

??左右交換從位置上看，實際上是一部分左移，另一部分右移。往同一個方向移動的位都是移動相同的位數，因此可以把所有要左移的位一次性取出，然后移位即可，右移也是同樣的操作，最后再使用位或將兩部分合并。所以一次交換一步即可完成。
??如8位二進制數的第一次的$\frac{1}{2}交換$， 只需要如下操作即可：

((num >> 4) & 0x0F) | ((num << 4) & 0xF0)

??其中 0x0F 和 0xF0 是用于配合 位與(&) 取對應的二進制位，稱為掩碼。
??也可以先取對應二進制位再移動，但是這樣要保證num為無符號整數，否則當最高位為1時，右移可能會引入多余的1，所以并不推薦先取位再移動。

((num & 0x0F) << 4) | ((unsigned int)(num & 0xF0) >> 4)

??逆序算法中的位交換也可以反著順序來，先以1位為一組，交換相鄰兩組，再以兩位為一組相互交換，再以四位為一組進行交換，直至所有位都為一組。

3.7.2.1 8位二進制數逆序

??8位二進制數的逆序算法如下，屬于常用且較為簡單的算法，可以直接使用固定數值來簡化加速：
?掩碼的變化依次為：

0b11110000, 0b00001111
0b11001100, 0b00110011
0b10101010, 0b01010101

unsigned char byteReverse(unsigned char data) {data = ((data<<4) & 0xF0) | ((data>>4) & 0x0F);data = ((data<<2) & 0xCC) | ((data>>2) & 0x33);data = ((data<<1) & 0xAA) | ((data>>1) & 0x55);return data; }

3.7.2.2 $N$ 位二進制數逆序

??$N$ 位的蝴蝶算法（N只能取2的冪，如32，16， 8等，否則中間無法等分。 int 是32位的,所以 $N$ 最大為32）
??最重要的是如何構造出要移動的位對應的二進制掩碼。我們只需將原來$M$位連續的掩碼右移$\frac{M}{2}$位，再與原來的掩碼按位異或即可得到下一級的掩碼。

??算法實現如下，復雜度為 $O(\log n)$。

unsigned int bitReverse(unsigned int num, unsigned int N = 32) {//先構造低N位的掩碼 unsigned int mask = (N >= 32) ? (0xFFFFFFFF) : ((1U << N) - 1U);num &= mask; //取低N位unsigned int M = N / 2; //生成下一級掩碼需要移動的位數// 當M=0時，下一級掩碼將為全0，此時已逆序完成，可以結束while (M > 0) {//構造每一組中高為1，低為0的位掩碼mask ^= (mask >> M);//每組對半交換num = ((num << M) & mask) | ((num >> M) & ~mask);M /= 2;}return num; }

??掩碼為全0后就已經逆序完成，而且值就不再變化，所以循環至掩碼為 $10101010$ 即可。

3.8 位循環移動

??位循環移動即相當于把所有位看成一個首尾相連的環，一端移出的位會放入另一端。

??位循環移動$n$位，相當于將所有位分割左右兩部分，一部分$n$位，另一部分為$N?n$位($N$為二進制數的總位數)，然后左右對調。因此，我們分別將兩部分移動至對應位置上即可。

??因為無符號數的左移和右移，空位都會被補上0，所以移位后并不需要進行取位，直接左移或右移就能得到對應的位。最后再通過按位或運算將兩部分組合起來即可。
??對于32位的unsigned int型變量，移動的位數可以對32求余，然后分別移動 $n$ 位和 $32?n$ 位，寫法如下所示：

//將32位數num循環右移n位 unsigned int circleRightShift(unsigned int num, unsigned int n) {n %= 32;return (num >> n) | (num << (32 - n)); } //將32位數num循環左移n位 unsigned int circleLeftShift(unsigned int num, unsigned int n) {n %= 32;return (num << n) | (num >> (32 - n)); }

??上面是固定的位數，如果想設置對于8位二進制數，16位二進制數或者其它32位以下其它數，可以再加一個總位數的參數。

??需要注意的是，之前固定位數的移動，空位會自動補0，但現在設置的位數和變量類型實際上不匹配，所以并不會幫你補零，所以在計算前需要將其它位手動清0。并且計算完成后，需要再一次將其它位清零，否則數據會移動至其他高位上。

//將nBit位二進制數num循環右移n位 unsigned int circleRightShift(unsigned int num, unsigned int n, unsigned int nBit) {if (nBit > 32)nBit = 32;//獲取低nBit位的掩碼unsigned int mask = (nBit >= 32) ? (0xFFFFFFFF) : ((1U << nBit) - 1U);num &= mask; //取低nBit位n %= nBit;return ((num >> n) | (num << (nBit - n)) ) & mask; }//將nBit位二進制數num循環左移n位 unsigned int circleLeftShift(unsigned int num, unsigned int n, unsigned int nBit) {if (nBit > 32)nBit = 32;//獲取低nBit位的掩碼unsigned int mask = (nBit >= 32) ? (0xFFFFFFFF) : ((1U << nBit) - 1U);num &= mask; //取低nBit位n %= nBit;return ((num << n) | (num >> (nBit - n)) ) & mask; }

3.9 lowbit運算

??$lowbit$ 運算 是位運算中比較重要的運算方式，用于計算一個二進制數最低位的1。

3.9.1 lowbit概念

??$\mathrm{lowbit}$ 即二進制數最低位1所對應的值。
??如，二進制數 $0b01011000$最低的$1$是在第$3$位，對應值為 $0b1000$。

??我們把數用二進制的形式來表示，如下(左為十進制數，右為二進制數，二進制數用前綴$0b$)：$$\begin{array}{rl}2& =0b00000010\\ 5& =0b00000101\\ 160& =0b10100000\end{array}$$??在上面 $2$, $5$和$160$ 的二進制表達式中，我們直接取最低位的1對應的二進制值，得到
$$\begin{array}{rl}\mathrm{lowbit}(2)& =0b00000010\\ \mathrm{lowbit}(5)& =0b00000001\\ \mathrm{lowbit}(160)& =0b00100000\end{array}$$

??由上面的結果可以得出，假設一個數的二進制表示最低位的1在第$k$位(從右往左，最右邊為第0位)，那么，這個數的$lowbit$值為 $2^k$。
??如下圖，最低位1在第3位上，則 $lowbit$ 值為 $2^3=8$，也就是 $0b1000$。

3.9.2 lowbit運算的實現

??一個數的$\mathrm{lowbit}$值，即一個數的最低位，可通過如下操作取出，復雜度為 $O(1)$：
??假設原來的數是a，對a取反加1得到~a+1，原數a和~a+1進行位與操作，就得到了$\mathrm{lowbit}$值，即lowbit(a) = a & (~a + 1)。

int lowbit(int a) {return a & (~a + 1); }

??因為取反加1就是一個數的相反數的補碼，lowbit也寫作

int lowbit(int a) {return a & (-a); }

??當這個數是0，沒有最低位1的時候，結果將為0。

??所以求 $\mathrm{lowbit}(a)$ 值的運算方法為：$$\mathrm{lowbit}(a)=a\&(～a+1)=a\&(?a)$$

3.9.3 消去lowbit

??一個數消去它的 $\mathrm{lowbit}$ 位，直接減去它的 $\mathrm{lowbit}$值 即可。由上面 $\mathrm{lowbit}$ 的求法，可得：

int removeLowbit(int a) {return a - lowbit(a); //a - (a & -a) }

??還可以由 a & (a-1) 得到：

int removeLowbit(int a) {return a & (a-1); }

??通過不斷進行消除 $\mathrm{lowbit}$ 操作，最后會變成0，并且 0 & (0-1) 依舊為 0。

??既然得到了移除 $\mathrm{lowbit}$ 后的二進制數，那么使用之前的值減去移除 $\mathrm{lowbit}$ 后的值， 就得到了求 $\mathrm{lowbit}$ 的另一種算法：

int lowbit(int a) {return a - (a & (a-1)); // a - removeLowbit(a); }

3.10 highbit運算

??$\mathrm{highbit}$ 即二進制數最高位1所對應的值。
??如，二進制數 $0b01011000$最高的$1$是在第$6$位，對應值為 $0b01000000$。

??$\mathrm{highbit}$ 運算和 $\mathrm{lowbit}$ 運算不同，并不能通過一個簡單計算得到。一般是通過將最高位的1往低位擴散，直至填滿比它低的位，再利用異或操作得到目標位。
??這里先列出代碼，方便后面解釋。

//highbit運算，取最高位的1 unsigned int highbit(unsigned int n) {n |= (n >> 1);n |= (n >> 2);n |= (n >> 4);n |= (n >> 8);n |= (n >> 16);// 如果考慮 int 是64位的情況，那么需要再擴散一次，32位數多擴散一次無影響n |= (n >> 32);return n ^ ((unsigned int)n >> 1); }

3.10.1 位的擴散

??這里的核心操作就是位的“擴散”：將二進制數中比最高位1低的位全部變為1，采用的是右移和位或操作。
??$N$位數完成擴散需要進行至 a |= (a >> (N/2))，如32位數需要進行至 a |= (a >> 16)，8位數需要進行至 a |= (a >> 4)。多次擴散對變量值無影響，8位數也可進行至 a |= (a >> 16)，因為位移會對位寬進行取模，取模后移位數為0，相當于不變。
??擴散的復雜度是 $O(\log \log n)$，這個復雜度通常可視為 $O(1)$，因為變量一般是32位或64位數，運算不超過6次。

// 將二進制數中比最高位1低的位全部變為1 unsigned int bitSpread(unsigned int a) {// 連續進行移位位或a |= (a >> 1);a |= (a >> 2);a |= (a >> 4); // 8位a |= (a >> 8); // 16位a |= (a >> 16); // 32位a |= (a >> 32); // 64位return a; }

3.10.2 利用異或取最高位

??假設二進制數 $a$ 的最高位1在第 $k$ 位上，位擴散完成之后，整個數變成一個 $0～k$ 位都為1的二進制數 $b$，再將其右移，進行 位異或 或者 相減即可得到最高位。

b ^ ((unsigned int) b >> 1U); 或者 b - ((unsigned int) b >> 1U);

??注意這里 b >> 1 雖然是 $0～k?1$ 位都為1的二進制數，但是這里并不是通過加1來得到最高位，而是和 $b$ 進行運算，這是因為如果出現 $b=0$的情況，(b >> 1)+1 將會得到錯誤的結果：1，正確結果應該是0。

3.10.3 highbit運算實現

??最終得到如下的實現代碼，如果 int 是32位數，執行至 n |= (n >> 16) 即可，如果考慮 64位的情況，那么需要多執行一步。

??特別需要注意的是，下面的處理代碼中，即使 n 已經是無符號類型了，依然特意添加一個強轉類型 unsigned int，這是因為上面的 n類型可以是有符號類型 ，但 這一步必須是無符號右移。

unsigned int highbit(unsigned int n) {n |= (n >> 1);n |= (n >> 2);n |= (n >> 4);n |= (n >> 8);n |= (n >> 16);// 如果考慮 int 是64位的情況，那么需要再進行 n |= (n >> 32);// 這里必須是無符號右移return n ^ ((unsigned int)n >> 1); }

3.10.4 擴展：取比給定值大的二進制位

??在將最高位擴散完成后，加1即可得到比給定值大的一個二進制位。

??特殊情況就是二進制數的最高有效位為1(如32位數的第31位為1)，那比它更大的二進制位是無法表示的，32位數沒有第32位。如果最高有效位為1，那么擴散后所有位都會變為1，再加1會變為0。可以根據結果是否為0判斷是否出現溢出的情況。

// 將二進制數中比最高位1低的位全部變為1 unsigned int bitSpread(unsigned int a) {// 連續進行移位位或a |= (a >> 1);a |= (a >> 2);a |= (a >> 4); // 8位a |= (a >> 8); // 16位a |= (a >> 16); // 32位a |= (a >> 32); // 64位return a; }// 計算比n大的二進制位，如果32位數或64位數的最高有效位為1，結果為0 unsigned int largerPowOfTwo(unsigned int n) {return bitSpread(n) + 1U; }

3.10.5 擴展：取不小于給定值的二進制位

3.10.5.1 實現一

??在 3.10.4中，只能得到比給定值大的二進制位，如果想在給定值本身已經是二進制位時，直接返回原值，可以做一下處理：
??① 先判斷原值是否是2的冪(利用 lowbit 運算)，是2的冪直接返回
??② 不是2的冪則按 3.10.4的方法進行處理。

// 判斷數是否是2的次冪 bool isPowerOfTwo(unsigned int a) {// 原數不等于0，且消去lowbit后等于0，即二進制位只有一個1return (a != 0) && ((a & (a-1)) == 0) }// 將二進制數中比最高位1低的位全部變為1 unsigned int bitSpread(unsigned int a) {// 連續進行移位位或a |= (a >> 1);a |= (a >> 2);a |= (a >> 4); // 8位a |= (a >> 8); // 16位a |= (a >> 16); // 32位a |= (a >> 32); // 64位return a; }// 返回大于或等于 n的最小的一個二進制位 // 如果二進制位超出表示范圍，則返回0 unsigned int nearestPowOfTwo(unsigned int n) {if (isPowerOfTwo(n))return n;elsereturn bitSpread(n) + 1U; }

3.10.5.2 實現二

??位擴散后再加1的得到的值是比給定值大的二進制位，我們可以先將原數減1后再進行處理，這樣就可以在給定值本身是二進制位時返回原值。
??將原數減1后再計算，結果超出范圍時會溢出變為0，這個是合理的。但是如果原數為0，計算后得到0 (0不是2的冪，1才是)，這是不符合要求的，需要做特殊處理。

// 將二進制數中比最高位1低的位全部變為1 unsigned int bitSpread(unsigned int a) {// 連續進行移位位或a |= (a >> 1);a |= (a >> 2);a |= (a >> 4); // 8位a |= (a >> 8); // 16位a |= (a >> 16); // 32位a |= (a >> 32); // 64位return a; }// 返回大于或等于 n的最小的一個二進制位 // 如果二進制位超出表示范圍，則返回0 unsigned int nearestPowOfTwo(unsigned int n) {if (n == 0U)return 1U;elsereturn bitSpread(n-1) + 1U; }

??可以對上面的bitSpread()函數 和 nearestPowOfTwo() 函數進行整合，得到一個函數

// 返回大于或等于 n的最小的一個二進制位 // 如果二進制位超出表示范圍，則返回0 unsigned int nearestPowOfTwo(unsigned int num) {unsigned int n = num - 1;n |= (n >> 1);n |= (n >> 2);n |= (n >> 4); // 8位n |= (n >> 8); // 16位n |= (n >> 16); // 32位n |= (n >> 32); // 64位return (num == 0U) ? 1U : (n + 1U); }

4. 位運算的應用

4.1 生成低N位掩碼

??低$N$位掩碼的值等于 $2^N?1$，如低8位掩碼 0xFF 的值為 $255$，等于$2^8?1$，而$2^N$可以通過 1 << N 得到，所以可以通過(1 << N) - 1來求取：

unsigned int mask(unsigned int n) {return (n >= 32) ? (-1) : ((1U << n) - 1); }

??需要注意的是，二進制位全為1的值為 0xFFFFFFFF，即 (0 - 1)，但是移位會對32取模，1 << 32 的值為 1 << 0，即1，并非為0，所以需要特殊處理。

??如果一個二進制數 $a$ 的 $\mathrm{lowbit}$ 在第$N$位，想要生成低$N+1$位的掩碼，可以通過 a ^ (a-1) 得到。但需要注意0的特殊情況，0^(-1)為全1，實際應返回0。

unsigned int maskToLowbit(unsigned int a) {return (a == 0) ? 0 : (a ^ (a-1)); }

4.2 生成從第M位開始的連續N位的掩碼

??可以通過將低$N$位掩碼左移$M$位得到，例如0b00000111 左移4位變成 0b00111000。

??而低$N$位掩碼可以借用上面的 mask()函數 生成，對于固定的某些位可以直接用固定值。

示例：
??生成16位數中高字節的掩碼(即第8至第15位)。

0XFF00 或 (0xFF << 8) 或 mask(8) << 8

4.3 取連續N位的值

??如果連續的 $N$ 位是從第 $n$ 位開始，可以通過將二進制數 右移 $n$ 位來將對應位移至最低位，再和低 $N$ 掩碼位與 就可以得到對應位的值。

示例：
??取32位數中第三個字節的值。第三個字節從第24位開始的8位，所以可以將原數右移24位，然后和低8位掩碼0xFF 做 按位與運算 即可得到對應的值。

(a >> 24) & 0xFF;

4.3.1 先右移再取位，和先取位再右移有什么不同？

??先移位再取位可以不用考慮原來的值是無符號類型還是有符號類型，但先取位再右移的方式需要考慮。
??如果是先對原來的數 num 取位再移位，要保證num為無符號整數，否則當num最高位為1時，移動就會引入多余的位。

??例如，對于有符號8位二進制數 0b11000001，想要取高4位的值，應該得到 0b00001100。

• 如果是先取高4位再右移4位，會變成0b11111100，高位被填補上1，這并不是想要的結果，如果想要不被填補上1，那就得先把 num 轉換成無符號數再右移。

//有符號數和無符號數結果的不同 int8_t num = 0b11000001; (num & 0xF0) >> 4; //得到 0b11111100uint8_t num = 0b11000001 (num & 0xF0) >> 4; //得到 0b00001100//移動前先把num轉換成無符號數 ((uint8_t)num & 0xF0) >> 4;

• 如果是先移位再取位，移位得到 0b11111100，取位得到 0b00001100，結果和預期的一致，不用關心原來num是無符號數還是有符號數。所以推薦先移位再取位。

int8_t num = 0b11000001; (num >> 4) & 0x0F; //得到 0b00001100

示例：
??ARGB顏色通過用32位二進制數來表示，從低字節到高字節依次表示B,G, R, A四個分量，求R分量的值。

(ARGB >> 16) & 0xFF;

4.4 設置某些位的值

??可以通過先使用位與運算將對應位清零，再使用位或運算將對應位置位的方法來達到賦值的目的。

示例：
??將16位數中的高8位賦值為0xA：

a &= ~0xFF00; a |= (0xA << 8);

4.5 位連續翻轉

??取反只能將全部位同時取反，而部分位翻轉可以使用異或運算。

??將對應位和1做異或運算將被取反，而其它位和0異或運算不變。

示例：
??連續翻轉低8位：

a ^= 0xFF; //首次翻轉 a ^= 0xFF; //再次翻轉 ... a ^= 0xFF; //第n次翻轉

4.6 lowbit應用：統計一個二進制數中為1的位數

??統計為1的位數，這個可以通過不斷進行消去 $\mathrm{lowbit}$ 來實現，每次消去一個為1的位，只需記錄變成0所需要的次數即可。

int calcNumOfBit1(unsigned int n) {int count = 0; //初始計數為0//不斷消去lowbit直至值為0while (n != 0) {n &= (n-1);++count;}return count; }

??因為是計算二進制的位數，所以參數需要傳入無符號整數，或者不被擴展字節的數。因為，如果被傳入其它如 short, char 之類的有符號整數，如果最高位為1，擴展后高位將被全部填充1，造成計算錯誤。
??所以在調用前，需要將參數轉成同字節大小的無符號整數。

char a = 0x80; //注意，這個最高位為1的有符號整數，并且比int小 calcNumOfBit1((unsigned char)a); //轉成同大小的無符號整數再調用

??如果是下方的調用，那么a 由1字節的char 擴展到4字節的int(或者unsigned int)，有符號數擴展后高位會被填充1，a由 0x80變成0xFFFFFF80，此時計算出錯誤的值。

char a = 0x80; calcNumOfBit1(a);

4.7 lowbit應用：判斷一個數是否是2的冪

??如果一個數是2的冪，那么為1的二進制位只有1位，可以通過消去一個lowbit后是否為0來判斷，但需要注意，0消去 $\mathrm{lowbit}$ 也為0，所以需要先判斷原數是否為0。

// 判斷數是否是2的冪 bool isPowerOfTwo(unsigned int a) {return (a != 0) && ((a & (a-1)) == 0) }

或者直接使用上面的calcNumOfBit1() 函數來計算二進制位為1的數量：

bool isPowerOfTwo(unsigned int a) {return calcNumOfBit1(a) == 1; }

4.8 lowbit應用：將右邊第一組連續為1的二進制位變為0

??可以使用a & (a+lowbit(a))來消去二進制數右邊連續的為1的位。

a & (a+lowbit(a)); //a & (a + (a & -a))

4.9 將右邊從最低位開始的連續為1的二進制位變為0

a & (a + 1)

4.10 將右邊從最低位開始的連續為0的二進制位變為1

a | (a-1)

??同時，也可以反向操作，先將原數取反，然后去掉右邊從最低位開始的連續的1，再取反回來。這兩個式子其實是一致的，可以相互轉換。

a = ~a; //先取反，將右邊0變為1 ~(a & (a + 1)); //去掉右邊的1再取反回去

4.11 奇偶判斷

??奇數最低位為1，偶數最低位為0，因此可以用按位與運算取出二進制數的最低位，通過最低位是0還是1來判斷出二進制數是奇數還是偶數。

(x & 1) == 1; //奇數判斷, 或者 (x & 1) != 0 (x & 1) == 0; //偶數判斷

4.12 對 $2^k$ 取模

??二進制形式的數對應的十進制數值為：
$$a_{n?1}?2^{n?1}+?+a_2?2^2+a_1?2^1+a_0?2^0$$??其中， $a_k$ 表示二進制形式數在第 $k$ 位$(0?k<n)$上的數值(二進制位上的數值只有0和1)。

??如果一個數要對 $2^k$ 取模，將其寫成二進制形式后，可以發現，不低于 $k$ 的位都能整除以 $2^k$，余數為低 $k$ 位對應的值。
??因此，一個數對 $2^k$ 取模，直接取其二進制形式的低 $k$ 位即可，方法是將其與低$N$位掩碼進行按位與運算：

a & ((1 << k) - 1)

??當然，需要注意的是，上面的代碼無法表示對$2^{32}$取模的操作，因為 $(1<<32)$ 等于 1 而不等于 0。32位數本身就是$2^{32}$的模，所以對$2^{32}$取模可以做特殊處理，直接返回原值即可。

unsigned int mod2(unsigned int a, unsigned int k) {return (k >= 32) ? a : (a & ((1 << k) - 1)); }

??上面代碼中 1<< k即 $2^k$，如果這個值已經作為 $b$ 給出，那么可以寫成

a & (b - 1)

??當 $b=0$ 時，上述式子求得的值和原數相等，相當于對 $2^{32}$取模。

---

專欄：算法

上一篇：（二）基礎運算

下一篇：（四）質數（素數）

總結

以上是生活随笔為你收集整理的（三）位运算的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。