[TOC]
Gosper’s Hack
Gosper‘s Hack用来逐一生成二进制枚举中n位含有k位1的二进制数。
def GospersHack(k:int,n:int)->None:
cur = (1<<k)-1
limit = (1<<n)
while cur<limit:
lb = cur&-cur
higher_bit = lb+cur
cur = higher_bit | (((higher_bit^cur)>>2)//lb)
Gosper’s Hack原理解析
时间复杂度
\[O(C_n^k)\]
即子集个数
Reference
