[Python] bit演算でn番目のbitが立っているか調べる

今回は、bit演算で与えられた整数を2進数にした時、n番目のbitが立っているか調べてみます。

簡略化のため、n番目は0から始まると考えます。

シフト演算

シフト演算とは、2進数の桁をずらす演算です。

左にずらす左シフト <<と、右にずらす右シフト >>があります。

ここでは、左シフトを使います。

左シフトは、指定した分だけ桁を左にずらして、空いたビットを0にする演算です。

1 << 0 : 0 0 0 0 0 1 # 1を0桁左シフト
1 << 1 : 0 0 0 0 1 0 # 1を1桁左シフト
1 << 2 : 0 0 0 1 0 0 # 1を2桁左シフト

n番目のbitが立っているかの判断

ある数のn番目のbitが立っているかどうかは、ある数と、n番目のみが1の数とを、and演算することで分かります。

例えば具体的に、5、二進数で101を考えてみます。

# 2番目はbitが立っている
    b2 b1 b0
5:  1  0  1
    1  0  0  &
    --------
    1  0  0
# 1番目はbitが立っていない
5:  1  0  1
    0  1  0  &
    ---------
    0  0  0 
# 0番目はbitが立っている
5:  1  0  1
    0  0  1  &
    ---------
    0  0  1

n番目のみが1の数とand演算すると、立っていない場合は必ず「0」が、立っている場合はそれ以外の数字が返ってきます。

Python は、if構文で、「0」は False、それ以外の整数は True と判定されるので、これをそのまま条件分岐に使えば、目的の判定ができます。

n番目のみが1となる数の生成

n番目のみが1となる2進数は、1をn桁左シフトすることで生成できます。

# 2番目はbitが立っている
         b2 b1 b0
5:        1  0  1
1 << 2    1  0  0  &
          --------
          1  0  0
# 1番目はbitが立っていない
5:        1  0  1
1 << 1    0  1  0  &
          ---------
          0  0  0 
# 0番目はbitが立っている
5:        1  0  1
1 << 0    0  0  1  &
          ---------
          0  0  1

関数にまとめる

ここまでを関数にまとめます。

>>> def is_nth_bit_set(num: int, n: int):
...     if num & (1 << n):
...         return True
...     return False
...
>>> is_nth_bit_set(5, 0)
True
>>> is_nth_bit_set(5, 1)
False
>>> is_nth_bit_set(5, 2)
True
>>> is_nth_bit_set(5, 3)
False
>>>

想定通りの結果を得ることができました。

以下に続きます。