什么是按位移位（位移位）运算符，它们是如何工作的？

我一直在尝试在业余时间学习C，其他语言（C#，Java等）也有相同的概念（通常是相同的运算符）。

在核心层面上，位转换（<<、>>、>>>）能做什么，它能帮助解决什么问题，以及在转弯处潜伏着什么陷阱？换句话说，一个绝对的新手引导位转换的所有好处。

803092 次浏览
小开

假设我们有一个字节：

0110110

应用一个左BitShift让我们：

1101100

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

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

左移N等于乘以2N。

右移N（如果您使用的是的补语）相当于除以2N并四舍五入为零。

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

例如，在过去，我们使用模式13h（320×200 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 cyclesmul word [row]; 22 CPU Cyclesmov di,ax; 2 cyclesadd 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 cyclesmov di, ax; 2shl ax, 6;  2shl di, 8;  2add 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 readyadd  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 latencylea edi, [edi + edi*4]   ; row*(64 + 64*4).  1 cycle latencyadd 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 VisualC++在优化#0时都使用Shift+lea。

这里要注意的最有趣的事情是x86有一个移位和添加指令（#0），它可以同时进行小左移和加法，性能与add指令相同。ARM更强大：任何指令的一个操作数都可以免费向左或向右移动。因此，通过已知为2的幂的编译时常量进行缩放甚至比乘法更有效。

好吧，回到现代……现在更有用的东西是使用位移将两个8位值存储在16位整数中。例如，在C#中：

// Byte1: 11110000// Byte2: 00001111
Int16 value = ((byte)(Byte1 >> 8) | Byte2));
// value = 000011111110000;

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

小开

一个问题是以下内容依赖于实现（根据ANSI标准）： 

char x = -1;x >> 1;

x现在可以是127（01111111）或-1（11111111）。

在实践中，通常是后者。

小开
最佳答案

位移位运算符正如其名称所暗示的那样。它们移位位。以下是对不同移位运算符的简短（或不那么简短）介绍。

运营商

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

所有这些运算符都可以应用于整数值（int、long、可能是short和byte或char）。在某些语言中，将移位运算符应用于任何小于int的数据类型会自动调整操作数的大小为int。

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

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

（在所有主流的C和C++实现中，包括GCC和Clang/LLVM，有符号类型上的>>是算术的。一些代码假设了这一点，但这不是标准所保证的。虽然它不是未定义；标准要求实现以这样或那样的方式定义它。然而，负符号数的左移是未定义的行为（有符号整数溢出）。所以除非你需要算术右移，否则用无符号类型进行位移动通常是个好主意。）

左移（<<）

整数以一系列位的形式存储在内存中。例如，存储为32位int的数字6将是：

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的幂除法。

小开

按位操作，包括位移位，是低级硬件或嵌入式编程的基础。如果您阅读设备甚至一些二进制文件格式的规范，您将看到字节、字和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 greenuint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;

补充说明

为了获得从偏移量5开始到10结束（即6位长）的绿色ONLY值，您需要使用（位）掩码，当应用于整个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;
小开

位掩蔽和移位

位移位通常用于低级图形编程。例如，给定的像素颜色值编码为32位字。

 Pixel-Color Value in Hex:    B9B9B900Pixel-Color Value in Binary: 10111001  10111001  10111001  00000000

为了更好地理解，用相同的二进制值标记哪些部分代表哪些颜色部分。

                                 Red     Green     Blue       AlphaPixel-Color Value in Binary: 10111001  10111001  10111001  00000000

比方说，我们想得到这个像素颜色的绿色值。我们可以很容易地通过掩蔽和变化得到这个值。

我们的面具：

                  Red      Green      Blue      Alphacolor :        10111001  10111001  10111001  00000000green_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:     000000B9Pixels-Green Value in Binary:  00000000 00000000 00000000 10111001Pixels-Green Value in Decimal: 185

这通常用于编码或解码图像格式，如jpg、png等。

小开

请注意，在Java实现中，要移动的位数是由源的大小决定的。

例如：

(long) 4 >> 65

你可能会期望将位向右移动65次会将所有内容归零，但它实际上相当于：

(long) 4 >> (65 % 64)

对于<<;, >>, 和>>>来说确实如此。我还没有在其他语言中尝试过。

小开

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

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

当然，如果您使用64位版本的PHP（Unix），您应该避免移动超过63位。但是，例如，MySQL使用64位BIGINT，因此不应该有任何兼容性问题。

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

小开

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

  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. 获取xth位n：n |= (1 << x)
  5. 检查x是偶数还是奇数：x&1 == 0（偶数）
  6. 切换x的nth位：x ^ (1<<n)
小开

Python中一些有用的位操作/操作。

我用Python实现了拉维·普拉卡什的回答。

# Basic bit operations# Integer to binaryprint(bin(10))
# Binary to integerprint(int('1010', 2))
# Multiplying x with 2 .... x**2 == x << 1print(200 << 1)
# Dividing x with 2 .... x/2 == x >> 1print(200 >> 1)
# Modulo x with 2 .... x % 2 == x & 1if 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) & 1print((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))
小开

按位运算符用于执行位级操作或以不同方式操作位。按位操作被发现更快，有时用于提高程序的效率。基本上，按位运算符可以应用于整数类型：长期、int、短、char和字节。

位移位运算符

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

  • 左移（<<）：向左移位运算符，将value中的所有位向左移位指定次数。语法：value<

在此处输入图片描述

输出：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中的所有位向右移位指定的次数。语法：value>>num，num指定将value中的值向右移位的位置数。也就是说，>>将指定值中的所有位向右移位/移位num指定的位位置数。以下代码片段将值35向右移动了两个位置：

在此处输入图片描述

输出：8，由于35在32位系统中的二进制表示是00…00100011，因此当我们右移两次时，前30个前导位被移动/移位到右侧，两个低阶位被丢失/忽略，并在前导位添加两个零。所以，它变成了00…00001000，这个二进制表示的十进制等效值是8。或者有一个简单的数学技巧来找出以下代码的输出：

在此处输入图片描述

输出：

在此处输入图片描述

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

  • 对于负数：由于负数，右移位运算符在有符号和无符号两种模式下工作。在有符号右移位运算符 (>>), 在正数的情况下，它用0填充前导位。在负数的情况下，它用1填充前导位。为了保持符号。这称为符号扩展。

在此处输入图片描述

输出：-5，正如我上面解释的那样，编译器将负值存储为2的补码。所以，-10表示为2^32-10，考虑到32位系统11……0110。当我们移动/移动一次时，前31位前导位在右侧移动，低阶位丢失/忽略。所以，它变成了11…0011，这个数字的十进制表示是-5（我怎么知道数字的符号？因为前导位是1）。有趣的是，如果你向右移动-1，结果总是保持-1，因为符号扩展不断在高阶位中引入更多的符号。

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

在此处输入图片描述

输出：2147483647，因为-2在32位系统中表示为11…10。当我们将位移动一位时，前31位前导位向右移动/移动，低阶位丢失/忽略，并将零添加到前导位。因此，它变成了011…1111（2^31-1），其十进制等效值为2147483647。


提交答案