如何生成一个时间复杂度为 O(n) 且重复次数如 100100100…1 的二进制整数?

问题描述 投票:0回答:1

我正在制作一个函数,以

length:int
distance:int
作为输入,并输出在其二进制表示中满足以下属性的最大整数:

  1. 1
    开头,以
    1

    结束
  2. 每个

    distance - 1
    之间有
    0
    很多
    1

  3. 其长度严格小于

    length

可以按如下方式实现:

def repeatdigit(length:int, distance:int) -> int:
   result = 0
   pointer = 1
   for _ in range(1, length, distance):
      result |= pointer
      pointer <<= distance
   return result

例如:

repeatdigit(10,3)==0b1001001
repeatdigit(15,4)=0b1000100010001
。我只关心二进制,因为我需要将它用作位操作的工具。实际上,
length
会很大,
distance ** 2 < length
。假设输入有效。

顾名思义,它一遍又一遍地重复相同的模式。

一个明确的公式:

result = (1 << (length+distance-2 - ((length-2) % distance)))//((1 << distance) - 1)

但这两种算法都很慢,它们的时间复杂度都是 O(n²),其中 n =

length

用列表做类似的事情只需要 O(n)。即

([1]+[0]*(distance-1)) * ((length-2)//distance) + [1]

(上下文:我想制作这样一个整数,这样我就不需要将 0 和 1 存储在很长的列表中,因为它很占用空间)

如何在 O(n) 时间内生成这样一个整数?

python optimization bit-manipulation
1个回答
0
投票

将 1 位的数量加倍,而不是一次只添加一个:

def repeatdigit(length:int, distance:int) -> int:
   def f(want):
      if want == 1:
         return 1
      have = (want + 1) // 2
      x = f(have)
      add = min(have, want - have)
      return x | (x << (add * distance))
   ones = 1 + (length - 2) // distance
   return f(ones)
© www.soinside.com 2019 - 2024. All rights reserved.