引言

大家好，我是GISer Liu😁，一名熱愛AI技術(shù)的GIS開發(fā)者。本系列文章是我跟隨DataWhale 2024年9月學(xué)習(xí)賽的LeetCode學(xué)習(xí)總結(jié)文檔；本文主要講解 位運(yùn)算算法。💕💕😊

---

一、 位運(yùn)算簡(jiǎn)介

1.什么是位運(yùn)算？

① 位運(yùn)算的定義

位運(yùn)算（Bit Operation）是指直接對(duì)整數(shù)的二進(jìn)制位進(jìn)行操作的運(yùn)算。在計(jì)算機(jī)內(nèi)部，所有的數(shù)據(jù)都是以二進(jìn)制形式存儲(chǔ)的，因此位運(yùn)算可以直接操作這些二進(jìn)制位，從而實(shí)現(xiàn)一些高效的計(jì)算。

② 優(yōu)勢(shì)：提高程序性能

位運(yùn)算的優(yōu)勢(shì)在于其高效性。由于位運(yùn)算是直接對(duì)二進(jìn)制位進(jìn)行操作，不需要進(jìn)行復(fù)雜的數(shù)值轉(zhuǎn)換，因此在某些情況下，使用位運(yùn)算可以顯著提高程序的性能。例如，在處理大量數(shù)據(jù)或需要頻繁進(jìn)行位操作的場(chǎng)景中，位運(yùn)算可以大大減少計(jì)算時(shí)間。

2.二進(jìn)制數(shù)的基本概念

① 二進(jìn)制數(shù)的表示方法

二進(jìn)制數(shù)（Binary）是由 0 和 1 兩個(gè)數(shù)碼組成的數(shù)。在計(jì)算機(jī)中，所有的數(shù)據(jù)最終都會(huì)被轉(zhuǎn)換為二進(jìn)制形式進(jìn)行存儲(chǔ)和處理。

② 二進(jìn)制數(shù)的位（Bit）

在二進(jìn)制數(shù)中，每一個(gè) 0 或 1 被稱為一個(gè)位（Bit）。位是二進(jìn)制數(shù)的最小單位，多個(gè)位組合在一起可以表示更大的數(shù)值。

① 二進(jìn)制與十進(jìn)制的區(qū)別

• 十進(jìn)制：由 0 到 9 共 10 個(gè)數(shù)碼組成，進(jìn)位規(guī)則是“滿十進(jìn)一”。例如，7 + 2 = 9，9 + 2 = 11。
• 二進(jìn)制：由 0 和 1 兩個(gè)數(shù)碼組成，進(jìn)位規(guī)則是“逢二進(jìn)一”。例如，1 + 0 = 1，1 + 1 = 10。

② 二進(jìn)制的進(jìn)位規(guī)則：逢二進(jìn)一

在二進(jìn)制中，當(dāng)某一位的數(shù)值達(dá)到 2 時(shí)，就會(huì)向高位進(jìn)一。例如：

• 1 + 0 = 1
• 1 + 1 = 10（相當(dāng)于十進(jìn)制的 2）
• 10 + 1 = 11（相當(dāng)于十進(jìn)制的 3）

③ 示例：二進(jìn)制數(shù)的加法

讓我們通過一個(gè)簡(jiǎn)單的例子來(lái)理解二進(jìn)制數(shù)的加法：

  101 (二進(jìn)制)
+ 011 (二進(jìn)制)
------1000 (二進(jìn)制)

在這個(gè)例子中：

• 最低位 1 + 1 = 10，結(jié)果是 0，進(jìn)位 1。
• 第二位 0 + 1 + 進(jìn)位 1 = 10，結(jié)果是 0，進(jìn)位 1。
• 第三位 1 + 0 + 進(jìn)位 1 = 10，結(jié)果是 0，進(jìn)位 1。
• 最高位只有進(jìn)位 1，結(jié)果是 1。

最終結(jié)果是 1000，即十進(jìn)制的 8。

---

3. 二進(jìn)制數(shù)的轉(zhuǎn)換

① 二進(jìn)制轉(zhuǎn)十進(jìn)制

轉(zhuǎn)換方法：按權(quán)展開

將二進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)的方法是按權(quán)展開。每一位的權(quán)值是 2 的冪次方，從右到左依次為 2^0, 2^1, 2^2, …。

