Как оптимизировать подсчёт единичных битов в числах?

Question

Даны два числа: «левое» и «правое» (1 <= «левое» <= «правое» <= 2000000000000000). Вернуть сумму всех вхождений «1» в двоичных представлениях чисел между «левым» и «правым» (включая оба).

Например: countOnes(4, 7) должно вернуть 8, потому что:

4(dec) = 100(bin), которое добавит 1 в результат
5(dec) = 101(bin), которое добавит 2 в результат
6(dec) = 110(bin), которое добавит 2 в результат
7(dec) = 111(bin), которое добавит 3 в результат

Финальный результат будет 8.

Как оптимизировать код? Желательно, чтобы время не превышало 6000мс.

def countOnes(left, right):
    do=[]
    c=0

    for j in range(left,right+1):
        while j>0:
            do.append(j%2)
            j//=2
            ans=""
            for i in do[::-1]:
                ans+=str(i) 
          
    arr=(ans)
    for i in arr:
        if i=="1":
            c+=1
   
    return c

Answer 1

Если код, как вы написали, должен считать количество единиц в двоичном числе, то подойдет следующий вариант:

def get_one(number):
    bin_num = bin(number)[2::]
    return bin_num.count('1')


get_one(10) # --> 2

Answer 2

Для подсчёта единичных битов в числах от 1 до n можно использовать такой подход:
Если подсчитать биты в числах, меньших, чем 2^k, то получится довольно простая формула k*2^k-1 (можно доказать по индукции). Например, в диапазоне 1..15 будет 4 * 2³ = 32 единичных бита.

Поэтому можно найти наибольшую степень двойки t=2^k, не превосходящую данное число, и по формуле получить число битов до неё. А оставшиеся числа (p=n-t+1 штук) обработаем рекурсивно, учитывая p старших единиц.

Например, для n=6 получаем степень двойки t=4, имеем 4 единички для диапазона 1..3, остаются числа 4..6. Их три штуки, у всех старший (второй) бит единичный, поэтому добавляем 3 единички, и рекурсивный вызов для числа 6-4=2 даст ещё 2 единички, всего 9

Сложность логарифмическая O(log(n)), расчёт будет мгновенный для очень больших чисел, например:

9999999999999999999999999999999999999999999999999: 
812343836660373030250828481978822227703908777590784

Как из этого получить решение для диапазона от A до B - наверное, понятно.

def bitcnt(n):
    if n < 2:
        return n
    t = 1
    b = 0
    while 2*t <= n:
        t *= 2
        b += 1
    return b*(1<<(b-1)) + (n-t+1) + bitcnt(n-t)

Answer 3

Ваш код можно оптимизировать, но в шесть секунд он не уложится никак. Так будет с любым кодом, который непосредственно считает биты. Нужно проанализировать постановку задачу заново.

Пусть g(n) число единичных бит в числе. Пусть f(n) число единичных бит во всех числах [0, n). Тогда верно что

f(0) = 0
f(2n) = 2f(n) + n
f(n + 1) = g(n) + f(n)

Второе равенство нуждается в объяснении:

Пусть k < n. Выпишем числа 2k и 2k + 1. Они отличаются только младшим битом и для них верны соотношения для g:

110...01010   # g(2k) = g(k)
110...01011   # g(2k + 1) = g(k) + 1

Все числа в [0, 2n) разобьём на пары (будет n пар). В каждой паре применим уравнения для g и получим g(2k) + g(2k + 1) = 2g(k) + 1. Сумма всех n уравнений: f(2n) = 2f(n) + n.

Через функцию f можно выразить нужное нам число: f(right + 1) - f(left).

Можно программировать:

def g(n):
    return bin(n).count('1')


def f(n):
    if n == 0:
        return 0
    if n % 2 == 0:
        return 2 * f(n // 2) + n // 2
    return g(n - 1) + f(n - 1)


def count(left, right):
    return f(right + 1) - f(left)


print(count(*map(int, input().split())))

$ echo 4 7 | python count_ones.py
8

$ echo 1 200000000000000 | python count_ones.py
4712825299386385

БЛОГ НА HUSL

Как оптимизировать подсчёт единичных битов в числах?

Ответы (3 шт):