パフォーマンスと汎用性の視点から選ぶ！C++20で2の累乗判定のベストプラクティス

2024-07-27

C++20で正の整数が2の累乗かどうかを効率的に判定する方法

C++20において、正の整数が2の累乗であるかどうかを効率的に判定する方法はいくつかあります。ここでは、パフォーマンスと汎用性の観点から、最も優れた2つの方法をご紹介します。

方法1: ビットマスクを使用した判定

最も基本的な方法は、ビットマスクを使用して判定する方法です。以下のコード例をご覧ください。

#include <iostream>

bool isPowerOfTwo(unsigned int x) {
  return (x && (x & (x - 1)) == 0);
}

int main() {
  unsigned int x;
  std::cin >> x;

  if (isPowerOfTwo(x)) {
    std::cout << x << "は2の累乗です" << std::endl;
  } else {
    std::cout << x << "は2の累乗ではありません" << std::endl;
  }

  return 0;
}

このコードは以下の通り動作します。

x と x - 1 のビットごとのAND演算を行います。2の累乗の場合、x - 1 は常に1つ前の2の累乗になります。よって、AND演算の結果は常に0になります。
x が0でないこと (x && True) と、1. で得られた結果が0であること ((x & (x - 1)) == 0) の論理積を返します。

この方法は非常に高速で、多くの場合で十分なパフォーマンスを発揮します。

より高速な方法として、論理ビットシフトを使用した判定があります。以下のコード例をご覧ください。

#include <iostream>

bool isPowerOfTwo(unsigned int x) {
  return (x != 0) && ((x & (x - 1)) == 0);
}

int main() {
  unsigned int x;
  std::cin >> x;

  if (isPowerOfTwo(x)) {
    std::cout << x << "は2の累乗です" << std::endl;
  } else {
    std::cout << x << "は2の累乗ではありません" << std::endl;
  }

  return 0;
}

このコードは方法1とほぼ同じですが、1つだけ違いがあります。

x != 0 という条件を追加しています。これは、x が0の場合、x - 1 の計算が誤った結果になる可能性があるためです。

この方法は方法1よりもわずかに高速ですが、ほとんどの場合、その差はごくわずかです。

どちらの方法を選択すべきか

一般的に、方法1 が推奨されます。これは、方法2 よりもコードが簡潔で分かりやすく、多くの場合で十分なパフォーマンスを発揮するためです。

方法2 を選択する場合は、方法1 で説明した注意点に留意する必要があります。

上記以外にも、2の累乗かどうかを判定する方法があります。例えば、以下のような方法があります。

標準ライブラリを使用する: C++20には、std::bitset クラスなどの標準ライブラリ機能が用意されており、これらを活用して2の累乗かどうかを判定することができます。
分岐予測を改善する: コンパイラによっては、分岐予測を改善することで、判定処理を高速化することができます。

#include <iostream>

bool isPowerOfTwo(unsigned int x) {
  return (x && (x & (x - 1)) == 0);
}

int main() {
  unsigned int x;
  std::cin >> x;

  if (isPowerOfTwo(x)) {
    std::cout << x << "は2の累乗です" << std::endl;
  } else {
    std::cout << x << "は2の累乗ではありません" << std::endl;
  }

  return 0;
}

#include <iostream>

bool isPowerOfTwo(unsigned int x) {
  return (x != 0) && ((x & (x - 1)) == 0);
}

int main() {
  unsigned int x;
  std::cin >> x;

  if (isPowerOfTwo(x)) {
    std::cout << x << "は2の累乗です" << std::endl;
  } else {
    std::cout << x << "は2の累乗ではありません" << std::endl;
  }

  return 0;
}

説明

上記の説明では、各方法の動作を詳細に説明しました。

実際のプログラムで使用する場合には、必要に応じてエラー処理などを追加する必要があります。

C++20には、std::log2() 関数が用意されています。この関数は、引数として与えられた数の2のべき乗を返します。よって、以下のコードのように std::log2() 関数を使用して、2の累乗かどうかを判定することができます。

#include <iostream>
#include <cmath>

bool isPowerOfTwo(unsigned int x) {
  return std::fmod(std::log2(x), 1) == 0;
}

int main() {
  unsigned int x;
  std::cin >> x;

  if (isPowerOfTwo(x)) {
    std::cout << x << "は2の累乗です" << std::endl;
  } else {
    std::cout << x << "は2の累乗ではありません" << std::endl;
  }

  return 0;
}

この方法は、標準ライブラリを使用しているので簡潔ですが、方法1 や 方法2 よりも計算量が多くなります。

方法4: ブール型反復を使用する

以下のコードは、ブール型反復を使用して2の累乗かどうかを判定する方法です。

bool isPowerOfTwo(unsigned int x) {
  if (x < 1) {
    return false;
  }

  while ((x & (x - 1)) == 0) {
    x >>= 1;
  }

  return x == 1;
}

この方法は、再帰を使用せずに2の累乗かどうかを判定することができます。

方法5: 組み込み関数をを使用する

一部のプラットフォームでは、2の累乗かどうかを判定する組み込み関数が用意されています。例えば、x86 アーキテクチャの場合には、_isqrt() 関数を使用して2の累乗かどうかを判定することができます。

#include <iostream>
#include <cstdlib>

bool isPowerOfTwo(unsigned int x) {
  return _isqrt(x) * _isqrt(x) == x;
}

int main() {
  unsigned int x;
  std::cin >> x;

  if (isPowerOfTwo(x)) {
    std::cout << x << "は2の累乗です" << std::endl;
  } else {
    std::cout << x << "は2の累乗ではありません" << std::endl;
  }

  return 0;
}