什么是位移(位移)操作符,它们是如何工作的?

我一直在尝试在业余时间学习C语言,而其他语言(C#,Java等)也有相同的概念(通常是相同的操作符)。

我想知道的是,在核心层面,什么是位移(<<,>>,>>>),它能帮助解决什么问题,什么问题在这个弯曲中潜伏着? 换句话说,一个绝对的初学者的指南,其所有的善良位移。

    位移操作员完全按照他们的名字暗示。 他们转移位。 下面是对不同换class经营者的简要介绍(或不是简单的介绍)。

    运营商

    • >>是算术(或有符号)的右移运算符。
    • >>>是逻辑(或无符号)右移运算符。
    • <<是左移运算符,并且满足逻辑和算术移位的需要。

    所有这些运算符都可以应用于整数值( intlong ,可能是shortbytechar )。 在某些语言中,将移位运算符应用于小于int任何数据types会自动将操作数调整为int

    注意<<<不是一个运算符,因为它是多余的。 另请注意,C和C ++不区分右移运算符。 它们只提供>>运算符,而右移行为是为签名types定义的实现。


    左移(<<)

    整数作为一系列位存储在内存中。 例如,存储为32位int的数字6将是:

     00000000 00000000 00000000 00000110 

    将这个位模式转移到左边的一个位置( 6 << 1 )将导致数字12:

     00000000 00000000 00000000 00001100 

    正如你所看到的,数字已经向左移动了一个位置,而最右边的数字被填充了一个零。 你也可以注意到左移相当于乘以2的乘方。所以6 << 1相当于6 * 2 6 << 3相当于6 * 8 。 一个好的优化编译器将尽可能地replace乘法。

    非循环移位

    请注意,这些不是循环class次。 将此值左移一个位置( 3,758,096,384 << 1 ):

     11100000 00000000 00000000 00000000 

    结果3,221,225,472:

     11000000 00000000 00000000 00000000 

    被“移出”的数字丢失了。 它不包裹。


    逻辑右移(>>>)

    一个合乎逻辑的右移是与左移相反的。 他们只是向右移动,而不是向左移位。 例如,将数字12:

     00000000 00000000 00000000 00001100 

    右边一个位置( 12 >>> 1 )将返回原来的位置6:

     00000000 00000000 00000000 00000110 

    所以我们看到向右移动相当于2的幂。

    迷失的一点消失了

    但是,换class不能收回“丢失”的位。 例如,如果我们改变这种模式:

     00111000 00000000 00000000 00000110 

    到左边4个位置( 939,524,102 << 4 ),我们得到2,147,483,744:

     10000000 00000000 00000000 01100000 

    (939,524,102 << 4) >>> 4 )我们得到134,217,734:

     00001000 00000000 00000000 00000110 

    一旦我们失去了位,我们不能恢复原来的价值。


    算术右移(>>)

    算术右移与逻辑右移完全相同,除了用零填充以外,填充最重要的位。 这是因为最重要的位是符号位,或者是区分正数和负数的位。 通过填充最重要的位,算术右移是保持符号的。

    例如,如果我们将此位模式解释为负数:

     10000000 00000000 00000000 01100000 

    我们有-2,147,483,552。 把这个移动到正确的四个位置(-2,147,483,552 >> 4)会给我们:

     11111000 00000000 00000000 00000110 

    或者数字-134,217,722。

    所以我们看到,通过使用算术右移,而不是逻辑右移,我们保留了负数的符号。 而且我们再一次看到我们正在进行两权分立。

    假设我们有一个字节:

     0110110 

    应用一个左移位让我们:

     1101100 

    最左边的零被移出该字节,并且在该字节的右端追​​加了一个新的零。

    位不翻转; 他们被丢弃。 这意味着,如果您左移1101100,然后右移,则不会得到相同的结果。

    左移N等于乘以2 N。

    向右移动N(如果使用的是补码 )等于除以2 N并舍入为零。

    偏移可以用于疯狂的快速乘法和除法,只要你正在使用2的幂。几乎所有的低级graphics例程使用偏移。

    例如,在过去的时代,我们使用模式13h(320×200 256色)进行游戏。 在模式13h中,video存储器按照每个像素顺序排列。 这意味着要计算一个像素的位置,你可以使用下面的math公式:

     memoryOffset = (row * 320) + column 

    现在,在那个时代,速度是至关重要的,所以我们会用位移来做这个操作。

    然而,320并不是二的力量,所以为了解决这个问题,我们必须找出两个加在一起的力量是320:

     (row * 320) = (row * 256) + (row * 64) 

    现在我们可以把它转换成左移:

     (row * 320) = (row << 8) + (row << 6) 

    最终结果如下:

     memoryOffset = ((row << 8) + (row << 6)) + column 

    现在我们得到和以前相同的偏移量,除了代替昂贵的乘法运算,我们使用了两个位移…在x86中,它会是这样的(注意,从我做完程序集到现在一直是这样(编者注:校正几个错误,并添加了一个32位的例子)):

     mov ax, 320; 2 cycles mul word [row]; 22 CPU Cycles mov di,ax; 2 cycles add di, [column]; 2 cycles ; di = [row]*320 + [column] ; 16-bit addressing mode limitations: ; [di] is a valid addressing mode, but [ax] isn't, otherwise we could skip the last mov 

    总计:在任何古代CPU有这些时间的28个周期。

    VRS

     mov ax, [row]; 2 cycles mov di, ax; 2 shl ax, 6; 2 shl di, 8; 2 add di, ax; 2 (320 = 256+64) add di, [column]; 2 ; di = [row]*(256+64) + [column] 

    在同一个古老的CPU上有12个周期。

    是的,我们将努力削减16个CPU周期。

    在32位或64位模式下,两个版本都变得更短更快。 像Intel Skylake(参见http://agner.org/optimize/ )这样的现代无序执行CPU具有非常快的硬件乘法(低延迟和高吞吐量),所以增益要小得多。 AMD推土机系列有点慢,特别是对于64位的乘法。 在Intel CPU和AMD Ryzen上,两次转换的延迟稍微低一些,但比乘法的指令要多(这可能会导致较低的吞吐量):

     imul edi, [row], 320 ; 3 cycle latency from [row] being ready add edi, [column] ; 1 cycle latency (from [column] and edi being ready). ; edi = [row]*(256+64) + [column], in 4 cycles from [row] being ready. 

     mov edi, [row] shl edi, 6 ; row*64. 1 cycle latency lea edi, [edi + edi*4] ; row*(64 + 64*4). 1 cycle latency add edi, [column] ; 1 cycle latency from edi and [column] both being ready ; edi = [row]*(256+64) + [column], in 3 cycles from [row] being ready. 

    编译器会为你做这件事情:看优化return 320*row + col;时,gcc,clang和MSVC如何使用shift + lea return 320*row + col;

    这里最值得注意的是x86有一个移位和加法指令( LEA ) ,它可以执行小的左移,同时添加性能和add指令。 ARMfunction更强大:任何指令的一个操作数可以左右移位。 因此,通过一个已知是2的乘方的编译时常量进行缩放可能比乘法更有效。


    好吧,回到现代…现在更有用的东西就是使用位移来存储16位整数中的两个8位值。 例如,在C#中:

     // Byte1: 11110000 // Byte2: 00001111 Int16 value = ((byte)(Byte1 >> 8) | Byte2)); // value = 000011111110000; 

    在C ++中,编译器应该为你做这个,如果你使用两个8位成员的结构,但实际上并不总是如此。

    按位操作(包括位移)是低级硬件或embedded式编程的基础。 如果你阅读一个设备的规范,甚至一些二进制文件格式,你会看到字节,单词和双字,分解成非字节alignment的位域,其中包含各种感兴趣的值。 访问这些位域来读/写是最常见的用法。

    在graphics编程中一个简单的实例是一个16位像素表示如下:

      bit | 15| 14| 13| 12| 11| 10| 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | | Blue | Green | Red | 

    为了获得绿色价值,你可以这样做:

      #define GREEN_MASK 0x7E0 #define GREEN_OFFSET 5 // Read green uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET; 

    说明

    为了获得从偏移量5开始并以10结束(即6位长)的绿色的值,需要使用(位)掩码,该掩码在应用于整个16位像素时将产生只有我们感兴趣的位。

     #define GREEN_MASK 0x7E0 

    适当的掩码是0x7E0,二进制是0000011111100000(十进制为2016)。

     uint16_t green = (pixel & GREEN_MASK) ...; 

    要应用蒙版,请使用AND运算符(&)。

     uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET; 

    在应用掩码后,最终会得到一个16位的数字,这个数字实际上只是一个11位的数字,因为它的MSB位于第11位。 绿色实际上只有6位长,所以我们需要使用右移(11 – 6 = 5)来缩放,因此使用5作为偏移量( #define GREEN_OFFSET 5 )。

    通常使用比特移位进行快速乘法和除以2的幂除法:

      i <<= x; // i *= 2^x; i >>= y; // i /= 2^y; 

    Bit Masking&Shifting

    位移通常用于低级graphics编程。 例如,以32位字编码的给定像素颜色值。

      Pixel-Color Value in Hex: B9B9B900 Pixel-Color Value in Binary: 10111001 10111001 10111001 00000000 

    为了更好地理解,用什么部分标记的相同二进制值表示什么颜色部分。

      Red Green Blue Alpha Pixel-Color Value in Binary: 10111001 10111001 10111001 00000000 

    比方说,我们想要得到这个像素颜色的绿色值。 我们可以很容易地通过掩饰转移来获得这个价值。

    我们的面具:

      Red Green Blue Alpha color : 10111001 10111001 10111001 00000000 green_mask : 00000000 11111111 00000000 00000000 masked_color = color & green_mask masked_color: 00000000 10111001 00000000 00000000 

    逻辑&运算符确保只保留掩码为1的值。 我们现在要做的最后一件事是通过将所有这些位右移16位(逻辑右移)来获得正确的整数值。

      green_value = masked_color >>> 16 

    Etvoilá,我们有整数表示像素颜色中的绿色数量:

      Pixels-Green Value in Hex: 000000B9 Pixels-Green Value in Binary: 00000000 00000000 00000000 10111001 Pixels-Green Value in Decimal: 185 

    这通常用于编码或解码像jpgpng等图像格式。

    一个问题是,以下是依赖于实现(根据ANSI标准):

     char x = -1; x >> 1; 

    x现在可以是127(01111111)或者仍然是-1(11111111)。

    实际上,通常是后者。

    请注意,在Java实现中,要移位的位数由源的大小来修改。

    例如:

     (long) 4 >> 65 

    等于2.你可能期望将位向右移65次将会把所有东西都归零,但实际上它相当于:

     (long) 4 >> (65 % 64) 

    <<,>>和>>>都是如此。 我还没有用其他语言尝试过。

    我只写技巧和窍门,可能在testing/考试中发现有用。

    1. n = n*2n = n<<1
    2. n = n/2n = n>>1
    3. 检查n是否为2(1,2,4,8,…)的幂:check !(n & (n-1))
    4. 获取第nnn |= (1 << x)

    请注意,在Windows平台上只能使用32位版本的PHP。

    那么,如果你比<<或>>多了31位,结果是不可能的。 通常原来的数字,而不是零将返回,这可能是一个非常棘手的错误。

    当然,如果你使用64位版本的PHP(unix),你应该避免移位超过63位。 但是,例如,MySQL使用64位的BIGINT,所以不应该有任何兼容性问题。

    更新:从PHP7的Windows,PHP版本终于能够使用完整的64位整数:整数的大小是平台相关的,虽然约20亿的最大值是通常的值(这是32位签名)。 64位平台的最大值通常为9E18,除了PHP 7之前的Windows,其总是32位。