位移运算符

Question

我遇到了这样一个编程面试问题。但是我不明白怎么知道可以在这里使用位移操作符。 有人能够友善地解释一下吗？谢谢。

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

我想知道位移操作符在现实世界中代表什么。以及如何确定需要位移处理的问题。

谢谢 Sanjay

- bespectacled

---

这个问题所涉及的是“位运算符”，而不是“位移运算符”。这是一个更通用的术语（[请参见维基百科]（http://en.wikipedia.org/wiki/Bitwise_operator））。 - Jeremy

Answer 1

这是一个非常简单的面试问题。因为你知道第一个集合中最多有1025个不同的整数，所以你可以使用这个数字的位数来表示每个数字是否在输入集合中找到。所以，如果你想要答案只打印每个不同的数字一次，那么逻辑就是：

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

现在，创建一个1025位的bitset可能不被你的编程语言直接支持，所以有时你需要使用一个字节数组，每个字节有8位。然后，假设你想设置位“k”，你将找到索引为k / 8的字节，然后设置位置为k％8的位。为了做到这一点，你必须将位位置（0到7）转换为位值（位0表示值1，位1表示值2，位2表示值4...位7表示值128-所有的2的幂）。为了得到这些值，你可以取数字1并将其左移“位位置”。所以，1 << 0仍然是1，而1 << 7是128。然后你可以：

• 通过对移位值和字节值进行AND运算并查看是否得到非零结果来询问一个字节是否具有该位-例如，在C和C++中：if (array[k / 8] & (1 << (k % 8))) ...它是开启的...
• 通过将值与字节进行OR运算在特定的位位置记录1-在C和C++中：array[k / 8] |= (1 << (k % 8));

如果两个集合中有远少于1025个值，那么有更有效的方法来做到这一点，但这是一个很好的通用解决方案。

- Tony Delroy

Answer 2

位移运算符的工作方式如下。想象一下你有一个整数值X。这个X将以二进制形式表示，即1和0。然后根据位移运算符，将移动一定数量的位置。

访问此链接http://www.php.net/manual/en/language.operators.bitwise.php，他们有一些关于这些位移运算符如何工作的示例。

- Gayan Hewa

---

他并不是在一般地询问位运算符，而是在询问它们在现实世界中的应用以及它们与这个问题的相关性。 - Jeremy

是的，但是为了理解底层概念，他首先需要知道位运算符如何工作。 - Gayan Hewa