Быстрый подсчет битов в диапазоне

Question

Мне нужно найти алгоритм, решающий эту проблему:
найти сумму всех положительных битов в числах в диапазоне [x,y].
Предупреждение: x и y могут быть очень большими (от 1 до 10^20).
Спасибо за помощь.

Answer 1

Возможно, будет полезно взглянуть на конкретный пример, чтобы определить закономерности. Например, от 20 до 25. Вот их двоичные представления:

20: 10100
21: 10101
22: 10110
23: 10111
24: 11000
25: 11001

Глядя на это по столбцу, видно, что самый правый столбец всегда чередуется от 0 до 1. Из этого мы можем сделать вывод, что если в вашем диапазоне есть N чисел, а N четно, то в самом правом столбце есть N/2 бита. Теперь не обращайте внимания на крайний правый столбец и попытайтесь определить шаблон в оставшихся битах.

1010
1010
1011
1011
1100
1100

Каждый номер в списке повторяется ровно один раз. Преобразование в десятичную, мы видим, что эти числа 1010 = 10, 1011 = 11, 1100 = 12, Используя эти два наблюдения, мы можем заключить, что bitsInRange(20, 25) = (27 - 20 - 1) + 2*bitsInRange(10,12), Оба идентифицированных нами шаблона верны для любого четного начального номера и нечетного конечного числа, поэтому формулу можно обобщить так:

bitsInRange(X,Y) =
if X is even and Y is odd:
    (Y - X - 1) + 2*bitsInRange(X/2, (Y-1)/2)

Но что, если у нас есть начальный номер, который является нечетным, или конечный номер, который является четным? Приведенная выше формула не будет работать для них, потому что два идентифицированных нами шаблона не совсем одинаковы для этих типов чисел. Вы можете попробовать написать отдельные формулы для каждой возможной комбинации четных и нечетных, но этот путь опасен и полон ошибок в заборах. Вам будет легче, если вы воспользуетесь этими важными свойствами:

bitsInRange(X, Y) = bitsInRange(X, Y-1) + numBits(Y)
bitsInRange(X, Y) = bitsInRange(X+1, Y) + numBits(X)

... Куда numBits дает количество 1 биты в одном номере.

Теперь мы можем написать рекурсивную формулу для каждой возможной комбинации четных и нечетных диапазонов. (Кстати, нам также нужен базовый вариант)

function bitsInRange(X,Y):
    if X == Y:
        return numBits(X)
    if X is odd:
        return bitsInRange(X+1, Y) + numBits(X)
    if Y is even:
        return bitsInRange(X, Y-1) + numBits(Y)
    return (Y - X - 1) + 2*bitsInRange(X/2, (Y-1)/2)

Поскольку последний случай делит проблемное пространство пополам, а все остальные случаи быстро превращают проблему в последний, вся формула имеет логарифмическую сложность. Это хорошо, если вы пытаетесь получить биты в огромном диапазоне, как [1, 10^20]. Даже для таких огромных количеств, bitsInRange будет работать только около 200 раз или около того.