0

我经常遇到涉及排序/未排序数组的面试问题，他们要求您找到该数组的某种属性。例如查找数组中出现奇数次的数字，或者在大小为一百万的未排序数组中查找缺失的数字。通常，问题会带来额外的约束，例如 O(n) 运行时复杂度或 O(1) 空间复杂度。使用逐位操作可以非常有效地解决这两个问题。当然这些还不是全部，这样的问题还有很多。

对我来说，按位编程似乎更像是基于黑客或直觉的，因为它以二进制而不是十进制工作。作为一个没有太多实际编程经验的大学生，我很好奇这类问题在实际工作中是否真的很流行，或者它们只是面试官用来选择最聪明的候选人的脑筋急转弯。如果它们确实有用，它们实际上适用于什么样的场景？

4

4 回答 4

3

逐位运算在实际编程中是否常见且有用？

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

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

一些例子：

  1. 您通过直接操作显存来设置屏幕上的单个像素，其中每个像素的颜色由 1 位或 4 位表示。因此，在每个字节中，您可以打包 8 或 2 个像素，您需要将它们分开。基本上，您的硬件决定了按位运算的使用。

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

  3. 您需要计算某种校验和（可能是奇偶校验或CRC）或哈希值，而一些最适用的算法通过使用位进行操作来做到这一点。

  4. 您正在实现（或使用）一个任意精度的算术库。

  5. 您正在实现FFT，您自然需要在整数中反转位或在添加时模拟相反方向的进位传播。该算法的性质需要一些按位操作。

  6. 您的空间不足，需要使用尽可能少的内存，并且您将多个位值和位组压缩到整个字节、字、双字和四字中。您选择使用按位运算来节省空间。

  7. CPU 上的分支/跳转代价高昂，您希望通过将代码实现为一系列没有任何分支的指令来提高性能，而逐位指令可以提供帮助。这里最简单的示例是从两个整数中选择最小（或最大）整数值。最自然的实现方式是使用某种if语句，最终涉及比较和分支。您选择使用按位运算来提高速度。

  8. 您的 CPU 支持浮点运算，但计算平方根之类的运算速度很慢，您可以使用一些快速简单的整数和浮点运算来模拟它。同样在这里，您可以从处理浮点格式的位表示中受益。

  9. OR您正在模拟 CPU 或整台计算机，并且在解码指令、访问 CPU 或硬件寄存器的一部分、简单地模拟诸如、AND、XOR、NOT等按位指令时，您需要操纵单个位（或位组） 。您的问题完全需要逐位说明。

  10. 您正在向网络（例如此处）或书中的其他人解释按位算法或技巧或需要按位操作的东西。:)

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

于 2013-04-09T08:47:27.947 回答
0

Using Bitwise Operations is strictly Dependent on your main concerns.

I was once asked to solve a problem to find the all combinations of numbers which don't

have a repeating digit within them , which are of form N*i, for a given i.

I suddenly made use of bitwise operations and generated all the numbers exactly with better

time , But to my surprise I was asked to rewrite and code with the no use of the Bitwise

Operators , as people find no readability with that , the code which many people has to use

in further . So, If performance is your concern go for Bitwise .

If readability is your concern reduce their use.

If you want both at time , you need to follow a good style of writing code with bitwise

operators in a way it was readable or understandable .

于 2013-04-09T07:44:50.890 回答
0

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

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

对于热代码中的一些优化，它也非常方便，您希望使用无分支实现可以用条件代码表示的东西，但需要更快的运行时性能。例如，找到给定整数的最接近 2 的幂可以在某些处理器上非常有效地实现，使用比更常见的解决方案的 bit hack。

有一本名为“Hacker's Delight”Henry S. Warren Jr. 的好书，其中包含非常有用的函数，可解决“现实世界”代码中出现的各种问题。网上也有很多类似的文档。

另一个例子是1970 年代 MIT AI 实验室的一份著名文件HAKMEM。

于 2013-04-09T08:27:08.057 回答
0

根据我的经验，当您以大型数据集的速度和效率为目标时，它非常有用。

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

于 2013-04-09T01:28:50.700 回答