Модуль уже объяснен, тем не менее, давайте повторим.
Чтобы найти остаток от k по модулю 2^n-1, напишите
k = a + 2^n*b, 0 <= a < 2^n
Затем
k = a + ((2^n-1) + 1) * b
= (a + b) + (2^n-1)*b
≡ (a + b) (mod 2^n-1)
Если a + b >= 2^n, повторять до тех пор, пока остаток не станет меньше 2^n, а если это приведет вас к a + b = 2^n-1, заменить его на 0. Каждое "смещение вправо на n и добавьте к последнему n bits "перемещает первый установленный бит вправо на n или n-1 мест (если только k < 2^(2*n-1), когда первый установленный бит после сдвига и добавления может быть 2^n бит).Поэтому, если ширина типа велика по сравнению с n, для этого потребуется много смен - рассмотрим 128-битный тип и n = 3, для больших k вам потребуется более 40 смен.Чтобы уменьшить количество требуемых смен, вы можете использовать тот факт, что
2^(m*n) - 1 = (2^n - 1) * (2^((m-1)*n) + 2^((m-2)*n) + ... + 2^(2*n) + 2^n + 1),
, из которых мы будем использовать только то, что 2^n - 1 делит 2^(m*n) - 1 на все m > 0.Затем вы сдвигаетесь на значения, кратные n, которые примерно равны половине максимальной длины в битах, которую может иметь значение на этом шаге.Для приведенного выше примера 128-битного типа и остатка по модулю 7 (2^3 - 1) ближайшие кратные от 3 до 128/2 равны 63 и 66, первое смещение на 63 бита
r_1 = (k & (2^63 - 1)) + (k >> 63) // r_1 < 2^63 + 2^(128-63) < 2^66
дополучить число максимум с 66 битами, затем сдвинуть на 66/2 = 33 бита
r_2 = (r_1 & (2^33 - 1)) + (r_1 >> 33) // r_2 < 2^33 + 2^(66-33) = 2^34
, чтобы достичь не более 34 бит.Следующий сдвиг на 18 бит, затем 9, 6, 3
r_3 = (r_2 & (2^18 - 1)) + (r_2 >> 18) // r_3 < 2^18 + 2^(34-18) < 2^19
r_4 = (r_3 & (2^9 - 1)) + (r_3 >> 9) // r_4 < 2^9 + 2^(19-9) < 2^11
r_5 = (r_4 & (2^6 - 1)) + (r_4 >> 6) // r_5 < 2^6 + 2^(11-6) < 2^7
r_6 = (r_5 & (2^3 - 1)) + (r_5 >> 3) // r_6 < 2^3 + 2^(7-3) < 2^5
r_7 = (r_6 & (2^3 - 1)) + (r_6 >> 3) // r_7 < 2^3 + 2^(5-3) < 2^4
Теперь достаточно одного вычитания, если r_7 >= 2^3 - 1 достаточно.Чтобы вычислить k % (2^n -1) в b-битном типе, необходимы сдвиги O (log 2 (b / n)).
Коэффициент получается аналогично, снова пишем
k = a + 2^n*b, 0 <= a < 2^n
= a + ((2^n-1) + 1)*b
= (2^n-1)*b + (a+b),
, поэтому k/(2^n-1) = b + (a+b)/(2^n-1), и мы продолжаем пока a+b > 2^n-1.Здесь, к сожалению, мы не можем уменьшить работу, сдвигая и маскируя примерно половину ширины, поэтому этот метод эффективен только тогда, когда n не намного меньше ширины типа.
Код для быстрых случаев, когда n не слишком мало:
unsigned long long modulus_2n1(unsigned n, unsigned long long k) {
unsigned long long mask = (1ULL << n) - 1ULL;
while(k > mask) {
k = (k & mask) + (k >> n);
}
return k == mask ? 0 : k;
}
unsigned long long quotient_2n1(unsigned n, unsigned long long k) {
unsigned long long mask = (1ULL << n) - 1ULL, quotient = 0;
while(k > mask) {
quotient += k >> n;
k = (k & mask) + (k >> n);
}
return k == mask ? quotient + 1 : quotient;
}
Для особого случая, когда n - половина ширины шрифта, цикл выполняется не более двух раз, поэтому, если ветки дороги, может быть лучшеразверните цикл и безоговорочно выполните тело цикла дважды.