Bit Manipulation

常见操作

x.bit_count()：返回x的二进制表示中，有几个1。也可以理解为，x最少需要用几个2的幂次之和来表示。

脑筋急转弯

2749. 得到整数零需要执行的最少操作数

设x = num1 - k * num2，则问题转化为：能否用k个2的幂次（允许重复）表示x？

找x的上下界，并且枚举。可对x = num1 - k * num2画图，k为横轴，x为纵轴。则答案为这条直线在第一象限上的某些点，通过分析x=2^(i1)+…2^(ik)这个等式，找到可能的x值。
由于2的幂次最小是1，所以x>=k
那么x最大为多少？x最大时，k最小，即k=x.bit_count()

把k从小到大枚举，第一个满足等式的，即为答案

3495. 使数组元素都变为零的最少操作次数

对一个数字除以 4 并向下取整：二进制右移两位 对于一个数字，如果它的二进制表示有n位，那么它需要(n+1)//2次操作可以变成0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def get(x):
    #计算从1到x。所有数的二进制的(位数+1)//2之和
    #比如从16到31，1000到1111，都是四位数
    #1=1, 2=10, 3=11, 4=100,5=101,6=110,7=111,8=1110
    base=1
    cnt=0
    i=1 #表示从1位数的二进制开始遍历
    while base<=x:
        end=min(x, 2*base-1)
        cnt+=(i+1)//2*(end-base+1)#位数*有几个数是i位的二进制数
        base*=2
        i+=1