Подсчет чисел от 1 до N (включительно), где установлен i-й бит - PullRequest
Новая
       19

Подсчет чисел от 1 до N (включительно), где установлен i-й бит

2 голосов
/ 02 июня 2019

Я хочу посчитать, сколько целых чисел от 1 до N имеет установленный i бит.Например, если N = 10 и i = 0, то результат должен быть 5 (потому что 1 = 0001 2 , 3 = 0011 2, 5 = 0101 2 , 7 = 0111 2 и 9 = 1001 2 каждый имеет 1 в бит 0).

Наивное линейное решение состоит в том, чтобы выполнить итерацию от 1 до N и, для каждого числа, посмотреть, установлен ли у него i -й бит.

Aнемного лучший подход был бы, потому что для известной степени 2 (скажем, 2 x ), 2 x -1 будут иметьих i -й бит установлен в число 2 x - 1, где 0 ≤ i i -ым битом, установленным начиная с ( N - 2 x ), где N - это число до тех пор, пока мы не попытаемся найти все числа с установленным битом i , а 2 x - ближайшая степень 2 для числа N .Этот подход уменьшает количество итераций, но все еще является решением с линейным временем и в некоторых случаях может быть очень бесполезным для больших чисел.

Существует ли решение с постоянным временем?

1 Ответ

4 голосов
/ 02 июня 2019

Давайте сначала посмотрим на пример. Если мы установим n=10, и мы посмотрим на второй бит, поэтому k=1 справа, мы увидим: 

00<b>0</b>0    0
00<b>0</b>1    0
00<b>1</b>0    1
00<b>1</b>1    2
01<b>0</b>0    2
01<b>0</b>1    2
01<b>1</b>0    3
01<b>1</b>1    4
----
10<b>0</b>0    4
10<b>0</b>1    4
10<b>1</b>0    5

Здесь мы видим, что есть N / 2 k + 1 & rfloor; полный круговые поездки из k - бит, и каждое такое обратное прохождение приводит к 2 k установленным битам. Мы сгруппировали эти записи перед горизонтальной чертой.

Кроме того, есть еще N + 1 - 2 k + 1 & times; & lfloor; N / 2 k + 1 & rfloor; записей под турник. Мы точно знаем, что это на меньше , чем 2 k , поскольку в противном случае N / 2 k & rfloor; будет на один выше. Первые 2 k-1 записей имеют 0 в качестве выбранного бита, а остальные биты (не более 2 k-1 записи) имеют 1 в качестве выбранного бита.

Таким образом, мы можем построить следующий алгоритм в Haskell: 

countBit k n = c1 +  max 0 (n + 1 - c0 - sk)
    where sk = shiftL 1 k
          c1 = shiftL (shiftR n (k+1)) k
          c0 = shiftL c1 1

Например, для k=1 мы получаем следующие значения: 

Prelude Data.Bits> map (countBit 0) [0..32]
[0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16]
Prelude Data.Bits> map (countBit 1) [0..32]
[0,0,1,2,2,2,3,4,4,4,5,6,6,6,7,8,8,8,9,10,10,10,11,12,12,12,13,14,14,14,15,16,16]
Prelude Data.Bits> map (countBit 2) [0..32]
[0,0,0,0,1,2,3,4,4,4,4,4,5,6,7,8,8,8,8,8,9,10,11,12,12,12,12,12,13,14,15,16,16]
Prelude Data.Bits> map (countBit 3) [0..32]
[0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,8,8,8,8,8,8,8,8,9,10,11,12,13,14,15,16,16]
Prelude Data.Bits> map (countBit 4) [0..32]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,16]

Итак, для n=10 и k=1 мы получаем ожидаемое: 

Prelude Data.Bits> countBit 0 10
5
Prelude Data.Bits> countBit 1 10
5

Или мы можем посчитать количество установленных бит в столбце k=3 для чисел от 0 до 12345 (включительно) с помощью: 

Prelude Data.Bits> countBit 3 12345
6170

или k=15 и n=12'345'678'901'234'567'890

Prelude Data.Bits> countBit 15 12345678901234567890
6172839450617282560

и для n=123'456'789'012'345'678'901'234'567'890: 

Prelude Data.Bits> countBit 15 123456789012345678901234567890
61728394506172839450617282560

Здесь мы выполняем некоторые битовые смещения и вычитания, для больших чисел это можно сделать за O (log N) время (с N значением верхней границы).

...