在实际编程中，按位操作是否通用且有用？

Question

我经常遇到涉及排序/未排序数组的面试问题，他们要求您查找此数组的某种属性。例如finding the number that appears odd number of times in an array或find the missing number in an unsorted array of size one million。通常这个问题需要额外的约束，比如O（n）运行时复杂度，或者O（1）空间复杂度。 这两个问题都可以通过按位操作相当有效地解决。当然，这些并不是全部，有很多这样的问题。

对我来说，按位编程似乎更像是基于黑客或直觉，因为它工作在二进制而非小数。作为一名没有太多现实生活编程经验的大学生，我很好奇这种类型的问题在实际工作中是否真正受到欢迎，还是他们只是面试官用来挑选最聪明的候选人的脑筋急转弯。 如果它们确实有用，它们实际上适用于哪种场景？

Answer 1

从我的经验来看，当您为大数据集提高速度和效率时，它非常有用。

为了表示非常大的集合，我使用了很多位向量，这使得存储非常高效，并且非常快速地进行比较和组合等操作。我还发现，位矩阵由于相同的原因非常有用，例如找到大量大二进制矩阵的交点。使用二进制掩码来指定子集也是非常有用的，例如Matlab和Python的Numpy/Scipy使用二进制掩码（本质上是二进制矩阵）来从矩阵中选择元素的子集。

Answer 2

使用按位操作严格取决于您的主要问题。

我曾经要求解决问题，以找到号码哪些没有

具有在其中重复的数字，这是形式的N个的所有组合* 1，对于给定的我。

我突然利用位操作，并产生所有的数字正好与更好

时间，但让我吃惊，我被要求重写和代码与没有使用按位

运营商，如人们发现没有可读性，许多人必须使用的代码

进一步。所以，如果性能是你关心的Bitwise。

如果可读性是您关心的问题，请减少它们的使用。

如果你在时间要两个，你需要遵循编写代码的好作风按位

运营商在某种程度上，它是可读或理解的。

Answer 3

尽管如果你真的不关心它，你通常可以在用户级代码中“避免它”，但它对于内存消耗是一个大问题的情况会很有用。位操作通常是需要的，甚至在处理硬件设备或嵌入式编程时甚至是需要的。

I/O寄存器通常具有多种不同的配置选项，可通过各种标志型位组合进行寻址。或者对于内存相对于现代PC RAM大小受到极大限制的小型嵌入式设备，您可能会习惯于正常工作。

它也是在炎热的代码中的一些优化，要使用一个免费的分支实施的东西，可以使用条件代码来表示很方便，但需要更快的运行时性能。例如，在某些处理器上使用比较常见的解决方案的比特攻击可以非常有效地实现给定整数的2的最近幂。

有一个名为“黑客的喜悦”亨利·沃伦小大书，充满了非常有用的功能，适用于各种发生在“现实世界”的代码问题。还有一些类似的东西在线文件。

从在被称为HAKMEM 20世纪70年代MIT人工智能实验室一位著名的文献是另一个例子。

Answer 4

是位运算常见的和有用的在现实生活中的编程？

共性或适用性取决于手头的问题。

一些现实生活中的项目确实从按位操作中受益。

一些例子：

1. 你在屏幕上直接操纵视频存储器，其中每一个像素的颜色是由1或4位表示设置单个像素。因此，在每个字节中，您可以打包8或2个像素，并且需要将它们分开。基本上，您的硬件决定使用按位操作。

2. 您正在处理某种文件格式（例如GIF）或网络协议，它使用个别位或位组来表示信息片段。您的数据决定使用按位操作。

3. 则需要通过与位操作来计算某种checksum（可能parity或CRC）或hash value和一些最适用的算法做到这一点。

4. 你实现（或使用）的arbitrary-precision arithmetic库。

5. 您正在实施FFT，您自然需要reverse bits in an integer或在添加时模拟相反方向的进位传播。算法的本质需要一些按位操作。

6. 您的空间不足，需要使用尽可能少的内存，并将多个位值和位组压入多个字节，字，双字和四字。您选择使用按位操作来节省空间。

7. CPU上的分支机构/跳转代价高昂，您希望通过将代码作为一系列指令实施而不需要任何分支机构和按位指令来提高性能。这里最简单的例子是选择两个中的最小（或最大）整数值。实现它的最自然的方式是使用某种if声明，最终涉及比较和分支。您选择使用按位操作来提高速度。

8. 您的CPU支持浮点运算，但计算诸如平方根之类的操作是一种缓慢的操作，您改为simulate it using a few fast and simple integer and floating operations。同样，在这里，您可以通过使用浮点格式的位表示来操作。

9. 您正在模拟一个CPU或整个计算机，并且在解码指令时，访问CPU或硬件寄存器的某些部分时，需要处理个别位（或位组），只需模拟按位指令，如OR ，AND,XOR,NOT等等。您的问题不再需要按位指示。

10. 您正在解释按位智能的算法或技巧，或者需要按位操作给网络上其他人（例如此处）或书中的内容。 :)

我在过去的20年里亲自完成了以上所有工作。 YMMV，但。