1

Даны два числа: «левое» и «правое» (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
5
  • 3
    Для начала поясните, что этот код должен делать.
    – Harry
    8 апр 2022 в 16:42
  • он должен считать еденицы полученные в результате перевода числа из десятичной системы в двоичную 8 апр 2022 в 16:57
  • 2
    Первое - зачем вы строки используете? Второе - вы хотите обрабатывать до 2*10^14 чисел? Пустой цикл в таком диапазоне будет выполняться ого-го сколько... Смотрим - пусть нужен только один такт процессора на число. Тогда этот такт должен длиться не дольше 3*10^-15 секунды, т.е. нужен процессор с тактовой частотой 333 Тгц... :) И все же, сформулируйте задачу ТОЧНО, То, что написали вы - это скорее вольная трактовка без точных деталей.
    – Harry
    8 апр 2022 в 17:02
  • 1
    Да уж, в таком диапазоне только если как-то аналитически задачу решать
    – CrazyElf
    8 апр 2022 в 17:26
  • Даны два числа: «левое» и «правое» (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 8 апр 2022 в 18:12

3 ответа 3

4

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

Поэтому можно найти наибольшую степень двойки t=2k, не превосходящую данное число, и по формуле получить число битов до неё. А оставшиеся числа (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)
4

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

Пусть 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
1

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

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


get_one(10) # --> 2
1
  • 5
    Для подсчёта в одном числе подойдёт, наверное, а для решения задачи с указанными ограничениями - увы...
    – MBo
    8 апр 2022 в 17:24

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.