C++である数値のセットビットと未セットビットの数が同じかどうかを判定する方法

この記事では、ある整数の2進数表現において、セットビット(1となっているビット)と未セットビット(0となっているビット)の数が同じかどうかを判定する方法を解説します。

例として、数値12を考えてみましょう。12の2進数表現は「1100」です。この中には1が2つ、0が2つ含まれており、セットビットと未セットビットの数が一致しています。

アルゴリズムの考え方

アプローチは非常にシンプルです。以下の手順で判定を行います。

1. 数値の最下位ビットから順に、1ビットずつ値を調べます。
2. 調べたビットが1であればセットビットのカウンター(set_count)を、0であれば未セットビットのカウンター(unset_count)をそれぞれインクリメントします。
3. すべてのビットを確認した後、両方のカウンターが一致していればtrueを、一致していなければfalseを返します。

C++での実装例

#include <iostream>
using namespace std;
bool hasSameSetUnset(int n) {
   int set_count = 0, unset_count = 0;
   while(n){
      if((n & 1) == 1){
         set_count++;
      }else{
         unset_count++;
      }
      n = n >> 1; //右へ1ビットシフト
   }
   if(set_count == unset_count)
   return true;
   return false;
}
int main() {
   int num = 35; //100011
   if(hasSameSetUnset(num)){
      cout << "Has same set, unset bits";
   }else{
      cout << "Not same number of set, unset bits";
   }
}

実行結果

Has same set, unset bits

コードの解説

サンプルコードでは、数値35(2進数で「100011」)をチェックしています。「100011」には1が3つ、0が3つ含まれているため、両者の数が一致していると判定され、「Has same set, unset bits(同じ数のセットビット・未セットビットを持っている)」というメッセージが出力されます。

ビットの判定にはn & 1(AND演算によって最下位ビットだけを取り出す)を使用し、次のビットへ移動する際にはn >> 1(右シフト演算)を使用しています。whileループは数値が0になるまで繰り返されるため、全体の計算量は数値のビット長に比例するO(log n)となり、非常に効率的な処理です。