Вычислить сумму обратной величины множества в диапазоне
Как вычислить сумму обратной величины установленных битов диапазона чисел [A, B] (Здесь A, B> 0&&А, В<10 ^ 9)
Мой подход:
Используя простой цикл for от A до B, я посчитал наборы чисел с помощью _builtin_popcount (встроенная функция для подсчета наборов чисел в C / C ++), а затем взял его обратно и добавил. Это O (n) подход. Но это занимает больше времени из-за больших ограничений. Как я могу оптимизировать дальше? Может ли алгоритм O (log (n)) быть возможным?
Решение
Позволять F(N, k) = |{m | m is an integer lying in [0, N] and m's binary representation has exactly k bits set}|, Вы хотите получить ответ SUM{ (F(B,k) - F(A-1,k))/k | 1<=k<=MSB(B)}, где MSB = самый значимый бит.
Вы можете вычислить F(N,k) рекурсивно. Обрабатывайте границы вашей рекурсии правильно. Фактическая рекурсия
F(N, k) = F(N^(1<<MSB(N)), k-1) + F((1<<MSB(N))-1, k)
На словах вы учитываете те числа, которые имеют одинаковые MSB как N и те, которые имеют MSB меньше, чем у N и рекурсировать.
Время выполнения O(log(B)*log(B)),
РЕДАКТИРОВАТЬ: Иллюстрирование рекурсии:
N = 1101в двоичном виде, k=2,
Набор чисел <= N, с MSB быть таким же, как N являются {1000, 1001, 1010, 1011, 1100, 1101}, Обратите внимание, что они на самом деле такие же, как этот набор 1000 + {000, 001, 010, 011, 100, 101}, Другими словами, они все числа <= N^(1<<MSB(N)) = 1101 ^ 1000 = 101, Так как вы уже посчитали MSB бит, количество бит, которое вам нужно из набора {000, 001, 010, 011, 100, 101} является k-1, Это объясняет F(N^(1<<MSB(N)), k-1) срок.
Набор чисел <=N, с MSB быть меньше чем N являются {000, 001, 010, 011, 100, 101, 110, 111}, Другими словами, все числа <= (1<<MSB(N)) - 1 = 1000 - 1 = 111, До сих пор вы не учитывали ни одного установленного бита. Итак, вам все еще нужно k биты из чисел в наборе {000, 001, 010, 011, 100, 101, 110, 111}, Вот где F((1<<MSB(N))-1, k) срок исходит от.
Другие решения
detector