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


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

我想知道的是,在核心层面,位移(<<,>>,>>>)做了什么,它有什么问题可以帮助解决,以及潜伏在弯道附近的是什么?换句话说,一个绝对的初学者指导比特移位的所有优点。


1189
2017-09-26 19:47


起源


在3GL中使用位移的功能或非功能情况很少。 - Troy DeMonbreun
阅读完这些答案后,您可能需要查看以下链接: graphics.stanford.edu/~seander/bithacks.html & jjj.de/bitwizardry/bitwizardrypage.html - claws
值得注意的是,对于计算机来说,位移非常容易且快速。通过在程序中找到使用位移的方法,可以大大减少内存使用和执行时间。 - Hoytman


答案:


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

运营商

  • >> 算术(或签名)右移运算符。
  • >>> 是逻辑(或无符号)右移运算符。
  • << 是左移运算符,满足逻辑和算术移位的需要。

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

注意 <<< 不是运营商,因为它是多余的。另请注意,C和C ++不区分右移位运算符。他们只提供 >> 运算符,右移行为是为签名类型定义的实现。


左移(<<)

整数在内存中存储为一系列位。例如,数字6存储为32位 int 将会:

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的力量进行分裂。


1508
2017-09-26 20:46



答案应该更清楚地表明这是一个特定于Java的答案。在C / C ++或C#中没有>>>运算符,并且>>是否传播符号是在C / C ++中定义的实现(一个主要的潜在问题) - Michael Burr
在C语言的上下文中,答案是完全错误的。对于C中的“算术”和“逻辑”移位没有有意义的划分。在C中,移位在无符号值和正有符号值上按预期工作 - 它们只是移位。在负值上,右移是实现定义的(即,通常没有任何关于它的作用),并且左移简单地被禁止 - 它产生未定义的行为。 - AnT
奥黛丽,算术和逻辑右移之间肯定存在差异。 C简单地保留了定义的选择实现。绝对禁止左移负值。将0xff000000向左移一位,你将获得0xfe000000。 - Derek Park
A good optimizing compiler will substitute shifts for multiplications when possible.   什么?当归结为CPU的低级操作时,异步提升的速度要快几个数量级,一个好的优化编译器可以做到这一点 精确 相反,即将普通乘法乘以2的幂变为位移。 - Mahn
@Mahn,你是从我的意图中向后看。用X代替Y意味着用Y代替X.Y代替​​X.因此,移位是乘法的替代。 - Derek Park


假设我们有一个字节:

0110110

应用一个左移位器让我们:

1101100

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

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

向左移动N相当于乘以2ñ

向右移动是(如果你正在使用 那些补充)相当于除以2ñ 四舍五入为零。

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

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

memoryOffset = (row * 320) + column

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

然而,320不是2的幂,所以为了解决这个问题,我们必须找出加在一起的两个2的幂是什么?

(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位模式下,两个版本都变得更短更快。现代无序执行CPU,如Intel Skylake(参见 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在优化时都使用shift + lea return 320*row + col;

这里要注意的最有趣的事情是 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位成员,但在实践中并不总是如此。


169
2017-09-26 19:55



在英特尔处理器(以及许多其他处理器)上扩展它,这样做的速度更快:int c,d; C = d << 2;比这个:c = 4 * d;有时,即使“c = d << 2 + d << 1”也比“c = 6 * d”快!!我在DOS时代广泛使用这些技巧用于图形功能,我认为它们不再那么有用了...... - Joe Pineda
@Joe:如果这些技巧不再有用,这是否意味着编译器编写者现在正在使用它们? - James Thompson
@James:不太好,现在它更像是视频卡的固件,其中包含类似的代码,由GPU而不是CPU执行。因此理论上你不需要像图形函数那样实现这样的代码(或者像Carmack的黑魔法反向根函数):-) - Joe Pineda
@JoePineda @james编译器编写者肯定在使用它们。如果你写 c=4*d 你会得到一个转变。如果你写 k = (n<0) 这也可以通过轮班完成: k = (n>>31)&1 避免分支。总而言之,编译器的聪明性的这种改进意味着现在不必在C代码中使用这些技巧,并且它们损害了可读性和可移植性。如果你正在写作例如,你仍然非常了解它们。 SSE矢量代码;或者你需要快速的任何情况,并且有一个编译器没有使用的技巧(例如GPU代码)。 - greggo
另一个很好的例子:非常普遍的事情是 if(x >= 1 && x <= 9) 这可以做到 if( (unsigned)(x-1) <=(unsigned)(9-1))  将两个条件测试更改为一个可以是一个很大的速度优势;特别是当它允许谓词执行而不是分支时。我用了很多年(合理的)直到10年前我注意到编译器已经开始在优化器中进行这种转换,然后我就停止了。仍然很好知道,因为有类似的情况,编译器无法为您进行转换。或者,如果您正在编写一个编译器。 - greggo


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

图形编程中一个简单的实例是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作为偏移(#define GREEN_OFFSET 5)。

同样常见的是使用位移来快速乘法并除以2的幂:

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

83
2017-09-26 22:22



0x7e0与11111100000相同,即十进制2016。 - Saheed


位屏蔽和移位

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

这通常用于编码或解码图像格式 jpgpng...


39
2018-03-31 10:49





一个问题是以下是依赖于实现的(根据ANSI标准):

char x = -1;
x >> 1;

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

在实践中,通常是后者。


26
2017-09-26 20:07



如果我没记错的话,ANSI C标准明确地说这是依赖于实现的,所以如果你想在代码上右移有符号整数,你需要检查编译器的文档,看看它是如何实现的。 - Joe Pineda
是的,我只是想强调ANSI标准本身就是这样说的,并不是供应商根本不遵循标准或标准对此特定案例一无所知的情况。 - Joe Pineda
@AShelly它的算术与逻辑右移。 - abc


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

例如:

(long) 4 >> 65

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

(long) 4 >> (65 % 64)

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


8
2017-08-28 13:16



嗯,有意思!在C中,这是技术上的 未定义的行为。 gcc 5.4.0 发出警告,但给出了 2 为5 >> 65;同样。 - pizzapants184


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

  1. n = n*2n = n<<1
  2. n = n/2n = n>>1
  3. 检查n是2的幂(1,2,4,8,...):检查 !(n & (n-1))
  4. 入门 X 有点 nn |= (1 << x)
  5. 检查x是偶数还是奇数: x&1 == 0 (甚至)
  6. 切换 ñ 比特x: x ^ (1<<n)

6
2017-10-11 22:43



你现在必须知道更多吗? - ryyker
@ryyker我已经添加了一些。我会尽力不断更新它:) - Ravi Prakash