代码之家  ›  专栏  ›  技术社区  ›  waiwai933

除了快速数学外,是否有充分的理由使用位移?

  •  8
  • waiwai933  · 技术社区  · 14 年前

    我了解位操作,以及它们对于不同目的(例如权限)的用处。然而,我似乎不理解位移位操作符的用途。我知道它们是如何工作的,但是我想不出任何我想使用它们的场景,除非我想做一些真正快速的乘法或除法。使用位移还有其他原因吗?

    4 回复  |  直到 14 年前
        1
  •  11
  •   Community CDub    8 年前

    原因有很多,以下是:

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

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

    从历史上看,乘法和除法的速度明显较慢,因为它们是更复杂的操作,而一些CPU根本没有这些操作。

    这里也看到: Have you ever had to use bit shifting in real projects?

        2
  •  6
  •   Jim Mischel    14 年前

    正如你所指出的,左移位和乘二是一样的。至少在我们讨论无符号数量的时候。有符号数量的“左移位”的意思是…语言依赖。

    在现代编译器中,编写“i=x*2”;和“i=x<<1”;编译器将生成最有效的代码。所以在这个意义上,没有理由更喜欢移位而不是乘法。

    有些算法的工作原理是将一个量左移一位,然后将低位设置为0或1。一些简单的压缩算法就是这样工作的。例如,如果您的累积值在变量x中,而当前值(0或1)在y中,那么写“x=(x<<1)y”比写“x=(x*2)+y”更有意义。两个都做同样的事,但第一个更重要 名义上 对的。你不必想,“哦,对了,乘两等于左移。”

    另外,当你谈论移位的算法时,用一个特定的位数左移或右移比算出你想乘或除的2的倍数更方便。

    因此,虽然通常情况下,转换没有任何性能上的好处,而不是成倍增加(至少在使用高级语言时没有),但有时,具有转换能力会使您所做的事情更容易理解。

        3
  •  4
  •   Goutham    14 年前

    在很多地方,位移操作经常被用于数值计算以外的地方。例如, Bitboard 是一种数据结构,通常在棋盘游戏中用于棋盘表示。一些最强的国际象棋引擎使用这种数据结构主要是为了快速和方便地生成和评估移动。这些程序大量使用位操作,位移位操作专门用于许多环境中,例如查找位掩码、在板上生成新的移动、非常快速地计算对数等。甚至还有非常高级的数值计算,可以通过巧妙地使用位操作优雅地完成。退房 this site 对于比特旋转黑客-许多这些算法使用移位运算符。位移操作通常用于设备驱动程序设计、编解码器开发、嵌入式系统编程等。

        4
  •  1
  •   dan04    14 年前

    移位允许访问变量中的特定位。表达式 (n >> p) & ((1 << m) - 1) 检索一个 m -变量的位部分 n 偏移量为 p 从右边开始。

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

    例如,我在 Netflix Prize 将记录(22位用户ID+15位电影ID+12位日期+3位分级)打包到 uint64_t (12位备用)。

    一个非常常见的特殊情况是打包8 bool 每个字节的变量。(Unix文件权限,黑白位图, CPU flags registers 等)

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