Максимальная длина последовательных в двоичном представлении

Question

Попытка найти максимальную длину единиц в двоичном представлении, включая отрицательные числа. В следующем коде input_file представляет собой текстовый файл, где:

• первая строка - это число строк с целыми числами образца
• каждая строка, начинающаяся со второй строки, содержит только одно целое число образца

Файл примера:

4 - количество образцов

3 - образец

0 - ...

1 - ...

2 - ...

Результат: 2

Задача: вывести максимальное число единиц, найденных среди всех целых чисел примера во входном файле. Найти решение, которое занимает O (n) времени и делает один проход через все выборки.

Как изменить решение для работы с отрицательными целыми числами произвольного (или хотя бы для n ≤ 10000) размера?

Обновление:

Как я понимаю, двоичное представление отрицательных чисел основано на дополнении Two (https://en.wikipedia.org/wiki/Two 's_complement). Так, например:

+ 3 -> 011

-3 -> 101

Как преобразовать целое число в двоичное строковое представление с учетом его знака в общем случае?

def maxConsecutive(input): 
    return max(map(len,input.split('0'))) 

def max_len(input_file):
    max_len = 0
    with open(input_file) as file:
        first_line = file.readline()
        if not first_line:
            return 0
        k = int(first_line.strip()) # number of tests
        for i in range(k):
            line = file.readline().strip()
            n = int(line)
            xs = "{0:b}".format(n)
            n = maxConsecutive(xs)
            if n > max_len:
                max_len = n
    return max_len

print(max_len('input.txt'))

Обновление 2: Это второе задание B со страницы обучения конкурса Яндекса: https://contest.yandex.ru/contest/8458/enter/?lang=en

Вам нужно зарегистрироваться там, чтобы протестировать свое решение.

Пока что все решения, приведенные здесь, терпят неудачу при тесте 9.

Обновление 3: Решение в Haskell которые проходят все тесты Яндекса

import Control.Monad (replicateM)

onesCount :: [Char] -> Int
onesCount xs = onesCount' xs 0 0
    where
        onesCount' "" max curr 
            | max > curr = max 
            | otherwise  = curr
        onesCount' (x:xs) max curr
            | x == '1' = onesCount' xs max $ curr + 1 
            | curr > max = onesCount' xs curr 0 
            | otherwise = onesCount' xs max 0

getUserInputs :: IO [Char]
getUserInputs = do
    n <- read <$> getLine :: IO Int
    replicateM n $ head <$> getLine

main :: IO ()
main = do
    xs <- getUserInputs 
    print $ onesCount xs

Answer 1

Для отрицательных чисел вам придется либо выбрать длину слова (32 бита, 64 бита, ...), либо обработать их как абсолютные значения (т. Е. Игнорировать знак), либо использовать минимальное количество бит для каждого значения .

Простой способ контролировать длину слова - использовать строки формата. Вы можете получить отрицательные биты, добавив значение к степени 2, соответствующее выбранному размеру слова. Это даст вам соответствующие биты для положительных и отрицательных чисел.

Например:

n = 123
f"{(1<<32)+n:032b}"[-32:]  --> '00000000000000000000000001111011'

n = -123
f"{(1<<32)+n:032b}"[-32:]  --> '11111111111111111111111110000101'

Обработка, чтобы подсчитать самую длинную серию последовательных 1-х, - это всего лишь вопрос манипуляции со строкой:

Если вы решили представлять отрицательные числа с помощью варьируя размер слова, вы можете использовать на один бит больше, чем минимальное представление положительного числа. Например, -3 представляется как два бита ('11'), когда положительный, поэтому для представления в виде отрицательного числа потребуется минимум 3 бита: '101'

n        = -123
wordSize = len(f"{abs(n):b}")+1
bits     = f"{(1<<wordSize)+n:0{wordSize}b}"[-wordSize:]
maxOnes  = max(map(len,bits.split("0")))

print(maxOnes) # 1   ('10000101')

Answer 2

Предположение

OP хочет двоичный код дополнения до двух. Целые числа

Python уже используют дополнение до двух, но, поскольку они имеют произвольную точность, двоичное представление отрицательных чисел будет иметь бесконечную строку 1 в начале, так же, как положительные числа имеют бесконечная строка 0 с. Поскольку это, очевидно, не может быть показано, вместо этого оно обозначается знаком минус. ссылка

Это приводит к:

>>> bin(-5)
'-0b101'

Таким образом, чтобы устранить эффект бесконечной точности, мы можем показать дополнение 2 к фиксированному числу битов. Используйте здесь 16, поскольку в OP упоминаются числа <10 000. </p>

>>> bin(-5 % (1<<16))            # Modulo 2^16
>> bin(-5 & 0b1111111111111111)  # 16-bit mask
'0b1111111111111011'

Пример использования дополнения 2

Код теста

result = []
for line in ['+3', '-3', '-25', '+35', '+1000', '-20000', '+10000']:
  n = int(line)
  xs = bin(n & 0b1111111111111011) # number in 16-bit 2's complement
  runs = maxConsecutive(xs)
  print(f"line: {line}, n: {n}, 2's complement: {xs}, max ones run: {runs}")
  result.append(runs)

print(f'Max run is {max(result)}')

Тестовый выход

line: +3, n: 3, 2's complement binary: 0b11, max ones run: 2
line: -3, n: -3, 2's complement binary: 0b1111111111111101, max ones run: 14
line: -25, n: -25, 2's complement binary: 0b1111111111100111, max ones run: 11
line: +35, n: 35, 2's complement binary: 0b100011, max ones run: 2
line: +1000, n: 1000, 2's complement binary: 0b1111101000, max ones run: 5
line: -20000, n: -20000, 2's complement binary: 0b1011000111100000, max ones run: 4
line: +10000, n: 10000, 2's complement binary: 0b10011100010000, max ones run: 3
Max run is 14

Код

def maxConsecutive(input):
    return max(map(len,input[2:].split('0')))  # Skip 0b at beginning of each

def max_len(input_file):
    max_len_ = 0
    with open(input_file) as file:
        first_line = file.readline()
        if not first_line:
            return 0
        k = int(first_line.strip()) # number of tests
        for i in range(k):
            line = file.readline().strip()
            n = int(line)
            xs = bin(n & '0b1111111111111011') # number in 16-bit 2's complement
            n = maxConsecutive(xs)
            if n > max_len_:
                max_len_ = n
    return max_len_

Упрощение кода из max_len

max_len может быть уменьшено до:

def max_len(input_file):
  with open(input_file) as file:
    return max(maxConsecutive(bin(int(next(file).strip()), 0b1111111111111011)) for _ in range(int(next(file))))