bitwise-operators - 位移运算符

Question

遇到这样一道编程面试题。但对我来说，你怎么知道可以在这里使用位移位并​​不明显。好心人解释一下。谢谢。

数组的大小为 N，整数介于 0 和 1024 之间(允许重复)。另一个整数数组的大小为 M，对数字没有限制。找出第一个数组的哪些元素存在于第二个数组中。 (如果您正在使用额外的内存，请考虑使用按位运算符将其最小化)

我想知道位移运算符在现实世界中的含义。以及如何识别需要移位方法的问题。

谢谢桑杰

Answer 1

这真的是一个非常简单的面试问题。因为您知道第一组中最多有 1025 个不同的整数，所以您可以使用该位数来表示是否在输入集中找到了这些数字中的每一个。因此，如果您希望答案只打印一次不同的数字，逻辑是:

• 将位集 A 中的所有 1025 位清零
• 对于第一组中的每个数，设置A中的对应位
• 将位集 B 中的所有 1025 位清零
• 对于第二组中的每个数字，设置B中的相应位
• 对于从 0 到 1024 的 i:如果在 A 和 B 中都设置了该位，则输出 i 作为答案的一部分

现在，您的语言可能不直接支持创建 1025 位的位集，因此有时您需要做的是使用一个字节数组，每个字节有 8 位。然后，假设你想设置位“k”，你会在索引 k/8 处找到字节，然后在位置 k % 8 处设置位。要执行后者，你必须从位位置(0 到7) 到位值(位 0 表示值 1，位 1 值 2，位 2 值 4...位 7 值 128 - 2 的所有幂)。要获得这些值，您需要将数字 1 向左移动“位位置”。所以，1 << 0 仍然是 1，而 1 << 7 是 128。然后你可以:

• 通过将移位后的值与字节值进行“与”运算并查看是否得到非 0 结果来询问字节是否具有该位 - 例如，在 C 和 C++ 中:if (array[k / 8] & (1 << (k % 8))) ...it's on...
• 通过将值与字节进行或运算，在字节中的特定位位置记录 1 - 在 C 和 C++ 中:array[k / 8] |= (1 << (k % 8));

如果任一集合中的值恰好少于 1025 个，则有更有效的方法来执行此操作，但这是一个很好的通用解决方案。