Вот предложение по ускорению:
Найдите наименьшее y1 такое, что y1> = x1 и y1 является степенью 2
Найдите наибольшее y2 такое, что y2 <= x2, а y2 - степень 2 </p>
Найдите p1 и p2 такие, что 2 ^ p1 = y1 и 2 ^ p2 = y2
Рассчитать сумму 1: s между y1 и y2
Разобраться с x1 до y1 и y2 до x2 отдельно
Суммируйте результаты 4 и 5
Давайте сосредоточимся на шаге 4. Пусть f (n) будет суммой единиц до (2 ^ n) -1.Мы можем быстро понять, что f (n) = 2 * f (n-1) + 2 ^ (n-1) и что f (1) = 1.Это может быть еще более улучшено, чтобы вам не приходилось иметь дело с рекурсивными вызовами, но я очень сомневаюсь, что это будет иметь какое-либо значение.В любом случае, f (n) = n * 2 ^ (n-1)
Чтобы получить результат между y1 и y2, просто используйте f (p2) -f (p1)
Для шага5, вы, вероятно, можете использовать модифицированную версию шага 4.
РЕДАКТИРОВАТЬ:
Может быть, я должен был быстро сказать "быстро понять".Вот способ понять это.Количество до 2¹-1 легко увидеть.Только два двоичных числа ниже 2¹ - это 0 и 1. Чтобы получить число единиц до 2², мы берем числа ниже 2¹ и делаем столбец:
0
1
Клонируем его:
0
1
0
1
И поставить 0: s перед первой половиной и 1: s перед второй половиной:
00
01
10
11
Чтобы получить 2³, мы делаем то же самое.Клонируйте его:
00
01
10
11
00
01
10
11
И добавьте 0 и 1:
000
001
010
011
100
101
110
111
Теперь должно быть легко понять, почему f (n) = 2 * f (n-1) + 2^ (п-1).Клонирование дает 2f (n-1) и добавление 0: s и 1: s дает 2 ^ (n-1).Если 2 ^ (n-1) трудно понять, помните, что 2 ^ (n-1) = (2 ^ n) / 2.На каждом шаге у нас есть 2 ^ n строк, и половина из них получает дополнительные 1.
EDIT2:
Когда я посмотрел на эти столбцы, у меня появилась идея, как выполнить шаг 5.Допустим, вы хотите найти суммы 1: с от 10 до 15. Двоичная таблица для этого будет:
10: 1010
11: 1011
12: 1100
13: 1101
14: 1110
15: 1111
Посмотрите на интервал 12-15.Последние две цифры в двоичном виде являются копией соответствующей таблицы для 0-3.Это можно использовать, но я оставляю это вам.
РЕДАКТИРОВАТЬ 3:
Это была забавная проблема.Я написал некоторый код Python, который делает это.У меня возникают некоторые проблемы со слишком большим количеством рекурсивных вызовов, но это может быть решено довольно легко, и не должно быть слишком сложно преобразовать это в C:
def f(n):
return n*2**(n-1)
def numberOfOnes(x):
if(x==0):
return 0
p = floor(log(x,2))
a = f(p)
b = numberOfOnes(x-2**p)
c = x - 2**p +1
return a+b+c
Я сделал изображение, чтобы вы могли легче понятьчто a, b и c делает в функции numberOfOnes, если мы вызываем ее с помощью numberOfOnes(12):
Iнаконец, преобразовал его в C. Конечно, я использовал некоторый код, который я нашел здесь при переполнении стека.Я позаимствовал код для целочисленных версий log2 и pow и сделал несколько небольших модификаций.
Этот код, вероятно, можно и дальше оптимизировать, но в этом нет необходимости.Он горит быстро, и я не смог измерить его производительность.
#include <stdio.h>
#include <math.h>
#include <assert.h>
#include <stdint.h>
#include <inttypes.h>
typedef uint64_t T;
// https://stackoverflow.com/a/11398748/6699433
const int tab64[64] = {
63, 0, 58, 1, 59, 47, 53, 2,
60, 39, 48, 27, 54, 33, 42, 3,
61, 51, 37, 40, 49, 18, 28, 20,
55, 30, 34, 11, 43, 14, 22, 4,
62, 57, 46, 52, 38, 26, 32, 41,
50, 36, 17, 19, 29, 10, 13, 21,
56, 45, 25, 31, 35, 16, 9, 12,
44, 24, 15, 8, 23, 7, 6, 5};
T log2_64 (T value) {
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
value |= value >> 16;
value |= value >> 32;
return tab64[((T)((value - (value >> 1))*0x07EDD5E59A4E28C2)) >> 58];
}
// https://stackoverflow.com/a/101613/6699433
T ipow(T base, T exp) {
T result = 1;
for (;;) {
if (exp & 1) result *= base;
exp >>= 1;
if (!exp) break;
base *= base;
}
return result;
}
T f(T n) { return ipow(2,n-1)*n; }
T numberOfOnes(T x) {
if(x==0) return 0;
T p = floor(log2(x));
T a = f(p);
T e = ipow(2,p);
T b = numberOfOnes(x-e);
T c = x - e + 1;
return a+b+c;
}
void test(T u, T v) {
assert(numberOfOnes(u) == v);
}
int main() {
// Sanity checks
test(0,0);
test(1,1);
test(2,2);
test(3,4);
test(4,5);
test(5,7);
test(6,9);
// Test case provided in question
test(1000000000,14846928141);
}