我们注意到,当修改时
(mod(x, n))
我们更愿意使n为2的幂。这有什么帮助,速度更快吗?
你的"问题"相当模糊,但作为猜测,这就是你想要的吗?
x & (n-1)
其中CCD_ 1是2的幂。这将为您提供x % n
。
设想位:
Let n = (1000)2 = 8
因此,如果你想知道X / n
的余数,你只需要知道在2:的幂以下的3个点中是否有任何值
Let X = (1111)2 = 15
^^^ .... these will be the remainder
因此,如果你选择2的幂,并从中减去1,你就可以为低于它的任何东西设置所有比特:
n - 1 = (1000)2 - (0001)2 = (0111)2
现在看X:
X = (1111)2
& n - 1 = (0111)2
------------------
= (0111)2
由于逐位运算可以非常快地完成,并且除法运算相对较慢,因此这种类型的模运算比除法运算快得多。
通过2的幂进行修改是一个&(按位AND)运算符。
mod(x,2^k)=x&U
其中U=((2^k)-1),这是一个常数。
否则,您必须进行除法运算并找到余数。逐位AND通常是执行1个时钟周期,而除法要慢得多。这方面的细节与&而%。
要回答为什么它更好的问题。。。mod(x,y)
的成本几乎与整数除法一样高。远不止一个简单的AND
操作(根据您的硬件划分,可能需要花费几个CPU周期)。
稍微偏离主题,但在FPGA(verilog/VVHDL)中,AND运算的结果是使用比除法少得多的硬件。
汇编程序中的div命令(用于计算mod)比shift命令要贵得多。
通常:1div=4个班次。
二次方的div可以用shift来代替。
n=2 -> shift by 1, mod = i & 1
n=4 -> shift by 2, mod = i & 3
或通常用于任何int i
n=2^i -> shift by i, mod = x & ((2^i)-1)