什么是按位移位(位移)运算符以及它们如何工作？

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

我想知道是,在核心层,是什么位移(<<,>>,>>>)这样做,可以帮助它什么问题解决,和周围的弯曲什么潜伏的陷阱？换句话说,一个绝对的初学者指导比特移位的所有优点.

比特移位运算符正如其名称所暗示的那样.他们转移位.以下是对不同班次运营商的简要介绍(或不那么简短).

运营商

>> 算术(或签名)右移运算符.

>>> 是逻辑(或无符号)右移运算符.

<< 是左移运算符,满足逻辑和算术移位的需要.

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

请注意,这<<<不是运算符,因为它将是多余的.另请注意,C和C++不区分右移运算符.它们仅提供>>运算符,右移行为是针对签名类型定义的实现.

左移(<<)

整数在内存中存储为一系列位.例如,存储为32位的数字6 >>将是:

00000000 00000000 00000000 00000110

将此位模式移动到左侧的一个位置(int)将导致数字12:

00000000 00000000 00000000 00001100

如您所见,数字向左移动了一个位置,右边的最后一个数字用零填充.您可能还会注意到,向左移位相当于乘以2的幂.所以6 << 1相当于6 << 1,6 * 2等于6 << 3.一个好的优化编译器会在可能的情况下用乘法替换乘法.

非圆形换档

请注意,这些不是循环转换.将此值向左移动一个位置(6 * 8):

11100000 00000000 00000000 00000000

结果为3,221,225,472:

11000000 00000000 00000000 00000000

"失去结束"的数字将丢失.它没有环绕.

逻辑右移(>>>)

逻辑右移与左移相反.它们不是向左移动位,而是向右移动.例如,移动数字12:

00000000 00000000 00000000 00001100

向右移动一个位置(3,758,096,384 << 1)将取回原来的6个:

00000000 00000000 00000000 00000110

所以我们看到向右移动相当于2的幂除法.

丢失的位消失了

但是,班次无法回收"丢失"的位.例如,如果我们改变这种模式:

00111000 00000000 00000000 00000110

在左边4个位置(12 >>> 1),我们得到2,147,483,744:

10000000 00000000 00000000 01100000

然后转回(939,524,102 << 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(如果你使用的是补码)相当于除以2 ^N并舍入为零.

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

例如,回到过去,我们使用模式13h(320x200 256色)进行游戏.在模式13h中,视频存储器按像素顺序布局.这意味着计算像素的位置,您将使用以下数学:

memoryOffset = (row * 320) + column

现在,回到那个时代,速度是至关重要的,所以我们将使用位移来进行此操作.

然而,320不是2的幂,所以为了解决这个问题,我们必须找出加在一起的两个幂是多少才能得到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这样的现代无序执行CPU(参见http://agner.org/optimize/)具有非常快的硬件乘法(低延迟和高吞吐量),因此增益要小得多.AMD Bulldozer系列有点慢,特别是对于64位乘法.在英特尔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.

这里要注意的最有趣的事情是x86有一个shift-and-add指令(LEA),它可以执行小的左移和同时添加,具有性能和add指令.ARM更强大:任何指令的一个操作数可以免费左移或右移.因此,通过编译时常量进行缩放(已知为2的幂)可以比乘法更有效.

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

// Byte1: 11110000
// Byte2: 00001111

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

// value = 000011111110000;

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

按位运算(包括位移)是低级硬件或嵌入式编程的基础.如果您阅读了设备规范甚至某些二进制文件格式,您将看到字节,字和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;

说明

为了获得绿色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作为offset(#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

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

在实践中,通常是后者.

我只是在写提示和技巧,可能会在测试/考试中发现有用.

n = n*2: n = n<<1

n = n/2: n = n>>1

检查n是2的幂(1,2,4,8,...):检查 !(n & (n-1))

获得X ^个位n:n |= (1 << x)

检查x是偶数还是奇数:( x&1 == 0偶数)

切换Ñ ^个 x的比特:x ^ (1<

(long) 4 >> 65

(long) 4 >> (65 % 64)