Нахождение общего количества битов от 1 до n

Question

Напишите алгоритм, чтобы найти F(n) количество бит, установленное в 1, во всех числах от 1 до n для любого заданного значения n.

Сложность должна быть O(log n)

Например:

1: 001
2: 010
3: 011
4: 100
5: 101
6: 110

So

F(1) = 1,  
F(2) = F(1) + 1 = 2,
F(3) = F(2) + 2 = 4,
F(4) = F(3) + 1 = 5,
etc.

Я могу только разработать алгоритм O(n).

Answer 1

Способ решения подобных проблем состоит в том, чтобы выписать первые несколько значений и найти шаблон

Number  binary   # bits set   F(n)
1       0001     1            1
2       0010     1            2
3       0011     2            4
4       0100     1            5
5       0101     2            7
6       0110     2            9
7       0111     3            12
8       1000     1            13
9       1001     2            15
10      1010     2            17
11      1011     3            20
12      1100     2            22
13      1101     3            25
14      1110     3            28
15      1111     4            32

Требуется немного посмотреть, но, подумав, вы заметили, что двоичные представления первых 8 и последних 8 чисел абсолютно одинаковы, за исключением того, что первые 8 имеют 0 в MSB (старший значащий бит) , в то время как последние 8 имеют 1. Таким образом, например, чтобы вычислить F(12), мы можем просто взять F(7) и добавить к нему количество установленных битов в 8, 9, 10, 11 и 12. Но это то же самое, что число установленных битов в 0 , 1, 2, 3 и 4 (т. Е. F(4)) , плюс еще один для каждого номера!

#    binary
0    0 000
1    0 001
2    0 010
3    0 011
4    0 100
5    0 101
6    0 110
7    0 111

8    1 000  <--Notice that rightmost-bits repeat themselves
9    1 001     except now we have an extra '1' in every number!
10   1 010
11   1 011
12   1 100

Таким образом, для 8 <= n <= 15, F(n) = F(7) + F(n-8) + (n-7). Точно так же можно отметить, что для 4 <= n <= 7, F(n) = F(3) + F(n-4) + (n-3); и для 2 <= n <= 3, F(n) = F(1) + F(n-2) + (n-1). В общем, если мы установим a = 2^(floor(log(n))), то F(n) = F(a-1) + F(n-a) + (n-a+1)

---

Это не совсем дает нам алгоритм O(log n); однако сделать это легко. Если a = 2^x, то обратите внимание в таблице выше, что для a-1 первый бит установлен ровно a/2 раз, второй бит установлен ровно a/2 раз, третий бит ... вплоть до х-й бит Таким образом, F(a-1) = x*a/2 = x*2^(x-1). В приведенном выше уравнении это дает нам

F(n) = x*2<sup>x-1</sup> + F(n-2<sup>x</sup>) + (n-2<sup>x</sup>+1)

Где x = floor(log(n)). Каждая итерация вычисления F будет по существу удалять MSB; таким образом, это алгоритм O(log(n)).

Answer 2

Если n= 2^k-1, then F(n)=k*(n+1)/2

Для общего n, пусть m будет наибольшим числом, таким как m = 2^k-1 и m<=n.F(n) = F(m) + F(n-m-1) + (n-m).

Состояние угла: F(0)=0 и F(-1)=0.

Answer 3

рассмотрите следующее:

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

Если вы хотите найти общее количество установленных битов от 1 до 14 (1110), несколько наблюдений:

