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

Question

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

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

Answer 1

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

运营商

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

所有这些操作符可以应用到整数值(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的力量进行分裂.

Answer 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位成员,编译器应该为您执行此操作,但实际上并非总是如此.

Answer 3

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

Answer 4

位屏蔽和移位

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

Answer 5

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

char x = -1;
x >> 1;

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

在实践中,通常是后者.

Answer 6

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

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

Answer 7

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

例如:

(long) 4 >> 65

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

(long) 4 >> (65 % 64)

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

Answer 8

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

Answer 9

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

按位移位运算符

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

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

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

• 在负数的情况下：

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

• Right Shift(>>)：右移运算符，将 value 中的所有位向右移动指定的次数。语法：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。

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

输出： 2147483647，因为 -2 在 32 位系统中表示为 11...10。当我们将位移一位时，前 31 位前导位被移动/右移，低位丢失/忽略，零被添加到前导位。所以，它变成了 011...1111 (2^31-1)，它的十进制等价物是 2147483647。