示例：二進(jìn)制數(shù) 01101010 轉(zhuǎn)換為十進(jìn)制

二進(jìn)制數(shù)：01101010
按權(quán)展開：
0 * 2^7 + 1 * 2^6 + 1 * 2^5 + 0 * 2^4 + 1 * 2^3 + 0 * 2^2 + 1 * 2^1 + 0 * 2^0
= 0 + 64 + 32 + 0 + 8 + 0 + 2 + 0
= 106

所以，二進(jìn)制數(shù) 01101010 轉(zhuǎn)換為十進(jìn)制數(shù)是 106。

② 十進(jìn)制轉(zhuǎn)二進(jìn)制

轉(zhuǎn)換方法：除二取余，逆序排列

將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)的方法是“除二取余，逆序排列”。具體步驟如下：

1. 將十進(jìn)制數(shù)不斷除以 2，記錄每次的余數(shù)。
2. 將所有余數(shù)逆序排列，得到二進(jìn)制數(shù)。

示例：十進(jìn)制數(shù) 106 轉(zhuǎn)換為二進(jìn)制

106 ÷ 2 = 53 余 053 ÷ 2 = 26 余 126 ÷ 2 = 13 余 013 ÷ 2 = 6  余 16 ÷ 2 = 3  余 03 ÷ 2 = 1  余 11 ÷ 2 = 0  余 1

將余數(shù)逆序排列，得到 1101010。由于二進(jìn)制數(shù)通常從高位開始，所以最終結(jié)果是 01101010。

所以，十進(jìn)制數(shù) 106 轉(zhuǎn)換為二進(jìn)制數(shù)是 01101010。

通過這些步驟，我們可以理解位運(yùn)算的基本概念和二進(jìn)制數(shù)的轉(zhuǎn)換方法。接下來(lái)，我們將深入探討位運(yùn)算的具體操作。

二、位運(yùn)算基礎(chǔ)操作

1.按位與運(yùn)算（AND）

① 運(yùn)算符：&

按位與運(yùn)算使用符號(hào) & 表示。它是一種雙目運(yùn)算符，即需要兩個(gè)操作數(shù)。

② 運(yùn)算規(guī)則

按位與運(yùn)算的規(guī)則是：只有當(dāng)兩個(gè)二進(jìn)位都為 1 時(shí)，結(jié)果位才為 1。否則，結(jié)果位為 0。

具體規(guī)則如下：

• 1 & 1 = 1
• 1 & 0 = 0
• 0 & 1 = 0
• 0 & 0 = 0

③ 示例

讓我們通過一個(gè)具體的例子來(lái)理解按位與運(yùn)算：

  01111100
& 00111110
----------00111100

逐位進(jìn)行與運(yùn)算：

• 第 1 位：0 & 0 = 0
• 第 2 位：0 & 1 = 0
• 第 3 位：1 & 1 = 1
• 第 4 位：1 & 1 = 1
• 第 5 位：1 & 1 = 1
• 第 6 位：1 & 1 = 1
• 第 7 位：1 & 1 = 1
• 第 8 位：0 & 0 = 0

最終結(jié)果是 00111100。

2. 按位或運(yùn)算（OR）

① 運(yùn)算符：|

按位或運(yùn)算使用符號(hào) | 表示。它也是一種雙目運(yùn)算符，需要兩個(gè)操作數(shù)。

② 運(yùn)算規(guī)則

按位或運(yùn)算的規(guī)則是：只要有一個(gè)二進(jìn)位為 1，結(jié)果位就為 1。否則，結(jié)果位為 0。

具體規(guī)則如下：

• 1 | 1 = 1
• 1 | 0 = 1
• 0 | 1 = 1
• 0 | 0 = 0

③ 示例：

下面通過一個(gè)具體的例子來(lái)理解按位或運(yùn)算：

  01001010
| 01011011
----------01011011

逐位進(jìn)行或運(yùn)算：

• 第 1 位：0 | 1 = 1
• 第 2 位：1 | 1 = 1
• 第 3 位：0 | 0 = 0
• 第 4 位：0 | 1 = 1
• 第 5 位：1 | 1 = 1
• 第 6 位：0 | 0 = 0
• 第 7 位：1 | 1 = 1
• 第 8 位：0 | 1 = 1

最終結(jié)果是 01011011。

3. 按位異或運(yùn)算（XOR）

① 運(yùn)算符：^