1. 0th бит(LSB) 1 бит появляется один раз каждые два бита (см. По вертикали), поэтому число установленных битов = n/2 + (1, если n's 0th bit is 1 else 0)
2. 1-й бит: 2 последовательных 1 споявляются каждые четыре бита (см. 1-й бит по вертикали по всем числам) количество установленных бит в 1st позиция бита = (n/4 *2) + 1 (поскольку 1st бит - это набор, иначе 0)
3. 2nd бит: 4 подряд 1s появляются каждые 8 биты (этот хитрый бит) количество битов, установленных во 2-й позиции = (n/8*4 )+ 1 (так как 2nd бит установлен, иначе 0) + ((n%8)%(8/2)) Последний член должен включать число 1s, которые были за пределами первой (n/8) группы битов (14/8 =1 рассматривает только группу 1, т.е. 4 устанавливает биты в 8 битах. Нам нужновключают 1s, найденные в последних 14-8 = 6 битах)
4. 3rd бит: 8 последовательные 1 появляются каждые 16 бит (аналогично приведенному выше) число установленных биts в 3rd position = (n/16*8)+1 (поскольку установлен 3rd бит, иначе 0) + ((n%16)%(16/2))

, поэтому мы делаем O(1) вычисление для каждого бита числа n.число содержит log2(n) бит.поэтому, когда мы повторяем вышеупомянутое для всех позиций n и добавляем все установленные биты на каждом шаге, мы получаем ответ в O(logn) шагов

Answer 4

Вот мое решение для этого. Временная сложность: O (Log n)

public int countSetBits(int n){
    int count=0;
    while(n>0){
        int i= (int)(Math.log10(n)/Math.log10(2));
        count+= Math.pow(2, i-1)*i;
        count+= n-Math.pow(2, i)+1;
        n-= Math.pow(2, i);
    }
    return count;
}

Answer 5

Быстрый поиск значений последовательности F приводит к этой целочисленной последовательности http://oeis.org/A000788

Там я заметил формулу: a (0) = 0, a (2n) = a (n) +a (n-1) + n, a (2n + 1) = 2a (n) + n + 1 (a - это то же самое, что и F, поскольку я просто копирую формулу из oeis)

, которую можно использоватьвычислить (n) в журнале (n).

Вот мой пример кода C ++:

memset(cache, -1, sizeof(cache))
cache[0] = 0

int f(int n)
    if cache[n] != -1 return cache[n];
    cache[n] = n % 2 ? (2 * f(n / 2) + n / 2 + 1) : (f(n / 2) + f(n / 2 - 1) + n / 2)

Answer 6

Пусть k будет количеством битов, необходимых для n.

для 0,...,2^(k-1)-1 каждый бит увеличен ровно на половину чисел, поэтому у нас пока есть (k-1)*2^(k-1)/2 = (k-1)*2^(k-2) бит. Нам нужно только проверить, что случилось с числами, которые больше, чем 2^(k-1)-1
У нас также есть для этих n-2^(k-1)-1 битов "вверх" для MSB.

Итак, мы можем вывести рекурсивную функцию:

f(n) = (k-1)*2^(k-2) + n-(2^(k-1)-1) + f(n-(2^(k-1)))
           ^               ^            ^
         first            MSBs        recursive call for 
       2^(k-1)-1                      n-2^(k-1) highest numbers
        numbers

Где base f(0) = 0 и f(2^k) = k*2^(k-1) + 1 [как мы видели ранее, мы точно знаем, сколько битов для 2^(k-1)-1, и нам просто нужно добавить 1 - для MSB 2^k]

Поскольку значение, отправляемое на f, уменьшается как минимум на половину на каждой итерации, мы получаем всего O(logn)

Answer 7

коротко и сладко!

 public static int countbits(int num){
    int count=0, n;
    while(num > 0){
        n=0;
        while(num >= 1<<(n+1))
            n++;
        num -= 1<<n;
        count += (num + 1 + (1<<(n-1))*n);
    }
    return count;
}//countbis

Answer 8

for i in range(int(input())):
    n=int(input())
    c=0
    m=13

    if n==0:
        print(c)
    while n%8!=0 or n!=0:
        t=bin(n)[2:]
        c+=t.count('1')
        n=n-1
    if n!=0:
        j=n//8
        if j==1:
            c+=m
        else:
            c+=m+((j-1)*7)
    print(c)        

Answer 9

Не уверен, что уже поздно отвечать, но вот мои выводы.

Попытка решения проблемы с использованием следующего подхода, для числа N каждое битное значение (от LSB до MSB, скажем, LSB начинается с битно 1 и увеличивается с увеличением следующего значения бита). Количество установленных битов можно вычислить как битно) * (2 верхних битно-1) + {(N% (2 верхних битно-1) - - (2 верхних битно-1) - 1]}

Написали рекурсивную функцию для него C / C ++, пожалуйста, проверьте. Я не уверен, но я думаю, что его сложность - log (N). Передайте параметры функции 2, число (нет), для которого мы хотим вычислить биты, и счетчик второго старта из LSB, значение 1.

int recursiveBitsCal(int no, int bitno){
int res = int(no/pow(2,bitno))*int(pow(2,bitno-1));
int rem1 = int(pow(2,bitno-1)) -1;
int rem = no % int(pow(2,bitno));
if (rem1 < rem) res += rem -rem1;
if ( res <= 0 )
    return 0;
else
    return res + recursiveBitsCal(no, bitno+1);
}

Answer 10

Кстати, этот вопрос также можно решить методом таблицы поиска.Предварительно вычислите количество установленных битов от 0 до 255 и сохраните его.После этого мы можем вычислить количество установленных битов в любом числе, разбив данное число на две части по 8 бит в каждой.Для каждой части мы можем искать в массиве count, сформированном на первом шаге.Например, если существует 16-битное число, например,

x = 1100110001011100, то здесь число установленных битов = количество установленных бит в первом байте + количество установленных бит во втором байте.Следовательно, для получения первого байта,

y = (x & 0xff) z = (x >> 8) & (0xff) total set bits = count[y] + count[z]

Этот метод также будет работать в O (n).