什么位移(位移)经营者和他们的工作是如何做?
https://stackoverflow.com/questions/141525
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我已经尝试学习C在我的业余时间、语文和其他语文(C#、Java、等等)。 有相同的概念(并经常同运营商)...
我想知道的是，在一个核心水平，这是什么位移(<<, >>, >>>)做什么的问题，它可以帮助解决了，有什么陷阱潜伏围绕弯？换句话说，一种绝对初学者指南的位移在其所有善良。
解决方案
位移的经营者做什么他们的名称所暗示的。他们转移位。这里有一个简单的(或者不那么简短的)介绍不同的移运营商。
经营者
>>是的算术(或签名)右转移操作员。>>>是的逻辑(或符号)的权利转移操作员。<<是左移动运营商，并满足需求的逻辑和算术班。
所有这些运营商可应用于整数值(int, long, 可能 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.转移这一权的4个职位的算术转移(-2,147,483,552>>4)将给我们：
11111000 00000000 00000000 00000110
或数-134,217,722.
因此，我们看到，我们有保留的标志我们的负数通过使用算术右转移，而不是合乎逻辑的权利的转变。和我们再次看到，我们正在执行司通过权力2。
其他提示
假设我们有一个字节：
0110110
应用一个左移位器让我们：
1101100
最左边的零移出了字节，并且在字节的右端附加了一个新的零。
这些位不会翻转;他们被丢弃了。这意味着如果你离开1101100然后右移它，你就不会得到相同的结果。
向左移动N相当于乘以2 N 。
N向右移动（如果您使用那些补充）是相当于除以2 N 并四舍五入为零。
Bitshifting可以用于疯狂快速的乘法和除法，只要你使用2的幂。几乎所有的低级图形例程都使用位移。
例如，回到过去，我们使用模式13h（320x200 256色）进行游戏。在模式13h中，视频存储器按像素顺序布局。这意味着计算像素的位置，您将使用以下数学：
memoryOffset = (row * 320) + column
现在，在那个时代，速度是至关重要的，所以我们会使用位移来进行此操作。
然而，320并不是两个人的力量，所以为了解决这个问题，我们必须找出两个加在一起的力量是什么使得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位模式下，两个版本都变得更短更快。现代无序执行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.
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和MSVC在优化return 320*row + col; 时都使用shift + lea。
这里最值得注意的是 x86如hift-and-add指令（LEA），可以执行小的左移和同时添加，具有性能和add指令。 ARM更强大：任何指令的一个操作数可以免费左移或右移。因此，通过编译时常量（称为2的幂）进行缩放甚至比乘法更有效。
好的，回到现代......现在更有用的是使用位移来将两个8位值存储在16位整数中。例如，在C＃中：
// Byte1: 11110000
// Byte2: 00001111
Int16 value = ((byte)(Byte1 >> 8) | Byte2));
// value = 000011111110000;
在C ++中，如果您使用带有两个8位成员的struct，编译器应该为您执行此操作，但实际上并非总是如此。
按位运算（包括位移）是低级硬件或嵌入式编程的基础。如果您阅读了设备规范甚至某些二进制文件格式，您将看到字节，字和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运算符（<！> amp;）。
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
Et voil <！>＃225;，我们有一个整数表示像素颜色中的绿色数量：
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）。
在实践中，通常是后者。
我只是在撰写技巧和窍门，可能会在测试/考试中发挥作用。
-
n = n*2：n = n<<1 -
n = n/2：n = n>>1 - 检查n是2的幂（1,2,4,8，...）：检查
!(n & (n-1)) - 获取 x 位
n：n |= (1 << x) - 检查x是偶数还是奇数：
x&1 == 0（偶数） - 切换x：
x ^ (1<<n)的 n th 位
请注意，在Java实现中，要移位的位数由源的大小来修改。
例如：
(long) 4 >> 65
等于2.您可能希望将位向右移动65次会将所有内容归零，但它实际上相当于：
(long) 4 >> (65 % 64)
对于<！> lt; <！> lt;，<！> gt; <！> gt;和<！> gt; <！> gt; <！> gt;。我没有用其他语言试过。
Python中一些有用的位操作/操作。在python中实现了@Ravi Prakash的答案。
# basic bit operations
# int to bin
print(bin(10))
# bin to int
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 2nd bit is 0
# toggle nth bit of x : x^(1<<n)
# take bin(10)==1010 and toggling 2nd bit in bin(10) we get 1110 === bin(14)
print(10^(1<<2))
请注意，Windows平台上只提供32位版本的PHP。
然后，如果你转移<！> lt; <！> lt;或<！> gt; <！> gt;超过31位，结果是不可想象的。通常会返回原始数字而不是零，这可能是一个非常棘手的错误。
当然如果你使用64位版本的PHP（unix），你应该避免移位超过63位。但是，例如，MySQL使用64位BIGINT，因此不应存在任何兼容性问题。
更新：从PHP7 Windows开始，php构建终于能够使用完整的64位整数： 整数的大小取决于平台，但最大值约为20亿是通常的值（32位有符号）。 64位平台的最大值通常约为9E18，除了在PHP之前的Windows上，它总是32位。
