什么位移(位移)经营者和他们的工作是如何做?
-
02-07-2019 - |
题
我已经尝试学习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位。