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

What are bitwise shift (bit-shift) operators and how do they work?

提问人:John Rudy 提问时间:9/27/2008 最后编辑:Peter MortensenJohn Rudy 更新时间:8/29/2022 访问量:855625

问:

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

在核心层面上,位移(、、)有什么作用,它可以帮助解决什么问题,以及弯道周围潜伏着什么陷阱?换句话说,这是一本绝对的初学者指南,可以充分发挥其优点。<<>>>>>

与语言无关的 操作 位移 二进制运算符

评论

2赞 Troy DeMonbreun 9/27/2008
在 3GL 中使用位移的功能性或非功能性情况很少。
23赞 claws 6/15/2010
阅读这些答案后,您可能需要查看以下链接: graphics.stanford.edu/~seander/bithacks.html & jjj.de/bitwizardry/bitwizardrypage.html
5赞 Hoytman 8/24/2016
需要注意的是,对于计算机来说,位移是极其容易和快速的。通过找到在程序中使用位移的方法,可以大大减少内存使用量和执行时间。

答:

241赞 FlySwat 9/27/2008 #1

假设我们有一个字节:

0110110

应用单个左位移位可以得到:

1101100

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

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

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

向右移动 N 是(如果你使用 1 的补码)相当于除以 2N 并四舍五入到零。

位移可用于极快的乘法和除法,前提是您使用的是 2 的幂。几乎所有低级图形例程都使用位移。

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

memoryOffset = (row * 320) + column

现在,在那个时代,速度至关重要,所以我们会使用位移来执行此操作。

然而,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

总计:28 个周期,在任何古代 CPU 上都有这些时序。

Tr1

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(见 http://agner.org/optimize/)这样的现代无序执行 CPU 具有非常快的硬件倍增(低延迟和高吞吐量),因此增益要小得多。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 和 Microsoft Visual C++ 在优化返回 320*row + col; 时如何使用 shift+lea

这里最需要注意的是,x86 有一个移位和加法指令 (LEA),可以同时进行小的左移和加法,性能作为指令。ARM 功能更强大:任何指令的一个操作数都可以免费向左或向右移动。因此,按已知为 2 的幂的编译时常量进行缩放可能比乘法更有效。add


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

// Byte1: 11110000
// Byte2: 00001111

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

// value = 000011111110000;

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

评论

11赞 Joe Pineda 9/27/2008
扩展这一点,在英特尔处理器(以及许多其他处理器)上,这样做会更快:int c, d;c=d<<2;比这个:c=4*d;有时,甚至“c=d<<2 + d<<1”也比“c=6*d”更快!在DOS时代,我广泛地将这些技巧用于图形功能,我认为它们不再那么有用了......
7赞 Joe Pineda 8/29/2012
@James:不完全是,现在的显卡固件包含这样的代码,由GPU而不是CPU执行。所以从理论上讲,你不需要为图形函数实现这样的代码(或者像 Carmack 的黑魔法逆根函数):-)
4赞 greggo 10/30/2014
@JoePineda @james 编译器编写者肯定在使用它们。如果你写,你会得到一个转变。如果你写,也可以通过轮班来完成:避免分支。归根结底,编译器智能性的这种改进意味着现在没有必要在 C 代码中使用这些技巧,而且它们会损害可读性和可移植性。如果您正在编写例如 SSE 向量代码,了解它们仍然非常好;或者任何需要快速它并且编译器没有使用的技巧(例如 GPU 代码)的情况。c=4*dk = (n<0)k = (n>>31)&1
2赞 greggo 10/30/2014
另一个很好的例子:非常常见的事情是可以做到的,因为将两个条件测试更改为一个可以是一个很大的速度优势;尤其是当它允许预测执行而不是分支时。我用了好几年(在合理的情况下),直到 10 年前我注意到编译器已经开始在优化器中进行这种转换,然后我就停止了。仍然很高兴知道,因为在类似的情况下,编译器无法为您进行转换。或者,如果您正在使用编译器。if(x >= 1 && x <= 9)if( (unsigned)(x-1) <=(unsigned)(9-1))
4赞 Mason Watmough 1/1/2016
你的“字节”只有 7 位是有原因的吗?
29赞 AShelly 9/27/2008 #2

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

char x = -1;
x >> 1;

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

在实践中,通常是后者。

评论

