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

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

источник

2012-06-21 John Smith

Подсказка: найдите количество бит «1» в крайнем правом положении. – wildplasser

Это домашнее задание? Что вы уже пробовали? Какой аспект проблемы вы застряли? – hatchet

Возможный дубликат [Число 1 в двоичных представлениях двоичных представлений целых чисел в диапазоне] (http://stackoverflow.com/questions/7942732/number-of-1s-in-the-twos-complement-binary-representations -of-integers-in-a-run) – tskuzzy

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

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

Каждый номер в списке повторяется ровно один раз. Преобразование в десятичное число, мы видим, что эти цифры: 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)

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

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 раз.

источник

2012-06-21 19:56:32 Kevin

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

ответ

Смежные вопросы