位移运算符

Question

我遇到了这样一个编程面试问题.但对我来说,如何知道如何在这里使用位移是不明显的.有人好心解释.谢谢.

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

我想知道现实世界中的bitshift运算符是什么意思.以及如何识别需要比特移位方法的问题.

谢谢桑杰

Answer 1

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

• 将bitset A中的所有1025位归零
• 对于第一组中的每个数字,在A中设置相应的位
• 将位集B中的所有1025位置零
• 对于第二组中的每个数字int,在B中设置相应的位
• 对于i从0到1024:如果在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.你可以:

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

如果在任何一组中碰巧有少于1025个值,那么有更有效的方法可以做到这一点,但这是一个很好的通用解决方案.