按位異或運(yùn)算使用符號(hào) ^ 表示。它也是一種雙目運(yùn)算符，需要兩個(gè)操作數(shù)。

② 運(yùn)算規(guī)則

按位異或運(yùn)算的規(guī)則是：對(duì)應(yīng)的兩個(gè)二進(jìn)位相異時(shí)，結(jié)果位為 1，相同時(shí)為 0。

具體規(guī)則如下：

• 1 ^ 1 = 0
• 1 ^ 0 = 1
• 0 ^ 1 = 1
• 0 ^ 0 = 0

③ 示例

下例中我們理解按位異或運(yùn)算：

  01001010
^ 01000101
----------00001111

逐位進(jìn)行異或運(yùn)算：

• 第 1 位：0 ^ 1 = 1
• 第 2 位：1 ^ 0 = 1
• 第 3 位：0 ^ 0 = 0
• 第 4 位：0 ^ 0 = 0
• 第 5 位：1 ^ 0 = 1
• 第 6 位：0 ^ 1 = 1
• 第 7 位：1 ^ 0 = 1
• 第 8 位：0 ^ 1 = 1

最終結(jié)果是 00001111。

4. 取反運(yùn)算（NOT）

① 運(yùn)算符：~

取反運(yùn)算使用符號(hào) ~ 表示。它是一種單目運(yùn)算符，只需要一個(gè)操作數(shù)。

② 運(yùn)算規(guī)則

取反運(yùn)算的規(guī)則是：將 1 變?yōu)?0，0 變?yōu)?1。

具體規(guī)則如下：

• ~0 = 1
• ~1 = 0

③ 示例

讓我們通過一個(gè)具體的例子來(lái)理解取反運(yùn)算：

~01101010
----------
10010101

逐位進(jìn)行取反運(yùn)算：

• 第 1 位：~0 = 1
• 第 2 位：~1 = 0
• 第 3 位：~1 = 0
• 第 4 位：~0 = 1
• 第 5 位：~1 = 0
• 第 6 位：~0 = 1
• 第 7 位：~1 = 0
• 第 8 位：~0 = 1

最終結(jié)果是 10010101。

5. 左移運(yùn)算（SHL）

① 運(yùn)算符：<<

左移運(yùn)算使用符號(hào) << 表示。它是一種雙目運(yùn)算符，需要一個(gè)操作數(shù)和一個(gè)移位次數(shù)。

② 運(yùn)算規(guī)則

左移運(yùn)算的規(guī)則是：將二進(jìn)制數(shù)的各個(gè)二進(jìn)位全部左移若干位，高位丟棄，低位補(bǔ) 0。

③ 示例：01101010 左移 1 位

讓我們通過一個(gè)具體的例子來(lái)理解左移運(yùn)算：

01101010 << 1
----------
11010100

逐位進(jìn)行左移運(yùn)算：

• 第 1 位：0 移出，高位丟棄
• 第 2 位：1 移到第 1 位
• 第 3 位：1 移到第 2 位
• 第 4 位：0 移到第 3 位
• 第 5 位：1 移到第 4 位
• 第 6 位：0 移到第 5 位
• 第 7 位：1 移到第 6 位
• 第 8 位：0 移到第 7 位
• 低位補(bǔ) 0

最終結(jié)果是 11010100。

6. 右移運(yùn)算（SHR）

① 運(yùn)算符：>>

右移運(yùn)算使用符號(hào) >> 表示。它也是一種雙目運(yùn)算符，需要一個(gè)操作數(shù)和一個(gè)移位次數(shù)。

② 運(yùn)算規(guī)則

右移運(yùn)算的規(guī)則是：將二進(jìn)制數(shù)的各個(gè)二進(jìn)位全部右移若干位，低位丟棄，高位補(bǔ) 0。

③ 示例：01101010 右移 1 位

讓我們通過一個(gè)具體的例子來(lái)理解右移運(yùn)算：

01101010 >> 1
----------
00110101

逐位進(jìn)行右移運(yùn)算：

• 第 8 位：0 移出，低位丟棄
• 第 7 位：1 移到第 8 位
• 第 6 位：0 移到第 7 位
• 第 5 位：1 移到第 6 位
• 第 4 位：0 移到第 5 位
• 第 3 位：1 移到第 4 位
• 第 2 位：1 移到第 3 位
• 第 1 位：0 移到第 2 位
• 高位補(bǔ) 0

