位运算的巧思：以一道简单题看高效算法的设计精髓
位运算的巧思：以一道简单题看高效算法的设计精髓
问题的提出：哪些字符串是“一致”的？
力扣1684. 统计一致字符串的数目
假设我们有一个允许使用的字符集合 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 相对较小的情况下，位运算的优势更明显。
实际应用场景的联想
位运算的这种巧妙应用不仅仅局限于这道算法题。很多需要表示和操作小型集合、状态标志的场景，都可以考虑使用位运算来提升效率和代码简洁度。比如：
- 权限管理：用一个整数的各个位表示用户拥有的不同权限，通过位运算快速判断用户是否拥有某项或某组权限。
- 状态标志：在游戏开发或系统编程中，用一个整数的不同位表示对象的不同状态（如“活动”、“可见”、“已锁定”等），通过位运算快速检查和修改状态。
- 集合操作：对于元素数量有限的小集合，位运算可以高效地实现集合的并集、交集、差集、子集判断等操作。
总结
通过这道简单的算法题，我们看到了位运算在解决特定问题时的强大能力。它不仅可以将复杂的逻辑用简洁的代码表达，更能利用底层硬件的特性实现高效计算。当我们面对问题时，跳出固有的思维模式，思考数据的特性（比如字符数量有限），并尝试运用计算机基础知识（如位运算），往往能发现意想不到的优化空间，写出更具性能优势的代码。位运算就像一个隐藏的宝藏，等待我们在合适的场景下挖掘和利用。