10

我了解按位运算以及它们如何用于不同的目的，例如权限。但是，我似乎不明白位移运算符的用途。我理解它们是如何工作的，但我想不出任何我想使用它们的场景，除非我想做一些非常快速的乘法或除法。还有其他使用位移的原因吗？

4

4 回答 4

15

有很多原因，这里有一些：

  1. 假设您将黑白图像表示为一系列位，并且您想在该图像中设置一个像素。例如，您的字节偏移量可能是 x>>3，而您的位偏移量可能是 x & 0x7，您可以通过以下方式设置该位：byte = byte | (1 << (x & 0x7));
  2. 实现处理可变长度位序列的数据压缩算法，例如霍夫曼编码。
  3. 您正在与一些硬件进行交互，例如串行通信设备，并且您需要读取或设置一些控制位。

由于这些和其他原因，大多数处理器具有位移和/或旋转指令以及其他逻辑指令（和/或/异或/非）。

从历史上看，乘法和除法的速度要慢得多，因为它们是更复杂的运算，而某些 CPU 根本没有这些运算。

另请参阅此处： 您是否曾经在实际项目中使用过位移？

于 2010-09-11T23:08:45.597 回答
7

正如您所指出的，左移与乘以 2 相同。至少在我们谈论无符号数量时是这样。有符号数量的“左移”的含义是......语言相关。

使用现代编译器，写“i = x*2;”之间真的没有区别 和“i = x << 1;” 编译器将生成最有效的代码。所以从这个意义上说，没有理由更喜欢移位而不是乘法。

一些算法通过将数量左移一位然后将低位设置为 0 或 1 来工作。一些简单的压缩算法以这种方式工作。例如，如果您的累加值在变量 x 中，而当前值（0 或 1）在 y 中，那么写“x = (x << 1) | y”比“x”更有意义= (x * 2) + y"。两者都做同样的事情，但第一个在符号上更正确。您不必想，“哦，对，乘以 2 与左移相同。”

此外，当您谈论移位位的算法时，向左或向右移位特定数量的位比计算要乘以或除以 2 的倍数更方便。

因此，虽然移位而不是乘法通常不会带来性能优势——至少在使用高级语言时不会——但有时，具有移位的能力会使你正在做的事情更容易理解。

于 2010-09-11T23:08:13.120 回答
6

除了在数值计算中的使用之外，还有很多地方经常使用移位操作。例如，Bitboard是棋盘游戏中常用的一种数据结构，用于棋盘表示。一些最强大的国际象棋引擎使用这种数据结构主要是为了提高移动生成和评估的速度和便利性。这些程序大量使用位操作，并且位移位操作在很多情况下都有使用 - 例如查找位掩码、在棋盘上生成新的移动、非常快速地计算对数等。甚至可以进行非常先进的数值计算通过巧妙地使用位操作优雅地完成。看看这个网站对于小技巧 - 很多算法都使用移位运算符。移位操作经常用于设备驱动程序编程、编解码器开发、嵌入式系统编程等。

于 2010-09-11T23:15:58.777 回答
2

移位允许访问变量中的特定位。该表达式(n >> p) & ((1 << m) - 1)检索m变量的一个 -bit 部分，该部分具有从右侧n偏移的位。p

这允许您的程序使用不是 8 位倍数的整数，这对于数据压缩很有用。

例如，我在我的Netflix Prize程序中使用它来将记录（22 位用户 ID + 15 位电影 ID + 12 位日期 + 3 位评级）打包成一个uint64_t（有 12 位备用）。

一个非常常见的特殊情况是将 8 个变量打包bool到每个字节中。（Unix 文件权限、黑白位图、CPU 标志寄存器等）

此外，位操作用于UTF-8，这是一种非常流行的字符编码。Unicode 字符通过将它们的位分布在 1、2、3 或 4 个字节上来表示。

于 2010-09-11T23:43:04.517 回答