目錄
預備知識
左移運算（<<）
位運算?
一、從最樸素的方法開始
二、如果只關心“有沒有出現過”，不關心“次數”，還能不能更省？
三、有沒有一種更“緊湊”的方式表示26個開關？
四、用一個整數的每一位表示一個字母是否出現
預備知識
左移運算（<<）
x << n
表示：把整數 x 的二進制表示整體向左移動 n 位
舉例說明：
我們來觀察下面的例子（以 int 為例，32 位）：
int x = 1;00000000 00000000 00000000 00000001
現在我們做左移操作：
int y = x << 3;
意思是把 1 向左移動 3位，得到的新值是 8
為什么？看圖：
x = 00000000 00000000 00000000 00000001 // 原始值是 1
y = 00000000 00000000 00000000 00001000 // 變成了 8
1 × 2^3 = 8
? 左移 n 位 就相當于 乘以 2?
左移的“位圖”意義
我們現在不把整數當作“數”，而當作一排開關/位
int mask = 1 << i; // 表示第 i 位是 1，其余是 0
| i | mask（二進制） | 十進制 |
|---|---|---|
| 0 | 00000000 00000000 00000001 | 1 |
| 1 | 00000000 00000000 00000010 | 2 |
| 2 | 00000000 00000000 00000100 | 4 |
| 3 | 00000000 00000000 00001000 | 8 |
| … | … | … |
| 25 | 00000010 00000000 00000000 | 33554432 |
mask = 1 << ('c' - 'a'); // 表示字符 'c' 的那一位
?所以就能精準地表示：字母 'c' 這個字符的“標志位”是否應該置 1
位運算?
ORing（按位或）
把某一位設置為 1（“合并標記”）
💡 場景：
想要記錄：這個字符 已經出現過了
我們通過：
bitmask = bitmask | mask;
示例：
bitmask = 00000000 00000000 00000000 00000101
mask = 00000000 00000000 00000000 00000100 // 想設置第2位bitmask | mask = 00000000 00000000 00000000 00000101注意：已經是 1 的位不會被改動；為 0 的位被“點亮”
快寫法（更常見）：
bitmask |= mask;
完全等價于 bitmask = bitmask | mask
ANDing（按位與）
檢查某一位是否是 1（“掩碼檢查”）
💡 場景：
想要判斷：這個字符是否 已經出現過
通過：
if ((bitmask & mask) > 0)// 第 i 位是 1，說明已經出現
示例：
bitmask = 00000000 00000000 00000000 00000101 // 第0位和第2位是1
mask = 00000000 00000000 00000000 00000100 // 想查第2位bitmask & mask = 00000000 00000000 00000000 00000100 // 非0 → 出現過
如果該位是 0，則結果為全 0
技術總結：“一個整數的每一位代表一個狀態，我們用按位或 | 來點亮，用按位與 & 來檢測。”
一、從最樸素的方法開始
問題目標
給定一個小寫字母字符串，比如："programming"
我們想找出：哪些字母 出現過不止一次（如：r, g, m）
我們第一時間想到的，是記錄每個字母出現的次數：
-
可以用數組
int count[26]來記錄每個字母是否出現 -
索引通過
'c' - 'a'映射到 0~25（參考：數據結構：找出字符串中重復的字符（Finding Duplicates in a String）——使用哈希表 -CSDN博客
這很好用，但我們接著問：
二、如果只關心“有沒有出現過”，不關心“次數”，還能不能更省？
我們回顧需求：
-
我不在乎你出現了幾次
-
我只想知道你是不是已經來過一次
-
如果再次遇到你，我就說你是重復字符
于是我們意識到：
我不需要記錄次數，只需要記錄「有沒有來過」
那我需要 26 個“是否來過”的記錄
想法：
bool seen[26] = {false};
-
'a'來了 → seen[0] = true -
'g'來了 → seen[6] = true -
再次遇到
'g'，發現 seen[6] == true → 它是重復的！
?這已經是一個優化：我們只用 26 個 bit（布爾量），不記錄次數了。
三、有沒有一種更“緊湊”的方式表示26個開關？
我們再想進一步優化空間：
如果我們有一個可以表示「26個狀態」的結構，我們就能把 seen[26] 合并成一個東西。
你也許會聯想到：
-
一個
bool變量本質上需要 1 字節（8位） -
26 個
bool實際上占用了 26 字節 ≈ 208 bits，但其實我們只需要 26 個 bit 就夠了！
于是我們問：
? 有沒有什么東西，能存儲多個“是/否”狀態？
想一想數字的二進制！
例子：
int x = 0; // 二進制：00000000 00000000 00000000 00000000
這不就是 32 個“是/否”開關嗎？每一位只能是 0 或 1！
我們現在重新定義：
一個 int 類型（32位），我們只用前 26 位，每一位表示一個字母是否已經出現過：
-
變量
int checker = 0; -
每當字符
ch出現時，我們設法標記它的“位置 i”為 1 -
如果下一次這個位置已是 1 → 它是重復的！
我們用 1 << i 來構造這個“單個字母對應的位置”
| 字母 | 位位置 | 說明 |
|---|---|---|
| 'a' | 0 | bit 0 表示 a 是否出現 |
| 'b' | 1 | bit 1 表示 b 是否出現 |
| 'c' | 2 | bit 2 表示 c 是否出現 |
| ... | ... | ... |
| 'z' | 25 | bit 25 表示 z 是否出現 |
所以我們的問題變成了：
-
有一個整型變量
int bitmask = 0;，代表 26 個字母的狀態 -
每個小寫字母
'a'到'z'，分別映射到第 0 位到第 25 位 -
我想對某個字母做兩件事：
-
檢測它是否已經出現（對應的位是不是 1）
-
標記它出現過（把對應的位設為 1）
-
四、用一個整數的每一位表示一個字母是否出現
第一步：確定某個字符應該對應哪一位（位置）
我們先要知道：'c' 應該對應 bitmask 的哪一位？
用以下方式：
int pos = ch - 'a'; // 'a' = 0, 'b' = 1, ..., 'z' = 25
| 字符 | ASCII | 'ch' - 'a' | 位位置 |
|---|---|---|---|
| 'a' | 97 | 0 | 第 0 位 |
| 'c' | 99 | 2 | 第 2 位 |
| 'z' | 122 | 25 | 第 25 位 |
第二步：構造一個“掩碼”來訪問這一位
我們的問題是：“如何選中第 pos 位？”
我們用左移操作構造：
int mask = 1 << pos;
含義是：
-
1 << pos就是一個整數，只有第 pos 位是 1，其他全是 0
| pos | mask（二進制） | 十進制 |
|---|---|---|
| 0 | 00000000 00000000 00000001 | 1 |
| 2 | 00000000 00000000 00000100 | 4 |
| 5 | 00000000 00000000 00100000 | 32 |
第三步：判斷該字符是否出現過（讀位）
此時我們就可以“檢測”：
if ((bitmask & mask) != 0) {// 字符 ch 已經出現過了
}
解釋：
-
bitmask & mask：-
如果該位是 1，結果就是 mask 本身（非 0）
-
如果該位是 0，結果是 0
-
所以我們通過這個判斷該字符是否出現。
?第四步：標記該字符出現（寫位）
如果該位還沒有被設置，我們就“標記”它出現過：
bitmask = bitmask | mask;
//或者簡寫為：
bitmask |= mask;
這會把原來的 bitmask 中的第 pos 位設為 1，其他位保持不變。?
第五步：代碼實現?
1.?忽略非小寫字母字符：
if (ch < 'a' || ch > 'z')continue;
2.?把當前字符映射為位索引：
int i = ch - 'a'; // 假設是小寫字母
?3. 構造一個掩碼，代表“我要檢查的位”：
int mask = 1 << i; // 只把第 i 位設置為 1
4. 檢查是否已經來過：
if ((checker & mask) > 0) {// 說明這位之前已經是 1，重復了
}
5. 否則，設置該位為 1：
checker |= mask;
完整代碼實現（只用于小寫字母）
#include <iostream>
using namespace std;void findDuplicatesUsingBits(const char str[]) {int checker = 0;cout << "重復字符有：";for (int i = 0; str[i] != '\0'; i++) {char ch = str[i];if (ch < 'a' || ch > 'z')continue; // 忽略非小寫字符int pos = ch - 'a';int mask = 1 << pos;if ((checker & mask) > 0) {cout << ch << " ";} else {checker |= mask;}}cout << endl;
}int main() {const char str[] = "programming";findDuplicatesUsingBits(str);return 0;
}
