language-agnostic - 什么是按位移位（bit-shift）运算符，它们是如何工作的？

Question

我一直在尝试在业余时间学习 C，其他语言（C#、Java 等）具有相同的概念（并且通常是相同的运算符）...

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

score 1814 · Accepted Answer

位移运算符的作用与它们的名字所暗示的完全一样。他们移动位。这是对不同班次运算符的简要（或不那么简要）介绍。

运营商

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

所有这些运算符都可以应用于整数值（int, long, 可能short和byteor char）。在某些语言中，将移位运算符应用于小于int自动将操作数调整为int.

请注意，这<<<不是运算符，因为它是多余的。

另请注意，C 和 C++ 不区分右移运算符。它们仅提供>>运算符，并且右移行为是为有符号类型定义的实现。答案的其余部分使用 C#/Java 运算符。

（在包括 GCC 和 Clang/LLVM 在内的所有主流 C 和 C++ 实现中，>>有符号类型是算术的。一些代码假设这一点，但这不是标准所保证的。但它不是undefined；标准要求实现来定义它方式或另一种方式。但是，负符号数的左移是未定义的行为（有符号整数溢出）。因此，除非您需要算术右移，否则使用无符号类型进行位移通常是个好主意。）

左移 (<<)

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

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 的幂除法。

score 220 · Accepted Answer

假设我们有一个字节：

应用单个左位移可以得到：

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

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

左移 N 相当于乘以 2 ^N。

右移 N 是（如果您使用的是补码）相当于除以 2 ^N并四舍五入为零。

只要您使用 2 的幂，移位可以用于非常快速的乘法和除法。几乎所有低级图形例程都使用移位。

例如，在过去，我们在游戏中使用模式 13h（320x200 256 色）。在模式 13h 中，视频内存按像素顺序排列。这意味着要计算像素的位置，您将使用以下数学：

memoryOffset = (row * 320) + column

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

但是，320 不是 2 的幂，所以要解决这个问题，我们必须找出什么是 2 的幂，加起来就是 320：

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

现在我们可以将其转换为左移：

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

对于最终结果：

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

现在我们得到了和以前一样的偏移量，除了不是昂贵的乘法运算，我们使用两个位移...几个错误并添加了一个 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（参见http://agner.org/optimize/ ）这样的现代乱序执行 CPU具有非常快的硬件乘法（低延迟和高吞吐量），因此增益要小得多。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.

编译器会为您做到这一点：了解GCC、Clang 和 Microsoft Visual C++ 在优化return 320*row + col;.

这里需要注意的最有趣的一点是，x86有一个移位和加法指令LEAadd（ARM 更强大：任何指令的一个操作数都可以自由地左移或右移。因此，通过已知为 2 的幂的编译时间常数进行缩放可能比乘法更有效。

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

// Byte1: 11110000
// Byte2: 00001111

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

// value = 000011111110000;

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

score 109 · Accepted Answer

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

图形编程中一个简单的真实示例是一个 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;

解释

为了获得 green ONLY 的值，它从偏移量 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;

score 56 · Accepted Answer

位屏蔽和移位

位移位常用于低级图形编程。例如，以 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

例如，假设我们想要获取该像素颜色的绿色值。我们可以通过mask和shift轻松获得该值。

我们的面具：

                  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

等等，我们有一个整数表示像素颜色中绿色的数量：

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

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

score 28 · Accepted Answer

一个问题是以下内容取决于实现（根据 ANSI 标准）：

char x = -1;
x >> 1;

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

在实践中，通常是后者。

score 25 · Accepted Answer

我只写提示和技巧。它可能在测试和考试中很有用。

n = n*2：n = n<<1
n = n/2：n = n>>1
检查 n 是否为 2 的幂（1,2,4,8,...）：检查!(n & (n-1))
获得^第x位：nn |= (1 << x)
检查 x 是偶数还是奇数：（x&1 == 0偶数）
切换x 的^第n位：x ^ (1<<n)

score 8 · Accepted Answer

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

例如：

(long) 4 >> 65

等于 2。您可能希望将位向右移动 65 次会将所有内容归零，但实际上相当于：

(long) 4 >> (65 % 64)

这适用于 <<、>> 和 >>>。我还没有用其他语言尝试过。

score 5 · Accepted Answer

位运算符用于执行位级别的操作或以不同的方式操作位。发现按位运算要快得多，并且有时用于提高程序的效率。基本上，位运算符可以应用于整数类型：long、int、short、char和byte。

移位运算符

它们分为左移和右移两类。

左移（<<）： 左移运算符，将值中的所有位向左移动指定的次数。语法：值 << 数字。这里 num 指定左移 value 中的值的位置数。也就是说，<< 将指定值中的所有位向左移动 num 指定的位位置数。对于每个左移，高位被移出（并被忽略/丢失），并在右侧带入零。这意味着当向 32 位编译器应用左移时，一旦移过位位置 31，位就会丢失。如果编译器是 64 位的，那么位位置 63 之后的位就会丢失。

输出： 6，这里 3 的二进制表示为 0...0011（考虑 32 位系统），因此当它移动一次时，前导零被忽略/丢失，其余 31 位向左移动。最后添加零。所以它变成了 0...0110，这个数字的十进制表示是 6。

在负数的情况下：

输出： -2，在 java 中为负数，用 2 的补码表示。所以，-1 由 2^32-1 表示，相当于 1....11（考虑 32 位系统）。当移位一次时，前导位被忽略/丢失，其余 31 位向左移位，最后添加零。所以它变成了 11...10，它的十进制等价物是 -2。所以，我认为你对左移及其工作方式有足够的了解。

