Python
 Computer >> コンピューター >  >> プログラミング >> Python

Pythonで数値のK番目のビットがセットされているかどうかを判定する方法

数値 n と別の値 k が与えられたとき、n の k 番目のビットが 1(セットされている状態)かどうかを判定します。ここで、k は右側(最下位ビット側)から数えた位置とします。

たとえば、入力が n = 23、k = 3 の場合、出力は True になります。これは、23 を2進数で表すと「10111」となり、右から3番目のビットが 1 であるためです。

解決のアプローチ

この問題は、ビット演算を使うことで効率的に解けます。手順は以下の通りです。

  • n を右に (k − 1) ビットシフトした値を temp とする
  • temp と 1 のAND演算結果が 1 であれば True を返す
  • それ以外の場合は False を返す

この方法では、目的のビットを最下位ビットまで移動させてから、1とのAND演算によってそのビットが立っているかどうかを直接確認できます。

サンプルコード

def solve(n,k):
    temp = n >> (k - 1)
    if temp & 1:
        return True
    return False

n = 23
k = 3
print(solve(n, k))

入力

23, 3

出力

True

コードの解説

n >> (k - 1) により、確認したいビットが最下位ビットの位置に移動します。その後、temp & 1 で最下位ビットだけを取り出し、結果が 1 なら該当ビットがセットされていることになります。この手法の計算量は O(1) であり、非常に高速に動作します。

  1. Pythonで数値が二面素数（Dihedral Prime）かどうかを判定する方法

    ある整数nが与えられたとき、それが「二面素数（dihedral prime）」であるかどうかを判定する方法を解説します。二面素数とは、その数自体が素数であり、さらに7セグメントディスプレイに表示した際に、表示の向き（通常の向きでも上下逆さまでも）に関わらず、同じ数または別の素数として読み取れる数のことです。例えば、入力がn = 1181の場合、出力はTrueになります。下の数字は上の数字を上下逆さま（180度回転）にして表示したものであり、どちらも素数となっています。アルゴリズムの手順この問題を解くために、以下の手順で進めます。up_side_down() 関数を定義します。引数としてnを受け

  2. Pythonで与えられたグラフが2部グラフかどうかを判定するプログラム

    2部グラフとは無向グラフが与えられたとき、そのグラフが2部グラフ(バイパータイトグラフ)であるかどうかを判定する方法を解説します。2部グラフとは、グラフのすべての頂点を2つの集合 A と B に分割でき、グラフ内のすべての辺 {u, v} が必ず一方の端点 u が集合 A、もう一方の端点 v が集合 B に属するようなグラフのことです。つまり、同じ集合内の頂点同士を結ぶ辺(A-A や B-B)が一切存在しないグラフです。例として、次のようなグラフを考えてみましょう。この場合、頂点 [0, 4] を集合 A に、[1, 2, 3] を集合 B に分類できます。すべての辺は A から B、または