最終結(jié)果是 00110101。

---

三、 位運(yùn)算的應(yīng)用

1. 位運(yùn)算的常用操作

① 判斷整數(shù)奇偶

原理：通過與 1 進(jìn)行按位與運(yùn)算

判斷一個(gè)整數(shù)是奇數(shù)還是偶數(shù)，可以通過與 1 進(jìn)行按位與運(yùn)算。如果結(jié)果為 0，則該數(shù)為偶數(shù)；如果結(jié)果為 1，則該數(shù)為奇數(shù)。

示例：判斷 x 是奇數(shù)還是偶數(shù)

def is_even(x):return (x & 1) == 0def is_odd(x):return (x & 1) == 1# 示例
x = 10
print(f"{x} 是偶數(shù)嗎？", is_even(x))  # 輸出：True
print(f"{x} 是奇數(shù)嗎？", is_odd(x))   # 輸出：False

思維流程

② 二進(jìn)制數(shù)選取指定位

原理：使用按位與運(yùn)算

要選取二進(jìn)制數(shù)中的某幾位，可以使用按位與運(yùn)算。通過構(gòu)造一個(gè)掩碼（mask），掩碼中對(duì)應(yīng)選取位置為 1，其余位置為 0，然后與原二進(jìn)制數(shù)進(jìn)行按位與運(yùn)算。

示例：取二進(jìn)制數(shù) 01101010 的末尾 4 位

def get_last_n_bits(x, n):mask = (1 << n) - 1return x & mask# 示例
x = 0b01101010
n = 4
result = get_last_n_bits(x, n)
print(f"二進(jìn)制數(shù) {bin(x)} 的末尾 {n} 位是 {bin(result)}")  # 輸出：0b1010

思維流程

③ 將指定位設(shè)置為 1

原理：使用按位或運(yùn)算

要將二進(jìn)制數(shù)中的某幾位設(shè)置為 1，可以使用按位或運(yùn)算。通過構(gòu)造一個(gè)掩碼，掩碼中對(duì)應(yīng)選取位置為 1，其余位置為 0，然后與原二進(jìn)制數(shù)進(jìn)行按位或運(yùn)算。

**示例：將二進(jìn)制數(shù) 01101010 的末尾 4 位設(shè)置為 **1

def set_last_n_bits(x, n):mask = (1 << n) - 1return x | mask# 示例
x = 0b01101010
n = 4
result = set_last_n_bits(x, n)
print(f"二進(jìn)制數(shù) {bin(x)} 的末尾 {n} 位設(shè)置為 1 后是 {bin(result)}")  # 輸出：0b1111

④ 反轉(zhuǎn)指定位

原理：使用按位異或運(yùn)算

要反轉(zhuǎn)二進(jìn)制數(shù)中的某幾位，可以使用按位異或運(yùn)算。通過構(gòu)造一個(gè)掩碼，掩碼中對(duì)應(yīng)選取位置為 1，其余位置為 0，然后與原二進(jìn)制數(shù)進(jìn)行按位異或運(yùn)算。

示例：將二進(jìn)制數(shù) 01101010 的末尾 4 位反轉(zhuǎn)

def invert_last_n_bits(x, n):mask = (1 << n) - 1return x ^ mask# 示例
x = 0b01101010
n = 4
result = invert_last_n_bits(x, n)
print(f"二進(jìn)制數(shù) {bin(x)} 的末尾 {n} 位反轉(zhuǎn)后是 {bin(result)}")  # 輸出：0b1100

⑤ 交換兩個(gè)數(shù)

原理：使用按位異或運(yùn)算

通過按位異或運(yùn)算可以實(shí)現(xiàn)兩個(gè)數(shù)的交換，而無(wú)需額外的變量。

示例：交換 a 和 b 的值

def swap_numbers(a, b):a ^= bb ^= aa ^= breturn a, b# 示例
a, b = 10, 20
a, b = swap_numbers(a, b)
print(f"交換后 a = {a}, b = {b}")  # 輸出：a = 20, b = 10

思維流程圖

⑥ 將二進(jìn)制最右側(cè)為 1 的二進(jìn)位改為 0

**原理：使用 **X & (X - 1)

要將二進(jìn)制數(shù)中最右側(cè)為 1 的二進(jìn)位改為 0，可以使用 X & (X - 1) 操作。

**示例：將 01101100 最右側(cè)的 1 改為 **0

