python - 快速将 id 分配给给定的位组合

Question

我的问题背后的背景并不重要，因为我的问题本身相当独立。

我目前正在尝试将数字分配给位序列。这样，如果我向 functionA 询问位序列 42，它会返回相应的位，比如“0110101011...”(不正确，只是一个例子)，如果我给 functionB 序列“0110101011...”，它可以给我数字 42。

目前，我分配每个序列号的方式是通过模式

  bits   val  
| 0    | 0    |
| 1    | 1    |
| 00   | 2    |
| 10   | 3    |
| 01   | 4    |
| 11   | 5    |
| 000  | 6    |
| 100  | 7    |

等等等等第四。目前，我创建的函数就是这样工作的

from itertools import product


def bit_lookup_num(lookup):
  if lookup == '':
    return -1
    
  bits=[]
  current_len=1
  while lookup not in bits:
    bits.extend(["".join(perm[::-1]) for perm in product(["0","1"],repeat=current_len)])
    current_len+=1
  return bits.index(lookup)

def num_lookup_bit(lookup):
  if lookup == -1:
    return ''
    
  bits=[]
  current_len=1
  while len(bits)-1<lookup:
    bits.extend(["".join(perm[::-1]) for perm in product(["0","1"],repeat=current_len)])
    current_len+=1
  return bits[lookup]

其中 num_lookup_bit 用作我之前示例的 functionA，而 bit_lookup_num 用作 functionB。但是，对于大位序列，我的实现变得相当慢，这是由于我使用了 itertools 中的 product() 函数。肯定有比使用 product() 生成所有可能性并检查其在列表中的位置更快的方法来完成此操作，唉，我还没有发现这种解决方法。

我如何通过避免暴力算法来改进这些功能？

Answer 1

你的位序列只是，取 val+2 的二进制表示，砍掉前导的 1，然后反转剩下的:

def bit_sequence(val):
    # [3:] removes the '0b1'
    return bin(val+2)[3:][::-1]
    # return bin(val+2)[:2:-1] would be a bit faster, but a bit harder to understand

def val_for_bit_sequence(bits):
    binary = '1' + bits[::-1]
    return int(binary, 2) - 2