Convert a Number to a Number

# 問題

整数$A$を整数$B$に変換するのに必要なビット反転の回数を計算せよ．

# 答え

1
2
3
4
5
6
7
def count(a, b):
    ret = 0
    c = a ^ b # 異なる桁だけ1が立つ
    while c != 0:
        ret += 1 if c & 1 else 0
        c = c >> 1
    return ret

こうも書ける．

1
2
3
4
5
6
7
def count(a, b):
    ret = 0
    c = a ^ b
    while c != 0:
        ret += 1
        c = c & (c - 1) # 右端の1が0になる
    return ret