位运算的巧思：以一道简单题看高效算法的设计精髓-EW帮帮网

位运算的巧思：以一道简单题看高效算法的设计精髓

问题的提出：哪些字符串是“一致”的？

假设我们有一个允许使用的字符集合 allowed，以及一串待检查的字符串数组 words。我们的目标是统计 words 中有多少个字符串，它们的所有字符都包含在 allowed 集合中。例如：

allowed = "ab", words = ["ad", "bd", "aaab", "baa", "badab"]

在这个例子中，只有 "aaab" 和 "baa" 里的字符都属于 "ab"，因此答案是 2。

最直观的思路，可能是对 allowed 构建一个哈希集合（Set），然后遍历 words 中的每一个字符串，再遍历字符串中的每一个字符，去哈希集合中查找。如果发现任何一个字符不在哈希集合里，则该字符串不符合要求。

// 传统哈希集合解法示意
Set<Character> allowedChars = new HashSet<>();
for (char c : allowed.toCharArray()) {
    allowedChars.add(c);
}

int count = 0;
for (String word : words) {
    boolean consistent = true;
    for (char c : word.toCharArray()) {
        if (!allowedChars.contains(c)) {
            consistent = false;
            break;
        }
    }
    if (consistent) {
        count++;
    }
}

这个方法是正确且易于理解的。它的时间复杂度是 O(m + n * k)，其中 m 是 allowed 的长度，n 是 words 数组的长度，k 是平均字符串长度。对于适中的数据量，这个方法足够了。但有没有更“酷”一点、效率更高一点的方法呢？

位运算的闪光点：用一个整数表示一个字符集

注意到英文字母只有 26 个，这个特性非常适合使用位运算来表示字符集。我们可以用一个整数的 26 个最低位来分别对应字母 ‘a’ 到 ‘z’。如果某个位是 1，就表示对应的字母存在于字符集中；如果位是 0，则表示不存在。

例如：

字符集 {“a”} 可以用二进制 ...0001 (十进制 1) 表示 (‘a’ 对应第 0 位)
字符集 {“b”} 可以用二进制 ...0010 (十进制 2) 表示 (‘b’ 对应第 1 位)
字符集 {“a”, “b”} 可以用二进制 ...0011 (十进制 3) 表示 (‘a’ 和 ‘b’ 对应位都为 1)
字符集 {“a”, “c”} 可以用二进制 ...0101 (十进制 5) 表示 (‘a’ 和 ‘c’ 对应位都为 1)

将一个字符添加到集合中，就相当于将对应位置的位设为 1，这可以通过按位或 (|) 操作实现：mask |= (1 << (c - 'a'))。这里的 (c - 'a') 计算出字符 c 相对于 ‘a’ 的偏移量，即它对应的位数。1 << (c - 'a') 生成一个只有对应位是 1 的整数。

代码解析：巧妙的子集判断

基于这个思想，我们可以对 allowed 字符串构建一个“允许字符掩码” mask。然后，遍历 words 中的每一个字符串 word，也为其构建一个“当前字符串掩码” mask1。

问题的关键就转化为：如何判断 word 的字符集是 allowed 字符集的子集？也就是说，word 中出现的任何字符，在 allowed 中都必须出现。用位掩码来表达就是：mask1 中为 1 的位，在 mask 中也必须为 1。

考虑代码中的这一行判断：

if ((mask1 | mask) == mask) {
    res++;
}

这句代码乍看有点绕，为什么是 (mask1 | mask) == mask 而不是直接比较 mask1 == mask 呢？

原因在于我们判断的是子集关系，而不是完全相等。

让我们用上面的例子来理解：

allowed = "ab", mask = ...0011 (十进制 3)
word = "a", mask1 = ...0001 (十进制 1)

如果直接比较 mask1 == mask (1 == 3)，显然是 false，这不符合我们的要求，因为 “a” 是由 “ab” 中的字符组成的。

现在看 (mask1 | mask)：

mask1 | mask 即 (...0001 | ...0011)
按位或的结果是 ...0011 (十进制 3)

此时 (mask1 | mask) == mask (3 == 3) 成立，判断正确！

再举一个不符合要求的例子：

allowed = "ab", mask = ...0011 (十进制 3)
word = "ac", mask1 = ...0101 (十进制 5)

计算 (mask1 | mask)：

mask1 | mask 即 (...0101 | ...0011)
按位或的结果是 ...0111 (十进制 7)

此时 (mask1 | mask) == mask (7 == 3) 不成立，判断正确，因为 “ac” 包含了不在 “ab” 中的字符 ‘c’。

结论：

mask1 | mask 的结果是包含 mask1 和 mask 中所有为 1 的位。只有当 mask1 中所有为 1 的位在 mask 中也为 1 时（即 mask1 是 mask 的子集），按位或操作并不会引入新的为 1 的位，结果才会和 mask 完全相同。这就是 (mask1 | mask) == mask 判断子集关系的精髓所在。

算法效率分析

使用位运算的方案：

构建 allowed 的掩码：时间复杂度 O(m)
遍历 words 数组：n 次循环
在每次循环中，构建 word 的掩码：时间复杂度 O(k)
位运算判断：时间复杂度 O(1)

总的时间复杂度为 O(m + n * k)，与哈希集合方案看起来相同。然而，位运算在硬件层面执行得非常快，常数时间 O(1) 的操作实际上比哈希集合的查找（平均 O(1)，但有额外的计算和内存开销）要快得多。尤其是在字符串长度 k 相对较小的情况下，位运算的优势更明显。

实际应用场景的联想

位运算的这种巧妙应用不仅仅局限于这道算法题。很多需要表示和操作小型集合、状态标志的场景，都可以考虑使用位运算来提升效率和代码简洁度。比如：

权限管理：用一个整数的各个位表示用户拥有的不同权限，通过位运算快速判断用户是否拥有某项或某组权限。
状态标志：在游戏开发或系统编程中，用一个整数的不同位表示对象的不同状态（如“活动”、“可见”、“已锁定”等），通过位运算快速检查和修改状态。
集合操作：对于元素数量有限的小集合，位运算可以高效地实现集合的并集、交集、差集、子集判断等操作。

总结

通过这道简单的算法题，我们看到了位运算在解决特定问题时的强大能力。它不仅可以将复杂的逻辑用简洁的代码表达，更能利用底层硬件的特性实现高效计算。当我们面对问题时，跳出固有的思维模式，思考数据的特性（比如字符数量有限），并尝试运用计算机基础知识（如位运算），往往能发现意想不到的优化空间，写出更具性能优势的代码。位运算就像一个隐藏的宝藏，等待我们在合适的场景下挖掘和利用。

位运算的巧思：以一道简单题看高效算法的设计精髓