除了快速数学之外,有没有什么好理由使用位移？

Question

我理解按位操作以及它们如何用于不同目的,例如权限.但是,我似乎不明白比特移位运算符的用途.我理解他们是如何工作的,但我想不出任何我可能想要使用它们的场景,除非我想做一些非常快速的乘法或除法.有没有其他理由使用位移？

Answer 1

原因有很多,这里有一些:

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

由于这些和其他原因,大多数处理器具有位移和/或旋转指令以及其他逻辑指令(和/或/ xor/not).

历史上,乘法和除法明显较慢,因为它们是更复杂的操作,而某些CPU根本没有那些.

另见这里: 你有没有必要在实际项目中使用位移？

Answer 2

正如您所指出的,左移与乘以2相同.至少在我们谈论无符号数量的时候.签名数量的"左移"的含义是......语言相关的.

使用现代编译器,写"i = x*2"之间真的没有区别 和"i = x << 1;" 编译器将生成最有效的代码.所以从这个意义上来说,没有理由倾向于倍增.

一些算法通过将数量左移一位然后将低位设置为0或1来工作.一些简单的压缩算法以这种方式工作.例如,如果您的累计值在变量x中,并且当前值(0或1)在y中,那么写"x =(x << 1)| y"更有意义,而不是"x" =(x*2)+ y".都做同样的事情,但首先是更notationally正确.你不必想,"哦,对,乘以2与左移相同."

此外,当你谈论移位的算法时,向左或向右移动特定数量的位比向你想要乘以或除以2的倍数更方便.

因此,对于转移而不是倍增通常没有性能上的好处 - 至少在使用高级语言时不是这样 - 有时候有能力转移使得你正在做的事情更容易被理解.

Answer 3

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