def clear_rightmost_bit(x):return x & (x - 1)# 示例
x = 0b01101100
result = clear_rightmost_bit(x)
print(f"二進(jìn)制數(shù) {bin(x)} 最右側(cè)的 1 改為 0 后是 {bin(result)}")  # 輸出：0b1101000

⑦ 計(jì)算二進(jìn)制中二進(jìn)位為 1 的個(gè)數(shù)

原理：使用 X & (X - 1) 統(tǒng)計(jì)次數(shù)

通過不斷使用 X & (X - 1) 操作，可以將二進(jìn)制數(shù)中最右側(cè)為 1 的二進(jìn)位改為 0，直到所有位都為 0。統(tǒng)計(jì)操作次數(shù)，即可得到二進(jìn)制中 1 的個(gè)數(shù)。

示例：計(jì)算 01101100 中 1 的個(gè)數(shù)

def count_ones(x):count = 0while x:x &= (x - 1)count += 1return count# 示例
x = 0b01101100
result = count_ones(x)
print(f"二進(jìn)制數(shù) {bin(x)} 中 1 的個(gè)數(shù)是 {result}")  # 輸出：4

思維流程

⑧ 判斷某數(shù)是否為 2 的冪次方

**原理：使用 **X & (X - 1) == 0

判斷一個(gè)數(shù)是否為 2 的冪次方，可以通過 X & (X - 1) == 0 來(lái)實(shí)現(xiàn)。如果結(jié)果為 0，則該數(shù)是 2 的冪次方；否則，不是。

示例：判斷 4 是否為 2 的冪次方

def is_power_of_two(x):return (x & (x - 1)) == 0# 示例
x = 4
result = is_power_of_two(x)
print(f"{x} 是 2 的冪次方嗎？ {result}")  # 輸出：True

思維流程

2. 位運(yùn)算的常用操作總結(jié)

① 常用操作列表

功能	位運(yùn)算符	示例
判斷整數(shù)奇偶	&	(x & 1) == 0
選取指定位	&	x & ((1 << n) - 1)
將指定位設(shè)置為 1	`	`
反轉(zhuǎn)指定位	^	x ^ ((1 << n) - 1)
交換兩個(gè)數(shù)	^	a ^= b; b ^= a; a ^= b;
將最右側(cè) 1 改為 0	&	x & (x - 1)
計(jì)算 1 的個(gè)數(shù)	&	while x: x &= (x - 1); count += 1
判斷是否為 2 的冪次方	&	(x & (x - 1)) == 0

3. 二進(jìn)制枚舉子集

① 二進(jìn)制枚舉子集簡(jiǎn)介

子集的概念

子集是指一個(gè)集合中的任意元素都是另一個(gè)集合的元素。例如，集合 {1, 2, 3} 的子集包括 {}、{1}、{2}、{3}、{1, 2}、{1, 3}、{2, 3}、{1, 2, 3}。

二進(jìn)制枚舉子集的原理

對(duì)于一個(gè)元素個(gè)數(shù)為 n 的集合 S，可以用一個(gè)長(zhǎng)度為 n 的二進(jìn)制數(shù)來(lái)表示其子集。每一位對(duì)應(yīng)集合中的一個(gè)元素，1 表示選取該元素，0 表示不選取該元素。通過枚舉 0 到 2^n - 1 的所有二進(jìn)制數(shù)，可以得到集合 S 的所有子集。

② 二進(jìn)制枚舉子集代碼

代碼實(shí)現(xiàn)：枚舉集合 S 的所有子集

def subsets(S):n = len(S)sub_sets = []for i in range(1 << n):sub_set = []for j in range(n):if i & (1 << j):sub_set.append(S[j])sub_sets.append(sub_set)return sub_sets# 示例
S = [1, 2, 3]
result = subsets(S)
print(f"集合 {S} 的所有子集是 {result}")  # 輸出：[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

思維流程圖

Ok，今天我們就學(xué)習(xí)到這！😎👌

---

相關(guān)鏈接

• 項(xiàng)目地址：LeetCode-CookBook
• 相關(guān)文檔：專欄地址
• 作者主頁(yè)：GISer Liu-CSDN博客

如果覺得我的文章對(duì)您有幫助，三連+關(guān)注便是對(duì)我創(chuàng)作的最大鼓勵(lì)！或者一個(gè)star🌟也可以😂.