Maximum length of consecutive ones in binary representation

Question

Trying to find maximum length of ones in a binary representation including negative numbers. In the following code input_file is a text file where:

• first line is a number of lines with sample integers
• every line staring from the second line has just one sample integer

An example file:

4 - number of samples

3 - sample

0 - ...

1 - ...

2 - ...

Result: 2

Task: print the maximum number of ones found among all sample integers in input file. Find solution that takes O(n) time and makes just one pass through all samples.

How to modify solution to work with negative integers of arbitrary (or at least for n ≤ 10000) size?

Update:

As I understand binary representation of negative numbers is based on Two's complement (https://en.wikipedia.org/wiki/Two's_complement). So, for example:

+3 -> 011

-3 -> 101

How to convert integer to binary string representation taking its sign into account in general case?

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'))

Update 2: This is a second task B from Yandex contest training page: https://contest.yandex.ru/contest/8458/enter/?lang=en

You need to register there to test your solution.

So far All solutions given here fail at test 9.

Update 3: Solution in Haskell that pass all Yandex tests

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

Assumption

OP wants two's complement binary.

Python's integers already use two's complement, but since they have arbitrary precision, the binary representation of negative numbers would have an infinite string of 1s at the start, much like positive numbers have an infinite string of 0s. Since this obviously can't be shown, it is represented with a minus sign instead. reference

This results in:

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

So to remove the effect of the infinite precision we can show 2's complement to a fixed number of bits. Use 16 here since OP mentions numbers are < 10, 000.

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

Example Using 2's Complement

Test Code

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)}')

Test Output

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

Code

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_

Code Simplification of max_len

max_len could be reduced to:

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))))

Answer 2

For negative numbers, you will either have to decide on a word length (32 bits, 64 bits, ...) or process them as absolute values (i.e. ignoring the sign) or use the minimum number of bits for each value.

An easy way to control the word length is to use format strings. you can obtain the negative bits by adding the value to the power 2 corresponding to the selected word size. This will give you the appropriate bits for positive and for negative numbers.

For example:

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

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

Processing that to count the longest series of consecutive 1s is just a matter of string manipulation:

If you choose to represent negative numbers using a varying word size you can use one bit more than the minimal representation of the positive number. For example -3 is represented as two bits ('11') when positive so it will need a minimum of 3 bits to be represented as a negative number: '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')