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
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.
8 回答
请注意,在Java实现中,要移位的位数由源的大小来修改 .
例如:
等于2.您可能希望将位向右移动65次会将所有内容归零,但它实际上相当于:
这对于<<,>>和>>> . 我还没有尝试过其他语言 .
我只是在写提示和技巧,可能会在测试/考试中发现有用 .
n = n*2
:n = n<<1
n = n/2
:n = n>>1
检查n是2的幂(1,2,4,8,...):检查
!(n & (n-1))
获取
n
的第x位:n |= (1 << x)
检查x是偶数还是奇数:
x&1 == 0
(偶数)切换x的第n位:
x ^ (1<<n)
位移操作符正如其名称所暗示的那样 . 他们转移位 . 以下是对不同班次运营商的简要介绍(或不那么简短) .
运营商
>>
是算术(或签名)右移运算符 .>>>
是逻辑(或无符号)右移运算符 .<<
是左移位运算符,满足逻辑和算术移位的需要 .所有这些运算符都可以应用于整数值(
int
,long
,可能short
和byte
或char
) . 在某些语言中,将移位运算符应用于小于int
的任何数据类型会自动将操作数的大小调整为int
.请注意
<<<
不是运算符,因为它是多余的 . 另请注意,C和C不区分右移运算符 . 它们仅提供>>
运算符,右移行为是针对签名类型定义的实现 .左移(<<)
整数在内存中存储为一系列位 . 例如,存储为32位
int
的数字6将是:将此位模式移动到左侧一个位置(
6 << 1
)将导致数字12:如您所见,数字向左移动了一个位置,右侧的最后一个数字用零填充 . 你可能还会注意到左移相当于乘以2的幂 . 所以
6 << 1
相当于6 * 2
,而6 << 3
相当于6 * 8
. 一个好的优化编译器会在可能的情况下用乘法替换乘法 .非循环移位
请注意,这些不是循环转换 . 将此值向左移动一个位置(
3,758,096,384 << 1
):结果为3,221,225,472:
“失去结束”的数字将丢失 . 它没有环绕 .
逻辑右移(>>>)
逻辑右移与左移相反 . 它们不是向左移动位,而是向右移动 . 例如,移动数字12:
向右移动一个位置(
12 >>> 1
)将取回原来的6个:所以我们看到向右移动相当于2的幂除法 .
丢失的位消失了
但是,移位无法回收“丢失”的位 . 例如,如果我们改变这种模式:
在左边4个位置(
939,524,102 << 4
),我们得到2,147,483,744:然后换回(
(939,524,102 << 4) >>> 4
)我们得到134,217,734:一旦我们丢失了比特,我们就无法取回原来的 Value .
算术右移(>>)
算术右移与逻辑右移非常相似,除了用零填充代替填充,它填充最高有效位 . 这是因为最重要的位是符号位,或区分正数和负数的位 . 通过使用最高有效位填充,算术右移是符号保留的 .
例如,如果我们将此位模式解释为负数:
我们的号码是-2,147,483,552 . 用算术移位(-2,147,483,552 >> 4)将它移到右边的4个位置会给我们:
或者数字-134,217,722 .
所以我们看到我们通过使用算术右移而不是逻辑右移来保留负数的符号 . 再一次,我们看到我们正以2的力量进行分裂 .
假设我们有一个字节:
应用一个左移位器让我们:
最左边的零移出字节,新的零附加到字节的右端 .
这些位不会翻转;他们被丢弃了 . 这意味着如果您离开1101100然后右移它,您将无法获得相同的结果 .
向左移动N相当于乘以2N .
向右移动N(如果使用ones' complement)相当于除以2N并舍入为零 .
如果您使用的是2的幂,则Bitshifting可以用于疯狂快速的乘法和除法 . 几乎所有低级图形例程都使用位移 .
例如,回到过去,我们使用模式13h(320x200 256色)进行游戏 . 在模式13h中,视频存储器按像素顺序排列 . 这意味着计算像素的位置,您将使用以下数学:
现在,回到那个时代,速度是至关重要的,所以我们会使用位移来做到这一点操作 .
然而,320不是2的幂,所以为了解决这个问题,我们必须找出加在一起的两个2的幂是什么320:
现在我们可以将其转换为左移:
最终结果如下:
现在我们获得与以前相同的偏移量,除了代替昂贵的乘法运算,我们使用两个位移......在x86中它将是这样的(注意,自从我完成汇编以来它一直是永远的(编者注:已更正)几个错误,并添加了一个32位的例子)):
总计:对于任何古老的CPU都有这些时间的28个周期 .
VRS
在同一个古老的CPU上进行12次循环 .
是的,我们会努力减少16个CPU周期 .
在32位或64位模式下,两个版本都变得更短更快 . 像Intel Skylake这样的现代无序执行CPU(参见http://agner.org/optimize/)具有非常快的硬件乘法(低延迟和高吞吐量),因此增益要小得多 . AMD Bulldozer系列有点慢,特别是对于64位乘法 . 在英特尔CPU和AMD Ryzen上,两个班次的延迟略低,但指令多于乘法(这可能导致吞吐量降低):
与
编译器会为您执行此操作:请参阅gcc, clang, and MSVC all use shift+lea when optimizing return 320*row + col; .
这里要注意的最有趣的事情是x86 has a shift-and-add instruction (LEA)可以做小左移并同时添加,性能和
add
指令 . ARM更强大:任何指令的一个操作数可以免费左移或右移 . 因此,通过已知为2的幂的编译时常数进行缩放甚至可以比乘法更有效 .好的,回到现代......现在更有用的是使用位移来将两个8位值存储在一个16位整数中 . 例如,在C#中:
在C中,如果您使用带有两个8位成员的
struct
,编译器应该为您执行此操作,但实际上并非总是如此 .按位运算(包括位移)是低级硬件或嵌入式编程的基础 . 如果您阅读了设备规范甚至某些二进制文件格式,您将看到字节,字和双字,分为非字节对齐的位域,其中包含各种感兴趣的值 . 访问这些位字段以进行读/写是最常见的用法 .
图形编程中一个简单的实例是16位像素表示如下:
要获得绿色值,您可以这样做:
Explanation
为了获得绿色ONLY的值,它从偏移5开始并以10结束(即6位长),你需要使用一个(位)掩码,当应用于整个16位像素时,它将产生只有我们感兴趣的位 .
相应的掩码是0x7E0,二进制为0000011111100000(2016年为十进制) .
要应用蒙版,请使用AND运算符(&) .
应用掩码后,最终会得到一个16位数,这个数字实际上只是一个11位数,因为它的MSB位于第11位 . 绿色实际上只有6位长,所以我们需要使用右移(11 - 6 = 5)来缩小它,因此使用5作为偏移(
#define GREEN_OFFSET 5
) .同样常见的是使用位移来快速乘法并除以2的幂:
位掩盖和移位
位移通常用于低级图形编程 . 例如,以32位字编码的给定像素颜色值 .
为了更好地理解,标有哪些部分的相同二进制值表示什么颜色部分 .
例如,我们想要获得此像素颜色的绿色值 . 我们可以通过屏蔽和移动轻松获得该值 .
我们的面具:
逻辑
&
运算符确保仅保留掩码为1的值 . 我们现在要做的最后一件事是通过将所有这些位向右移动16位(逻辑右移)来获得正确的整数值 .Etvoilá,我们有一个整数表示像素颜色中的绿色数量:
这通常用于编码或解码图像格式,如
jpg
,png
,...
.一个问题是以下是依赖于实现的(根据ANSI标准):
x现在可以是127(01111111)或仍然是-1(11111111) .
在实践中,通常是后者 .
请注意,Windows平台上只有32位版本的PHP可用 .
然后,如果您将<<或>>移位超过31位,则结果是不可理解的 . 通常会返回原始数字而不是零,这可能是一个非常棘手的错误 .
当然,如果你使用64位版本的PHP(unix),你应该避免移位超过63位 . 但是,例如,MySQL使用64位BIGINT,因此不应存在任何兼容性问题 .
更新:从PHP7 Windows开始,php构建最终能够使用完整的64位整数:整数的大小取决于平台,尽管大约20亿的最大值是通常的值(32位签名) . 64位平台的最大值通常约为9E18,除了PHP之前的Windows,它总是32位 .