假设我们对整数1和4执行异或运算,以找到汉明距离。为什么XOR和其他按位运算的运行时间低于常量?是不是因为int的大小在Python等语言中是固定的,这就是为什么无论整数输入如何,操作都会花费消耗时间的原因?
[编辑]假设我们使用Brian Kernighan的算法计算两个整数的hamming距离,如下所示。
def hammingDistance(x: int, y: int):
xor = x ^ y
distance = 0
while xor:
distance += 1
# remove the rightmost bit of '1'
xor = xor & (xor - 1)
return distance
函数不是恒定时间(这取决于最高设置位是什么(,但在大多数(或所有?(现代CPU上,它中的每个逐位运算符都是恒定时间,这些CPU具有在固定周期内对整个16/32/64位操作数进行操作的指令。
位指令是一些最简单的CPU指令;我很想知道是否有任何处理器有可变时间位操作指令。很少有算术CPU指令的运行时间取决于它们的值。一些例子是除法(在某些/大多数情况下(、当涉及非标准化时的乘法以及当前AMD CPU上的pdep
。