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

我一直在尝试在业余时间学习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位。