代码之家 › 专栏 › 技术社区 › Mr. W

如何生成一个重复的整数,如二进制中的1001001001,时间复杂度为O(n)?

bit-manipulation optimization python

Mr. W · 技术社区 · 7 月前

我正在制作一个函数,它需要 length:int 和 distance:int 并输出在其二进制表示中满足以下属性的最大整数:

它始于 1 ,以结尾 1.
有 distance - 1 许多的 0 在每一个 1.
其长度严格小于 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 。我只关心二进制,因为我需要把它用作位操作的工具。实际上, 长度 将非常大, distance ** 2 < length 。假设输入有效。

正如它的名字所暗示的那样,它一遍又一遍地重复着同样的模式。

一个明确的公式:

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

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

用list做类似的事情只需要O(n)。即 ([1]+[0]*(distance-1)) * ((length-2)//distance) + [1]

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

如何在O(n)中得到这样一个整数?

1 回复 | 直到 7 月前

Kelly Bundy 7 月前

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

我的 ones , want , have 和 add 请参考1位的数字。

这个 add = min(have, want - have) 正如我补充的那样,可以“简化” 有 或 have - 1 1比特。它来自这个较早的、稍微不太理想的版本:

def repeatdigit(length:int, distance:int) -> int:
   result = 1
   want = 1 + (length-2) // distance
   have = 1
   while have < want:
      add = min(have, want - have)
      result |= result << (add * distance)
      have += add
   return result