我一直在尝试业余时间学习C，而其他语言(C＃，Java等)具有相同的概念(并且通常具有相同的运算符)...

我想知道的是，在核心层面上，移位(<<，>>，>>>)有什么作用，它可以帮助解决什么问题，以及弯腰潜伏着什么陷阱？换句话说，这是一个绝对的初学者指南，它对所有好处都有益。

解决方案

假设我们只有一个字节：

0110110

应用左移一个位可以使我们：

1101100

最左边的零被移出字节，并且新的零被添加到字节的右端。

这些位不翻转；他们被丢弃。这意味着，如果左移1101100，然后右移，我们将不会获得相同的结果。

左移N等于乘以2N。

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

如果我们使用的是2的幂，则位移可以用于疯狂的快速乘法和除法。几乎所有低级图形例程都使用位移。

例如，回想起过去，我们在游戏中使用模式13h(320x200 256色)。在模式13h中，视频存储器按像素顺序排列。这意味着要计算像素的位置，我们可以使用以下数学公式：

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个周期。

虚拟现实

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这样的现代无序执行CPU(请参阅http://agner.org/optimize/)具有非常快的硬件乘法(低延迟和高吞吐量)，因此收益要小得多。 AMD Bulldozer系列的速度较慢，尤其是对于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。

这里要注意的最有趣的事情是x86拥有移位加法指令(LEA)，该指令可以执行小的左移并同时加法，其性能与and" add"指令相同。 ARM甚至更强大：任何指令的一个操作数都可以免费向左或者向右移位。因此，用已知为2的幂的编译时常数进行缩放甚至比乘法更有效。

好的，回到现代……现在，更有用的方法是使用移位将两个8位值存储在16位整数中。例如，在C＃中：

// Byte1: 11110000
// Byte2: 00001111

Int16 value = ((byte)(Byte1 >> 8) | Byte2));

// value = 000011111110000;

在C ++中，如果我们将" struct"与两个8位成员一起使用，则编译器应为我们执行此操作，但实际上并非总是如此。

一个陷阱是，以下内容取决于实现(根据ANSI标准)：

char x = -1;
x >> 1;

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

实际上，通常是后者。

移位运算符完全按照其名称的含义进行操作。他们移位。这是对不同移位运算符的简短介绍(或者不太简短)。

经营者

• " >>"是算术(或者有符号)右移运算符。
• " >>>"是逻辑(或者无符号)右移运算符。
• " <<"是左移位运算符，可以满足逻辑和算术移位的需求。

所有这些运算符都可以应用于整数值(" int"，" long"，可能是" short"和" byte"或者" char")。在某些语言中，将移位运算符应用于小于" int"的任何数据类型会自动将操作数的大小调整为" int"。

注意<<<不是运算符，因为它将是多余的。还要注意，C和C ++不能区分右移运算符。它们仅提供>>运算符，并且右移行为是为有符号类型定义的实现。

左移(<<)

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

00000000 00000000 00000000 00000110

将此位模式移至左侧一个位置(" 6 << 1")将得出数字12：

00000000 00000000 00000000 00001100

如我们所见，数字向左移动了一个位置，而右边的最后一个数字则填充了零。我们可能还会注意到，向左移动等效于乘以2的幂。因此，" 6 << 1"等效于" 6 * 2"，而" 6 << 3"等效于" 6 * 8"。一个好的优化编译器将在可能的情况下用移位代替乘法。

非圆移位

请注意，这些不是循环移位。将这个值向左移动一个位置(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的幂。

丢失的位不见了

但是，移位不能收回"丢失"的位。例如，如果我们改变这种模式：

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)将其右移4个位置将得到：

11111000 00000000 00000000 00000110

或者数字-134,217,722.

因此，我们看到通过使用算术右移而不是逻辑右移来保留负数的符号。再一次，我们看到我们正在执行2的幂除法。

按位运算(包括位移)是低级硬件或者嵌入式编程的基础。如果阅读设备规范甚至某些二进制文件格式，则会看到字节，字和dword分解为非字节对齐的位字段，其中包含感兴趣的各种值。访问这些位域以进行读/写是最常见的用法。

图形编程中一个简单的真实示例是一个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位。 Green实际上只有6位长，因此我们需要通过向右移位(11 6 = 5)来缩小比例，因此使用5作为偏移量(#define GREEN_OFFSET 5`)。

同样常见的是使用移位进行2的乘方快速乘法和除法：

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