Подсчет единиц в двоичном представлении чисел от A до B

@Csharper@ · Регистрация: 18.09.2013

Author24 — интернет-сервис помощи студентам

Как быстро можно посчитать количество единиц от A до B, где 0 < A <= B < 10^16.
Заранее благодарю!

@krapotkin · 21.03.2015, 20:08

думаю, нужно проанализировать ряд хотя бы 256 чисел
и подумать, нет ли закономерности
1 = 0001 (1)
2 = 0010 (1)
3 = 0011 (2)
4 = 0100 (1)
5 = 0101 (2)
6 = 0110 (2)
7 = 0111 (3)
8 = 1000 (1)
9 = 1001 (2)
10 = 1010 (2)
11 = 1011 (3)
12 = 1100 (2)
13 = 1101 (3)
14 = 1110 (3)
15 = 1111 (4)

@Qwertiy · 22.03.2015, 13:08

res = calc(b) - calc(a-1)

вычисление от 0 до a можносделать за количество бит. Или даже формулу вывести - для единиц она вроде простая, для нулей было бы сложнее, если лидирующие считать не надо.

Добавлено через 10 минут
Рассмотрим число, равное 2^k. Все числа строго меньшие его содержат 50% единиц от k*2^k, т. е. k*2^(k-1).
Этого должно быть достаточно чтобы пройти по единичным битам и посчитать нужное знаечение как сумму.

Javascript

1 2	for(k=0; k<10; ++k) console.log(k, 1<<k, k*(1<<(k-1)))

Код

@Mysterious Light · 22.03.2015, 13:12

Посудите сами (все числа записываю в двоичной системе)
от 0 до 1 — 1 единица, от 0 до 11 — 100, от 0 до 111 — 1100,
в общем случае от 0 до (10^n)-1 насчитывается S(n) единиц, где

$https://www.cyberforum.ru/cgi-bin/latex.cgi?S(1) = 1, \qquad S(n+1) = 10 S(n) + 10^n.$

Пусть U(A) — число единиц от 0 до A, и пусть , . Тогда

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{array}{ll} U(A) & = S(n) \, +\, (\overline{a_{n-1}\ldots a_1a_0} + 1) \,+\, U(\overline{a_{n-1}\ldots a_1a_0}) \,= \\<br /> &=\, S(n) \,+\, (\overline{a_{n-1}\ldots a_1a_0} + 1) \,+\, a_{n-1} S(n-1) \,+\, a_{n-1}(\overline{a_{n-2}\ldots a_1a_0} + 1) \,+\, U(\overline{a_{n-2}\ldots a_1a_0}) \, =\\<br /> &=\,\ldots\,=\\<br /> & =\, \sum_{k=1}^n a_k S(k) \,+\, \sum_{k=1}^n a_k (\overline{a_{k-1}\ldots a_0} + 1) \,\pm\, a_{0} \,\pm\, \rm{const}.<br /> \end{matrix}$

В последних двух членах не уверен, нужны ли. Впрочем, они калибруются.

Количество единиц от A до B — это U(B) - U(A-1).

Haskell

-- переводим число в двоичное представление
d :: Integer -> [Integer]
d 0 = [];
d 1 = [1];
d n = d (div n 2) ++ [rem n 2]
 
-- переводим из двоичного представления обратно
p :: [Integer] -> Integer
p = foldl (\a x -> a*2 + x) 0
 
-- эти функции взаимообратные
-- d . p = id
-- p . d = id
 
-- S(n), см. формулу выше
s :: Integer -> Integer
s 1 = 1;
s n = 2 * s(n-1) + 2^(n-1)
 
-- U(A), A задаётся двоичным представлением.
-- здесь использую рекурсивное определение
u :: [Integer] -> Integer
u [] = 0;
u [a] = a;
u (a:aaa) = a * s(length aaa) + a * (p aaa + 1) + u aaa
 
-- выведем таблицу число-разложение-количество единиц
*Main> mapM_ (\n -> putStrLn $
    show n ++ "\t- " ++ show (d n) ++ "\t- " ++ show (u (d n))) [1..20]
1   - [1]   - 1
2   - [1,0] - 2
3   - [1,1] - 4
4   - [1,0,0]   - 5
5   - [1,0,1]   - 7
6   - [1,1,0]   - 9
7   - [1,1,1]   - 12
8   - [1,0,0,0] - 13
9   - [1,0,0,1] - 15
10  - [1,0,1,0] - 17
11  - [1,0,1,1] - 20
12  - [1,1,0,0] - 22
13  - [1,1,0,1] - 25
14  - [1,1,1,0] - 28
15  - [1,1,1,1] - 32
16  - [1,0,0,0,0]   - 33
17  - [1,0,0,0,1]   - 35
18  - [1,0,0,1,0]   - 37
19  - [1,0,0,1,1]   - 40
20  - [1,0,1,0,0]   - 42

Впрочем, это не отменяет кода Qwertiy

@Qwertiy · 22.03.2015, 13:49

Сообщение от Mysterious Light

в общем случае от 0 до (10^n)-1 насчитывается S(n) единиц, где

Эм.. По условию задачи представление чисел нужно двоичное, а не десятичное. Что за 10^n? Или это двоичные 10?
И вообще, что-то сложное получилось. Задача должна решаться 2 вызовами функции из 2 циклов, насколько я представляю.

@krapotkin · 22.03.2015, 14:15