Right Shift(>>)：右移运算符，将值中的所有位向右移动指定的次数。语法：value >> num, num 指定将 value 中的值右移的位置数。也就是说，>> 将指定值中的所有位向右移动/移位 num 指定的位数。以下代码片段将值 35 向右移动两个位置：

输出： 8，由于 32 位系统中 35 的二进制表示是 00...00100011，所以当我们将其右移两次时，前 30 个前导位被移动/移动到右侧，两个低位位丢失/忽略，并在前导位添加两个零。所以，它变成了 00....00001000，这个二进制表示的十进制等价物是 8。或者有一个简单的数学技巧来找出以下代码的输出：为了概括这一点，我们可以说，x >> y = 地板（x/pow（2，y））。考虑上面的例子，x=35 和 y=2 所以，35/2^2 = 8.75，如果我们取底值，那么答案是 8。

输出：

但是请记住一件事，如果您采用较大的 y 值，则此技巧适用于较小的 y 值，它会给您不正确的输出。

在负数的情况下：由于负数，右移运算符以有符号和无符号两种模式工作。在有符号右移运算符（>>）中，如果是正数，则用 0 填充前导位。如果是负数，则用 1 填充前导位。保持符号。这称为“符号扩展”。

输出： -5，正如我上面解释的，编译器将负值存储为 2 的补码。因此，-10 表示为 2^32-10 并且考虑到 32 位系统 11....0110 以二进制表示。当我们移位/移动一次时，前 31 个前导位在右侧移动，而低位丢失/忽略。所以，它变成了 11...0011 并且这个数字的十进制表示是 -5（我怎么知道数字的符号？因为前导位是 1）。有趣的是，如果将 -1 右移，结果始终保持为 -1，因为符号扩展不断在高位中引入更多的位。

无符号右移（>>>）：此运算符也向右移动位。有符号和无符号之间的区别在于，如果数字为负数，后者用 1 填充前导位，而在任何一种情况下，前者都填充零。现在问题出现了，如果我们通过有符号右移运算符获得所需的输出，为什么我们需要无符号右操作。通过一个例子来理解这一点，如果你正在移动不代表数值的东西，你可能不希望发生符号扩展。当您使用基于像素的值和图形时，这种情况很常见。在这些情况下，无论初始值是什么，您通常都希望将零移到高位。

输出： 2147483647，因为 -2 在 32 位系统中表示为 11...10。当我们将位移动一位时，前 31 个前导位向右移动/移位，低位丢失/忽略，并将零添加到前导位。因此，它变为 011...1111 (2^31-1)，其十进制等效值为 2147483647。

score 4 · Accepted Answer

Python中一些有用的位操作/操作。

我用 Python 实现了Ravi Prakash 的答案。

# Basic bit operations
# Integer to binary
print(bin(10))

# Binary to integer
print(int('1010', 2))

# Multiplying x with 2 .... x**2 == x << 1
print(200 << 1)

# Dividing x with 2 .... x/2 == x >> 1
print(200 >> 1)

# Modulo x with 2 .... x % 2 == x & 1
if 20 & 1 == 0:
    print("20 is a even number")

# Check if n is power of 2: check !(n & (n-1))
print(not(33 & (33-1)))

# Getting xth bit of n: (n >> x) & 1
print((10 >> 2) & 1) # Bin of 10 == 1010 and second bit is 0

# Toggle nth bit of x : x^(1 << n)
# take bin(10) == 1010 and toggling second bit in bin(10) we get 1110 === bin(14)
print(10^(1 << 2))

score 2 · Accepted Answer

移位运算符移动二进制对象的位值。左操作数指定要移位的值。右操作数指定值中的位要移动的位置数。结果不是左值。两个操作数具有相同的优先级并且是从左到右关联的。

Operator     Usage

 <<           Indicates the bits are to be shifted to the left.

 >>           Indicates the bits are to be shifted to the right.

每个操作数必须具有整数或枚举类型。编译器对操作数执行整数提升，然后将右操作数转换为 int 类型。结果与左操作数具有相同的类型（在算术转换之后）。

右操作数不应具有负值或大于或等于要移位的表达式的位宽度的值。对这些值进行按位移位的结果是不可预测的。

如果右操作数的值为 0，则结果是左操作数的值（在通常的算术转换之后）。

<< 运算符用零填充空出的位。例如，如果 left_op 的值为 4019，则 left_op 的位模式（16 位格式）为：

0000111110110011

表达式 left_op << 3 产生：

0111110110011000

表达式 left_op >> 3 产生：

0000000111110110

score -3 · Accepted Answer

请注意，在 Windows 平台上只有 32 位版本的 PHP 可用。

然后，例如，如果您将 << 或 >> 移动 31 位以上，则结果出乎意料。通常会返回原始数字而不是零，这可能是一个非常棘手的错误。

当然，如果您使用 64 位版本的 PHP（Unix），则应避免移位超过 63 位。但是，例如，MySQL 使用 64 位 BIGINT，因此不应该有任何兼容性问题。

更新：从 PHP 7 Windows 开始，PHP 构建最终能够使用完整的 64 位整数：整数 的大小取决于平台，尽管通常值约为 20 亿的最大值（即 32 位有符号）。64 位平台的最大值通常约为 9E18，但在 PHP 7 之前的 Windows 上，它始终为 32 位。