移位运算符的作用与它们的名字所暗示的完全一致。他们移动比特。以下是对不同轮班操作员的简要介绍。

操作员

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

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

注意 <<< 不是操作员,因为它是多余的。

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

(在所有主流的C和C++实现中,包括GCC和Clang/LLVM, >> 有符号类型是算术。一些代码假设了这一点,但这不是标准所保证的。不是 未限定的 不过;该标准要求实现以某种方式定义它。然而,负符号数的左移 是 未定义行为(有符号整数溢出)。因此,除非你需要算术右移,否则用无符号类型进行移位通常是个好主意。)

左移(<<)

整数作为一系列位存储在内存中。例如,将数字6存储为32位 国际性组织 将是:

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

结果为3221225472:

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 ),我们得到2147483744:

10000000 00000000 00000000 01100000

然后向后移动( (939,524,102 << 4) >>> 4 )我们得到134217734:

00001000 00000000 00000000 00000110

一旦我们丢失了比特,就无法恢复原始价值。

算术右移(>>)

算术右移与逻辑右移完全相同,除了不是用零填充,而是用最高有效位填充。这是因为最高有效位是 签名 位或区分正数和负数的位。通过填充最高有效位,算术右移是符号保持的。

例如,如果我们将此位模式解释为负数:

10000000 00000000 00000000 01100000

我们有号码2147483552。通过算术移位(-2147483552>>4)将其向右移动4个位置,我们将得到:

11111000 00000000 00000000 00000110

或拨打134217722。

所以我们看到,通过使用算术右移而不是逻辑右移,我们保留了负数的符号。我们再次看到,我们正在按2的幂进行除法运算。

假设我们有一个字节:

0110110

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

1101100

最左侧的零被移出字节,一个新的零被附加到字节的右端。

这些比特不会翻转;它们被丢弃了。这意味着如果你左移1101100,然后右移它,你将不会得到相同的结果。

向左移动N相当于乘以2 ^N .

向右移动N是(如果您正在使用 ones' complement )相当于除以2 ^N 并四舍五入到零。

只要你使用的是2的幂,比特移位就可以用于疯狂快速的乘法和除法。几乎所有低级图形例程都使用位移。

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

memoryOffset = (row * 320) + column

现在,在那个时代,速度是至关重要的,所以我们会使用bitshift来做这个操作。

然而,320不是2的幂,所以为了解决这个问题,我们必须找出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个周期。

虚拟现实系统

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.

vs。

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, and Microsoft Visual C++ all use shift+lea when optimizing return 320*row + col; .

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

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

// Byte1: 11110000
// Byte2: 00001111

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

// value = 000011111110000;

在C++中,如果你使用 struct 有两个8位成员,但在实践中并不总是如此。

逐位操作,包括位移,是低级硬件或嵌入式编程的基础。如果你阅读设备的规范,甚至一些二进制文件格式,你会看到字节、字和双字,它们被分解为非字节对齐的位字段,其中包含各种感兴趣的值。访问这些位字段进行读/写是最常见的用法。

图形编程中的一个简单实例是,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,二进制为000001111100000(十进制为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;

比特掩码和;移位

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

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

一个问题是,以下内容取决于实现(根据ANSI标准):

char x = -1;
x >> 1;

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

在实践中,通常是后者。

我只是在写技巧和窍门。它可能在测试和考试中有用。

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. 得到 英语字母表的第24个字母 ^钍 的位 n : n |= (1 << x)
5. 检查x是偶数还是奇数: x&1 == 0 (甚至)
6. 切换 n ^钍 x的位: x ^ (1<<n)

请注意,在Java实现中,要移位的位数会根据源代码的大小进行调整。

例如:

(long) 4 >> 65

等于2。你可能会认为将位向右移动65次会使所有内容归零,但实际上相当于:

(long) 4 >> (65 % 64)

这对<<>>以及>>>我还没有用其他语言试过。

Bitwise运算符用于执行位级别的操作或以不同的方式操纵位。发现位操作要快得多,有时用于提高程序的效率。 基本上,位运算符可以应用于整数类型: 长的 , 国际性组织 , 短的 , 烧焦 和 字节 .

逐位移位运算符

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

• 左移(<<): 左移运算符将值中的所有位向左移动指定次数。语法:value<<num。这里num指定左移值的位置数。即<<将指定值中的所有位向左移动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。 所以,我认为你已经对左移及其工作原理有了足够的了解。

• 右移(>>): 右移运算符将值中的所有位向右移动指定的次数。语法:value>>num,num指定将值右移的位置数。即>>移动/移位右侧指定值中的所有位,即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填充前导位,而前者在任何一种情况下都填充零。现在的问题是,如果我们通过有符号右移运算符得到所需的输出,为什么我们需要无符号右移操作。通过一个例子来理解这一点,如果你正在移动不代表数值的东西,你可能不希望发生符号扩展。当您使用基于像素的值和图形时,这种情况很常见。在这些情况下,无论初始值是多少,您通常都希望将零移位到高位。

产量:2147483647 ,因为在32位系统中,-2表示为11…10。当我们逐位移位时,前31个前导位向右移动/移位,低位丢失/忽略,零被添加到前导位。因此,它变为011…1111(2^31-1),其十进制等效值为2147483647。

Python中一些有用的位操作。

我实施了 Ravi Prakash's answer 在Python中。

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

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

然后,如果你换了<<或>>超过31比特的结果是不可预料的。通常会返回原始数字而不是零,这可能是一个非常棘手的错误。

当然,如果你使用64位版本的PHP(Unix),你应该避免偏移超过63位。然而,例如,MySQL使用64位BIGINT,因此不应该有任何兼容性问题。

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