Сообщение от Qwertiy

Задача должна решаться 2 вызовами функции из 2 циклов

даже 1 цикла достаточно

вопрос только, доживет ли препод до результата, если введет 10^16

@Qwertiy · 22.03.2015, 14:26

Там (lb(x))^2 должно бы получиться, может быть даже до lb(x) возможно упростить.
Просто надо детально продумать, что на что умножать.
Ну и другой вариант - просто динамику написать.

@krapotkin · 22.03.2015, 14:33

в лоб решение предельно простое
делить переменную пополам, пока не получится 0
на каждом шаге проверять остаток от деления
если =1, то увеличивать счетчик

если получилось так, познакомьте с кодом)

@Qwertiy · 22.03.2015, 14:44

Сообщение от Mysterious Light

lb(x) это что?

log2, binary logarithm
x - значение, для которого считаем

Сообщение от krapotkin

если получилось так, познакомьте с кодом)

Нет, так не получится. Надо тот цикл что я привёл как-то прикрутить к проходу по битам.

@Mysterious Light · 22.03.2015, 14:54

Для Qwertiy и остальных алгоритм из Подсчет единиц в двоичном представлении чисел от A до B, переписанный на JavaScript

Javascript

var U = function(a) {
  var n = 0;
  var b = 0;
  var u = a%2;
  while(a > 0) {
    b = b + (a%2) * (1<<n);
    a = a>>1;
    ++ n;
    u += (a%2) * (n * (1<<(n-1)) + b + 1);
  }
  return u;
};
 
for(var k = 1; k < 10; ++k) writeln(k + ". " + U(k));

Код

Что характерно, работает за O(log(a)).
Для меня прямая манипуляции с битами — лунная грамота, поэтому прошу подправить, если что-то можно, для красоты. Писал, как умел.

@krapotkin · 22.03.2015, 16:34

ну, это написано ровно то что я текстом описал )
теперь задача - запустите это с параметром a = 10^16

@Qwertiy · 22.03.2015, 16:57

Ну перепиши на си++ и запусти.

Подсчет единиц в двоичном представлении чисел от A до B

Решение

Решение

@Csharper@ 0 / 0 / 0 Регистрация: 18.09.2013 Сообщений: 24
		1
	Подсчет единиц в двоичном представлении чисел от A до B 21.03.2015, 11:09. Показов 5881. Ответов 11 Метки нет (Все метки) Как быстро можно посчитать количество единиц от A до B, где 0 < A <= B < 10^16. Заранее благодарю! 0

@krapotkin 5786 / 4528 / 1431 Регистрация: 14.04.2014 Сообщений: 20,157 Записей в блоге: 20
	21.03.2015, 20:08	2
	думаю, нужно проанализировать ряд хотя бы 256 чисел и подумать, нет ли закономерности 1 = 0001 (1) 2 = 0010 (1) 3 = 0011 (2) 4 = 0100 (1) 5 = 0101 (2) 6 = 0110 (2) 7 = 0111 (3) 8 = 1000 (1) 9 = 1001 (2) 10 = 1010 (2) 11 = 1011 (3) 12 = 1100 (2) 13 = 1101 (3) 14 = 1110 (3) 15 = 1111 (4) 0

@Qwertiy 833 / 641 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	22.03.2015, 13:49	5
	Сообщение от Mysterious Light в общем случае от 0 до (10^n)-1 насчитывается S(n) единиц, где Эм.. По условию задачи представление чисел нужно двоичное, а не десятичное. Что за 10^n? Или это двоичные 10? И вообще, что-то сложное получилось. Задача должна решаться 2 вызовами функции из 2 циклов, насколько я представляю. 0

@krapotkin 5786 / 4528 / 1431 Регистрация: 14.04.2014 Сообщений: 20,157 Записей в блоге: 20
	22.03.2015, 14:15	6
	Сообщение от Qwertiy Задача должна решаться 2 вызовами функции из 2 циклов даже 1 цикла достаточно вопрос только, доживет ли препод до результата, если введет 10^16 0

@Qwertiy 833 / 641 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	22.03.2015, 14:26	7
	Там (lb(x))^2 должно бы получиться, может быть даже до lb(x) возможно упростить. Просто надо детально продумать, что на что умножать. Ну и другой вариант - просто динамику написать. 0

@krapotkin 5786 / 4528 / 1431 Регистрация: 14.04.2014 Сообщений: 20,157 Записей в блоге: 20
	22.03.2015, 14:33	8
	в лоб решение предельно простое делить переменную пополам, пока не получится 0 на каждом шаге проверять остаток от деления если =1, то увеличивать счетчик если получилось так, познакомьте с кодом) 0

@Qwertiy 833 / 641 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	22.03.2015, 14:44	9
	Сообщение от Mysterious Light lb(x) это что? log2, binary logarithm x - значение, для которого считаем Сообщение от krapotkin если получилось так, познакомьте с кодом) Нет, так не получится. Надо тот цикл что я привёл как-то прикрутить к проходу по битам. 1

@krapotkin 5786 / 4528 / 1431 Регистрация: 14.04.2014 Сообщений: 20,157 Записей в блоге: 20
	22.03.2015, 16:34	11
	ну, это написано ровно то что я текстом описал ) теперь задача - запустите это с параметром a = 10^16 0

@Qwertiy 833 / 641 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	22.03.2015, 16:57	12
	Ну перепиши на си++ и запусти. 0