数据结构：找出字符串中重复的字符（Finding Duplicates in a String）——使用位运算_spf合并重复位号
目录
预备知识
左移运算（<<）
位运算
一、从最朴素的方法开始
二、如果只关心“有没有出现过”，不关心“次数”，还能不能更省？
三、有没有一种更“紧凑”的方式表示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 // 原始值是 1y = 00000000 00000000 00000000 00001000 // 变成了 81 × 2^3 = 8
✅ 左移 n 位 就相当于 乘以 2ⁿ
左移的“位图”意义
我们现在不把整数当作“数”，而当作一排开关/位
int mask = 1 << i; // 表示第 i 位是 1，其余是 0mask = 1 << (\'c\' - \'a\'); // 表示字符 \'c\' 的那一位 所以就能精准地表示：字母 \'c\' 这个字符的“标志位”是否应该置 1
位运算
ORing（按位或）
把某一位设置为 1（“合并标记”）
💡 场景：
想要记录：这个字符 已经出现过了
我们通过：
bitmask = bitmask | mask;示例：
bitmask = 00000000 00000000 00000000 00000101mask = 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位是1mask = 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 来构造这个“单个字母对应的位置”
所以我们的问题变成了：
-
有一个整型变量
int bitmask = 0;，代表 26 个字母的状态 -
每个小写字母
\'a\'到\'z\'，分别映射到第 0 位到第 25 位 -
我想对某个字母做两件事：
-
检测它是否已经出现（对应的位是不是 1）
-
标记它出现过（把对应的位设为 1）
-
四、用一个整数的每一位表示一个字母是否出现
第一步：确定某个字符应该对应哪一位（位置）
我们先要知道：\'c\' 应该对应 bitmask 的哪一位？
用以下方式：
int pos = ch - \'a\'; // \'a\' = 0, \'b\' = 1, ..., \'z\' = 25\'ch\' - \'a\'第二步：构造一个“掩码”来访问这一位
我们的问题是：“如何选中第 pos 位？”
我们用左移操作构造：
int mask = 1 << pos;含义是：
-
1 << pos就是一个整数，只有第 pos 位是 1，其他全是 0
第三步：判断该字符是否出现过（读位）
此时我们就可以“检测”：
if ((bitmask & mask) != 0) { // 字符 ch 已经出现过了}解释：
-
bitmask & mask：-
如果该位是 1，结果就是 mask 本身（非 0）
-
如果该位是 0，结果是 0
-
所以我们通过这个判断该字符是否出现。
第四步：标记该字符出现（写位）
如果该位还没有被设置，我们就“标记”它出现过：
bitmask = bitmask | mask;//或者简写为：bitmask |= mask;这会把原来的 bitmask 中的第 pos 位设为 1，其他位保持不变。
第五步：代码实现
1. 忽略非小写字母字符：
if (ch \'z\') continue;2. 把当前字符映射为位索引：
int i = ch - \'a\'; // 假设是小写字母3. 构造一个掩码，代表“我要检查的位”：
int mask = 1 << i; // 只把第 i 位设置为 14. 检查是否已经来过：
if ((checker & mask) > 0) { // 说明这位之前已经是 1，重复了}5. 否则，设置该位为 1：
checker |= mask;完整代码实现（只用于小写字母）
#include 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 \'z\') continue; // 忽略非小写字符 int pos = ch - \'a\'; int mask = 1 < 0) { cout << ch << \" \"; } else { checker |= mask; } } cout << endl;}int main() { const char str[] = \"programming\"; findDuplicatesUsingBits(str); return 0;}