4赞 Joe Pineda 9/27/2008
如果我没记错的话,ANSI C 标准明确指出这是依赖于实现的,因此如果您想在代码上右移有符号整数,您需要检查编译器的文档以了解它是如何实现的。
0赞 Joe Pineda 9/27/2008
是的,我只是想强调 ANSI 标准本身是这么说的,这并不是供应商根本不遵循标准的情况,也不是标准对这种特殊情况一无所知的情况。
1874赞 Derek Park 9/27/2008 #3

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

运营商

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

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

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

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

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


左移 (<<)

整数以一系列位的形式存储在内存中。例如,存储为 32 位的数字 6 为:int

00000000 00000000 00000000 00000110

将此位模式移到左侧一个位置 () 将产生数字 12:6 << 1

00000000 00000000 00000000 00001100

如您所见,数字向左移动了一个位置,右侧的最后一个数字用零填充。您可能还会注意到,左移等同于乘以 2 的幂。所以等价于 ,并且等价于 。一个好的优化编译器会在可能的情况下用移位代替乘法。6 << 16 * 26 << 36 * 8

非圆周变速

请注意,这些不是循环班次。将此值向左移动一个位置 ():3,758,096,384 << 1

11100000 00000000 00000000 00000000

结果为 3,221,225,472:

11000000 00000000 00000000 00000000

“从末尾”移位的数字丢失。它不会环绕。


逻辑右移 (>>>)

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

00000000 00000000 00000000 00001100

向右移动一个位置 () 将返回我们原来的 6:12 >>> 1

00000000 00000000 00000000 00000110

因此,我们看到向右移动等同于 2 的幂除。

丢失的位不见了

但是,移位无法回收“丢失”的位。例如,如果我们改变这种模式:

00111000 00000000 00000000 00000110

在左边的 4 个位置 (),我们得到 2,147,483,744:939,524,102 << 4

10000000 00000000 00000000 01100000

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

00001000 00000000 00000000 00000110

一旦我们丢失了位,我们就无法恢复原来的价值。


算术右移 (>>)

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

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

10000000 00000000 00000000 01100000

我们有数字 -2,147,483,552。通过算术移位将其移动到右侧 4 个位置 (-2,147,483,552 >> 4) 将得到:

11111000 00000000 00000000 00000110

或数字 -134,217,722。

因此,我们看到我们通过使用算术右移而不是逻辑右移来保留负数的符号。再一次,我们看到我们正在执行 2 的幂除法。

评论

341赞 Michael Burr 10/20/2008
答案应该更清楚地表明这是一个特定于 Java 的答案。C/C++ 或 C# 中没有 >>> 运算符,>>是否传播符号是 C/C++ 中定义的实现(一个主要的潜在问题)
63赞 AnT stands with Russia 6/9/2010
在C语言的上下文中,答案是完全不正确的。在 C 语言中没有对“算术”和“逻辑”移位进行有意义的划分。在 C 语言中,移位在无符号值和正符号值上按预期工作 - 它们只是移位。在负值上,右移是实现定义的(即不能说它的一般作用),而左移是被禁止的 - 它会产生未定义的行为。
12赞 Derek Park 7/10/2010
奥黛丽,算术和逻辑右移肯定是有区别的。C 只是将选择实现保留定义。负值的左移绝对不被禁止。0xff000000向左移动一点,你会得到0xfe000000。
17赞 Mahn 6/14/2013
A good optimizing compiler will substitute shifts for multiplications when possible.什么?当涉及到 CPU 的低级操作时,比特移位的速度要快几个数量级,一个好的优化编译器会做完全相反的事情,即将普通的 2 次幂乘法转换为比特移位。
61赞 Derek Park 1/28/2014
@Mahn,你是从我的意图倒过来读的。用 Y 代替 X 意味着用 Y 替换 X,Y 是 X 的替代品。因此,移位是乘法的替代品。
115赞 robottobor 9/27/2008 #4

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

图形编程中的一个简单的真实示例是 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;

评论

1赞 Saïd 4/1/2015
0x7e0与11111100000相同,十进制为 2016。
61赞 Basti Funck 3/31/2015 #5

位掩码和移位

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

评论

0赞 David H Parry 10/14/2019
将原始字节(例如 32 位 cl_uint)转换为类似 cl_uchar4 并直接以 *.s2 格式访问所需的字节不是更容易吗?
9赞 Patrick Monkelban 8/28/2015 #6

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

例如:

(long) 4 >> 65

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

(long) 4 >> (65 % 64)

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

