数据结构：找出字符串中重复的字符（Finding Duplicates in a String）——使用位运算

目录

预备知识

左移运算（<<）

位运算 

一、从最朴素的方法开始

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

三、有没有一种更“紧凑”的方式表示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

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 来构造这个“单个字母对应的位置”

所以我们的问题变成了：

• 有一个整型变量 int bitmask = 0;，代表 26 个字母的状态

• 每个小写字母 'a' 到 'z'，分别映射到第 0 位到第 25 位

• 我想对某个字母做两件事：

  1. 检测它是否已经出现（对应的位是不是 1）

  2. 标记它出现过（把对应的位设为 1）

四、用一个整数的每一位表示一个字母是否出现

第一步：确定某个字符应该对应哪一位（位置）

我们先要知道：'c' 应该对应 bitmask 的哪一位？

用以下方式：

int pos = ch - 'a';  // 'a' = 0, 'b' = 1, ..., 'z' = 25

第二步：构造一个“掩码”来访问这一位

我们的问题是：“如何选中第 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 < '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;
}