二进制表示中连续数的最大长度

Question

试图在包含负数的二进制表示中找到1的最大长度。在以下代码中input_file是一个文本文件，其中：

• 第一行是带有样本整数的多行
• 从第二行开始的每一行只有一个样本整数

示例文件：

4-样本数量

3-样本

0-

1-

2-

结果：2

任务：打印输入文件中所有样本整数中找到的最大整数数。找到需要O（n）时间且只需一次通过所有样本的解决方案

如何修改解决方案以处理任意大小的负整数（或至少针对n ≤ 10000）呢

更新：

据我所知，负数的二进制表示是基于二的补码（https://en.wikipedia.org/wiki/Two的_补码）。例如：

+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: 这是Yandex竞赛培训页面的第二项任务： https://contest.yandex.ru/contest/8458/enter/?lang=en

您需要在那里注册以测试您的解决方案

到目前为止，这里给出的所有解决方案都在测试9中失败

更新3:Haskell中通过所有Yandex测试的解决方案

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需要2的二进制补码

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

这导致：

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

所以为了消除无限精度的影响，我们可以显示2对固定位数的补码。此处使用16，因为OP提到的数字是<；10, 000.

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

最大长度的代码简化

最大长度可以减少到：

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