评论

0赞 pizzapants184 1/15/2018
呵呵,有意思!在 C 语言中,这在技术上是未定义的行为。 发出警告,但给出 5 >> 65;也。gcc 5.4.02
-3赞 lukyer 10/23/2015 #7

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

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

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

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

28赞 HoneyBeer 10/12/2016 #8

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

  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 位:nn |= (1 << x)
  5. 检查 x 是偶数还是奇数:(偶数)x&1 == 0
  6. 切换 x 的第 n 位:x ^ (1<<n)

评论

0赞 reggaeguitar 10/6/2018
x 和 n 0 是否被索引?
0赞 Peter Mortensen 1/7/2020
广告 5.:如果是负数怎么办?
0赞 Willy satrio nugroho 1/18/2020
那么,我们可以得出结论,二进制中的 2 就像十进制中的 10 吗?位移就像在十进制中的另一个数字后面再加一个数字或减去一个数字?
0赞 JaredH 4/9/2020
对于快捷方式 (3),输入 将导致 ,因此请务必检查该输入。0true
0赞 Will 7/19/2023
对于第 4 项。您需要按位 & 运算符,以仅获得位置 x 处的单个位。n &= (1 << x)
5赞 user6573621 4/28/2019 #9

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))
7赞 Trishant Saxena 6/14/2020 #10

按位运算符用于执行位级操作或以不同的方式操作位。按位运算被发现要快得多,并且有时用于提高程序的效率。 基本上,按位运算符可以应用于整数类型:longintshortcharbyte

按位移位运算符

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

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

enter image description here

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

  • 如果是负数:

Code for Negative number.

输出:-2,在 java 负数中,用 2 的补码表示。所以,-1 表示 2^32-1,相当于 1....11(考虑到 32 位系统)。当移动一次时,前导位被忽略/丢失,其余 31 位向左移动,最后添加零。所以它变成 11...10,它的十进制等价物是 -2。 所以,我认为你对左移及其工作原理有足够的了解。

  • 右移位(>>):右移运算符,将所有值位向右移动指定次数。语法:value >> num,num 指定将值右移的位置数。也就是说,>>移动/移动指定值中的所有位,使 num 指定的位位置数正确。 以下代码片段将值 35 向右移动两个位置:

enter image description here

输出:8,由于 35 位系统中 32 的二进制表示是 00...00100011,因此当我们向右移动两次时,前 30 个前导位被移动/向右侧移动,两个低阶位丢失/忽略,并在前导位添加两个零。因此,它变为 00....00001000,此二进制表示的十进制等效值为 8。 或者有一个简单的数学技巧来找出以下代码的输出: 为了概括这一点,我们可以说,x >> y = floor(x/pow(2,y))。考虑上面的例子,x=35 和 y=2,所以,35/2^2 = 8.75,如果我们取下限值,那么答案是 8。

enter image description here

输出:

enter image description here

但请记住一件事:这个技巧对于 y 的小值是可以的,如果你取 y 的大值,它会给你不正确的输出。

  • 如果是负数: 由于负数,右移运算符在有符号和无符号两种模式下工作。在有符号右移运算符 (>>) 中,如果为正数,则用 0 填充前导位。如果为负数,则用 1 填充前导位。保持标志。这称为“符号扩展”。

enter image description here

输出:-5,正如我上面解释的,编译器将负值存储为 2 的补码。因此,-10 表示为 2^32-10,并考虑 32 位系统 11....0110 的二进制表示。当我们移动/移动一次时,前 31 个前导位在右侧移动,而低阶位丢失/忽略。因此,它变成了 11...0011,这个数字的十进制表示是 -5(我怎么知道数字的符号?因为前导位是 1)。 有趣的是,如果向右移动 -1,结果始终保持 -1,因为符号扩展会不断在高阶位中引入更多符号。

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

enter image description here

输出:2147483647,因为 -2 在 32 位系统中表示为 11...10。当我们将位移 1 时,前 31 个前导位向右移动/移位,低阶位丢失/忽略,零添加到前导位。因此,它变为 011...1111 (2^31-1),其十进制等价物为 2147483647。

评论

0赞 Peter Mortensen 8/14/2023
请查看为什么在提问时不上传代码/错误的图像?(例如,“图像只能用于说明无法通过任何其他方式阐明的问题,例如提供用户界面的屏幕截图。做正确的事情(它也涵盖了答案)。提前致谢。