是的,如果你想有效地做的话,算术右移是很有用的。 但是,n >>= 2;并不是一个有用的东西,你所做的任何移位都需要是可变计数的(或者如果你广播符号位来制作一个0 / -1掩码,则需要31)。 看看编译器如何处理一个常量n,比如return x / (1<<11);.(Godbolt)。
# x86-64 GCC -O3
bar(int):
testl %edi, %edi # set FLAGS according to x
leal 2047(%rdi), %eax
cmovns %edi, %eax # x < 0 ? x+(1<<11)-1 : x
sarl $11, %eax # arithmetic right shift that value
ret # return value in EAX
# untested
.global dividePower2 # int x in EDI, int n in ESI
# returns int in EAX
dividePower2:
xor %eax, %eax
bts %esi, %eax # 2^n = 1<<n
lea -1(%rax, %rdi), %eax # x + 2^n - 1
test %edi, %edi
cmovns %edi, %eax # x for non-negative, x + 2^n - 1 for negative
mov %esi, %ecx # or sarx %esi, %eax, %eax
sar %cl, %eax # >>= n on the adjusted value is equivalent to /= (1>>n)
ret
// well-defined behaviour for n=0..30
int divp2_bitshift(int x, int n){
int bias = x < 0 ? (1U<<n)-1 : 0U;
return (x+bias) >> n;
// To handle n=31, use unsigned bias and cast x+bias back to signed int to avoid signed-overflow UB
// That might depend on int being 2's complement, so C++20 or C23
}
int divp2_reference(int x, int n){
return x / (1LL<<n); // 64-bit shift and division avoids overflow to INT_MIN
}
2条答案
按热度按时间xpszyzbs1#
是的,如果你想有效地做的话,算术右移是很有用的。
但是,
n >>= 2;
并不是一个有用的东西,你所做的任何移位都需要是可变计数的(或者如果你广播符号位来制作一个0 / -1掩码,则需要31)。看看编译器如何处理一个常量
n
,比如return x / (1<<11);
.(Godbolt)。字符串
*一个简单的
x >> n
(sar %cl, %edi
)舍入到-Infinity,而不是截断到0。Difference in x/2 and x>>1 or x*2 and x << 1 where x is an integer * 详细介绍了编译器如何为x/2
或x/8
或其他对象实现C除法语义。加上
2047
可以将小负数 Package 成小正数,但只有小于1<<11的数字。因此,后面的sar
将把所有设置的位移出去,留下0
,就像我们想要的除法一样,对于幅度小于2048的原始小负数,向零截断。对于更大的负数,增加一个正数会减少数量,减少商,除非它是一个精确的倍数。(因为我们增加的1比除数小)。这让我们可以使用
sar
(算术右移),它向-Infinity舍入,考虑到它和我们想要的截断除法之间的差。对于一个变量count,
return x / (1<<n)
,编译器简单地将1<<n
具体化并使用idiv
。但是我们可以通过遵循与2的常数幂的有符号除法相同的模式来做得更好。(The
[0,30]
中的n范围限制意味着1<<31
溢出到INT_MIN
是没有问题的。我认为这个算法可以正确地用于n=31
。结果是0
或-1
,这是32位sar
乘31的两个可能结果。将0x7fffffff
与除INT_MIN
= 0x 80000000之外的任何负数相加将产生非负数,所以sar
产生0。对于x = INT_MIN,我们执行-1 >> 31
得到-1
。)我们可以做
x + (1<<n)-1
,并使用相同的测试/cmovns得到x
或x + (1<<n)-1
。-1
部分可以作为莱亚的一部分来完成。在Intel CPU上获取
1<<n
的最有效方法是将bts
放入一个置零寄存器。(变量计数shl
为3 uops,除非我们使用BMI 2sarx
。使用xor实现0
比mov $1, %eax
便宜。)在AMD Zen上,bts
是2个uops,但shl %cl, %eax
只有1个uops(https://uops.info),将1
移到EAX和shl
中可能更便宜,因为我们无论如何都需要CL中的移位计数用于后面的sar
。(除非我们有sarx
的BMI 2,它允许移位计数来自任何寄存器。)另一种选择是通过将BMI2
bzhi
应用于0xffffffff
来获得(1<<n) - 1
;我认为这直接适用于[0,32]
范围内的n
(尽管sar
仍然只适用于n=[0,31])。它在Intel和AMD上是单uop(https://uops.info/)。见下文;这就是clang对C版本的作用。型
具有3个组件的莱亚(
[-1 + rax + rdi]
)在Skylake和更早版本上会有3个周期的延迟,但Ice Lake运行它有1个周期的延迟。Ice Lake和更高版本上的“慢”LEA不能在那么多端口上运行,但没有延迟损失。(在桤木Lake P-core上,scaled index像Zen系列一样花费2个周期延迟,即使它只是一个2组件莱亚,但我们没有在这里缩放索引。)在Zen-family上,这个3组件莱亚有2个周期延迟。在桤木Lake E-core上也是如此。所以用单独的add
和dec
指令来做没有什么可保存的。另一种获取
(1<<n) - 1
的方法是旧的clang所做的:0xffffffff >> (-n&31)
。它实际上从sar $31, reg
生成0xffffffff
或0
来广播符号位。但是这种策略对于变量n
不太方便,因为它需要求反。在没有BMI 2的x86上尤其不方便,因为移位计数需要在CL中。应该可以使用SSE 2
pslld
和psrad
的SIMD版本,或者使用每个元素变量计数的AVX 2vpsllvd
。与SSE4.1
pblendvps
混合可以替代标量cmov
,但似乎应该可以更高效。也许使用psrad
来获取0
或-1
并做一些事情会更好?或者只是使用它作为pandn
的掩码,在x
为非负的元素中将1<<n - 1
向量置零。psrad
结果直接用作(1<<n) - 1
中的-1
。在C或C++中
型
Clang
-march=skylake
使用bzhi
巧妙地编译为优化版本:型
Godbolt,包括一个
main
,用于针对每个int32_t
位模式和从0
到31
的每个n
,对参考版本和优化版本进行详尽测试。它通过了所有情况。如果参考实现是
return x / (1<<n)
,则它对所有n=0..30
都通过,但对-2147483648 / (1<<31) = 1
则失败(因为参考实现中的1<<31
溢出到INT_MIN,但移位版本给出-1
,因为它除以2的正幂。)我用gcc -O3 -fwrapv -march=native
编译,使有符号整数溢出良好-为了便于测试ASM而定义。因此,这种优化对于
x/(1<<n)
和gcc -fwrapv
是不可用的,因为n=31
的行为被定义为具有负除数。但是如果没有
-fwrapv
,其中有符号溢出在C中是未定义的行为,那么这种优化将是有效的。TODO:向GCC和clang报告这种错过的优化。对于n=0..31的
x/(1LL<<n)
也是有效的,但对于n=32或更高的n则不有效,因为这在C中仍然是定义良好的(我假设x是32位的int
,所以long long
更宽;n=32..63
是有效的,并且使商为0)。oiopk7p52#
你需要在计算中使用IEEE标准的浮点数。这会占用更多的内存,但我看不出有任何其他方法。
记住,任何浮点数都可以写成:
S| exp比特|分数位
设n1=x = s_x| exp bits_x|分数位x
n2=2^n 0| B(n+127)|0
n1/n2等于s_x| exp bits_x-b(n+127)|分数位x
您需要2个32位寄存器来存储除数和除数,1个32位寄存器用于结果。