什么是位移（位移）操作符，它们是如何工作的？

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

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

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

运营商

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

所有这些运算符都可以应用于整数值（ int ， long ，可能是short和byte或char ）。 在某些语言中，将移位运算符应用于小于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

这通常用于编码或解码像jpg ， png等图像格式。

一个问题是，以下是依赖于实现（根据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*2 ： n = n<<1
  2. n = n/2 ： n = n>>1
  3. 检查n是否为2（1,2,4,8，…）的幂：check !(n & (n-1))
  4. 获取第n位n ： n |= (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位。

    Interesting Posts

    为什么C＃编译器把这个！=比较翻译成比较呢？