Почему время выполнения побитовой операции постоянно?

Question

Допустим, мы выполняем операцию XOR над целыми числами 1 и 4, чтобы найти расстояние Хэмминга. Почему время выполнения XOR и других побитовых операций ниже постоянного? Это потому, что размер int фиксирован в таких языках, как Python и et c., Поэтому операция займет согласованное время независимо от целочисленных входов?

[Edit] Предположим, мы вычисляем расстояние Хэмминга двух целых чисел с использованием алгоритма Брайана Кернигана, как показано ниже.

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

Answer 1

Эта функция не является постоянной времени (это зависит от того, какой самый высокий установленный бит), но каждый побитовый оператор в ней является постоянным временем для большинства (или всех? ) современные процессоры, которые имеют инструкции для тех, которые работают с целыми 16/32/64-битными операндами за фиксированное количество циклов.

Побитовые инструкции - это одни из самых простых инструкций процессора; Мне было бы любопытно узнать, имел ли когда-либо какой-либо процессор инструкции по манипулированию битами с переменным временем. Существует очень мало инструкций процессора arithmeti c, время выполнения которых зависит от их значений. Некоторыми примерами являются деление (в некоторых / большинстве? Случаев), умножение, когда задействованы денормальные числа, и pdep на текущих процессорах AMD.