预备知识

左移运算（<<）

位运算

一、从最朴素的方法开始

二、如果只关心“有没有出现过”，不关心“次数”，还能不能更省？

三、有没有一种更“紧凑”的方式表示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）
2. 标记它出现过（把对应的位设为 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;
}