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

Pythonで数値が2の累乗かどうかを判定する方法

はじめに

ある数値 n が与えられたとき、その数値が2の累乗であるかどうかを判定する問題について解説します。

例えば、入力が n = 2048 の場合、2048は 211 に等しいため、出力は True となります。

解法のアプローチ

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

  • n が 0 と等しい場合は False を返します。

  • (n AND (n - 1)) の計算結果が 0 と等しい場合は True を、そうでない場合は False を返します。

この手法が機能する理由は、2の累乗を二進数で表すと「1000…0」のように最上位ビットのみが1になるという性質にあります。そこから1を引くと「0111…1」となり、元の数値とのAND演算の結果は必ず0になります。一方、2の累乗でない数値では複数のビットが立っているため、AND演算の結果は0になりません。

実装例

以下にPythonでの実装例を示します。

def solve(n):
   if n == 0:
      return False
   return (n & (n - 1)) == 0

n = 2048
print(solve(n))

入力

2048

出力

True

まとめ

ビット演算 n & (n - 1) を利用することで、数値が2の累乗であるかどうかをO(1)の時間計算量で判定できます。ループ処理や対数計算を使わずに済むため、非常にシンプルかつ効率的な手法です。競技プログラミングや実務のコーディング面接でも頻出のテクニックなので、ぜひ覚えておきましょう。

  1. Pythonで素数を判定するプログラムの書き方を徹底解説

    はじめに この記事では、「与えられた数値が素数かどうかを判定する」という問題に対する解決策を、Pythonのコード例とともにわかりやすく解説します。 問題の概要 問題設定：ある数値が与えられたとき、その数が素数であるかどうかを判定するプログラムを作成します。 まず「素数」の定義をおさらいしましょう。1より大きい正の整数のうち、1とその数自身以外に約数を持たない数を素数（そすう）と呼びます。たとえば、2、3、5、7などはそれ以外の約数を持たないため、素数です。 プログラムの考え方 今回作成するプログラムでは、入力された数値が素数かどうかを以下の手順で判定します。 1以下の数値は素数ではない

  2. Pythonでアームストロング数を判定するプログラムの書き方

    この記事では、与えられた整数が「アームストロング数（Armstrong number）」であるかどうかを判定するための考え方と、Pythonによる具体的な実装方法を解説します。 問題の定義 整数 n が与えられたとき、その整数がアームストロング数であるかどうかを判定することを目標とします。 アームストロング数とは？ n 桁の正の整数 abcd… が次の条件を満たすとき、この数は「n 次（オーダー n）のアームストロング数」と呼ばれます。 abcd... = a^n + b^n + c^n + d^n + … つまり、各桁の数字を「桁数乗」した値の総和が、元の数と一致するかを確認す