什么是按位移位(bit-shift)运算符,它们如何工作?

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

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

答案

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

经营者

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

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

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

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

(在包括 gcc 和 clang / LLVM 在内的所有主流 C 和 C ++ 实现中,带符号类型上的>>都是算术运算。一些代码假定这样做,但这不是标准所保证的。但是,它不是undefined ;该标准要求实现定义但是,负号的左移未定义的行为(有符号整数溢出)。因此,除非需要算术右移,否则对无符号类型进行位移位通常是个好主意。)


左移(<<)

整数作为一系列位存储在内存中。例如,存储为 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 的幂次除法。

假设我们只有一个字节:

0110110

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

1101100

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

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

左移 N 等于乘以 2 N。

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

如果您使用的是 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.

编译器将为您执行此操作:查看gcc,clang 和 MSVC 在优化return 320*row + col;如何全部使用 shift + lea return 320*row + col;

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


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

// Byte1: 11110000
// Byte2: 00001111

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

// value = 000011111110000;

在 C ++ 中,如果您使用具有两个 8 位成员的struct ,则编译器应为您执行此操作,但实际上并非总是如此。

位操作(包括位移)是低级硬件或嵌入式编程的基础。如果阅读设备规范甚至某些二进制文件格式,则会看到字节,字和 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 位长,因此我们需要使用右移( #define GREEN_OFFSET 5 = 5)来按比例缩小它,因此使用 5 作为偏移量( #define GREEN_OFFSET 5 )。

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

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

位屏蔽和移位

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

等等,我们有一个整数,代表像素颜色中绿色的数量:

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)。

实际上,通常是后者。

我只是在写技巧和窍门,可能对测试 / 考试有用。

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

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

例如:

(long) 4 >> 65

等于 2。您可能期望将位右移 65 次将所有内容归零,但这实际上等效于:

(long) 4 >> (65 % 64)

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

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

在 Python 中实现了 @Ravi Prakash 答案。

# Basic bit operations
# Int to bin
print(bin(10))

# Bin to int
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 2nd bit is 0

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

请注意,Windows 平台上仅提供 32 位版本的 PHP。

然后,如果您将 <<或>> 移位 31 位以上,则结果是无法预期的。通常,将返回原始数字而不是零,这可能是一个非常棘手的错误。

当然,如果使用 64 位版本的 PHP(Unix),则应避免移位超过 63 位。但是,例如,MySQL 使用 64 位 BIGINT,因此不应存在任何兼容性问题。

更新:从 PHP 7 Windows,PHP 构建最终可以使用完整的 64 位整数:整数的大小取决于平台,尽管通常的最大值约为 20 亿(32 位带符号)。 64 位平台的最大值通常约为 9E18,但 PHP 7 之前的 Windows 始终为 32 位。