C++で数値に1を加算した際に変化するビット数をカウントする方法

ある整数 num が与えられたとき、その数に 1 を加算した結果、何個のビットが変化するかを求めるのが本記事の課題です。

2進表現とは、数値を 0 と 1 の並びで表したものです。2進変換にはさまざまな方法がありますが、その一つとして、数値を 2 で割った余りを順に調べていく方法があります。余りが 0 以外であればその桁のビットは 1 に、0 であれば 0 に設定されます。

ビットの加算表

0 + 1 = 1
1 + 0 = 1
0 + 0 = 0
1 + 1 = 10（1ビットの繰り上がり）

具体例

入力： num = 10
出力： count is : 1

説明： 10 の2進表現は「1010」です。これに 1 を加えると「1011」になります。変化したのは最下位ビットの1か所だけなので、カウントは 1 となります。

入力： num = 5
出力： count is : 2

説明： 5 の2進表現は「101」です。これに 1 を加えると「110」になります。下位2ビットが変化したため、カウントは 2 となります。

プログラムのアプローチ

• 整数型の数値を入力として受け取ります（例：int num）

• カウントを格納する変数を宣言します（例：int count）

• 別の変数（例：temp）を用意し、「n ^ (n + 1)」というXOR演算の結果を代入します。n と n+1 のXORを取ると、変化したビットの位置だけが 1 になります。

• count 変数に対して __builtin_popcount(temp) を呼び出します。この関数は、与えられた整数の2進表現中で 1 になっているビット（セットビット）の数を計算する GCC コンパイラの組み込み関数です。

• count を返します

• 結果を出力します

なぜXORで求まるのか？

n に 1 を加算すると、最下位から連続する 1 の並びがすべて 0 に反転し、その直上の 0 が 1 に変わります。たとえば「1011（11）」に 1 を足すと「1100（12）」となり、下位2ビットが変化します。n と n+1 のXORを取ると、変化したビット位置だけが 1 となるため、そのセットビットの数を数えれば、変化したビット数がそのまま求まります。

コード例

#include <iostream>
using namespace std;
// 変化したビット数を求める関数
int changedbit(int n){
   int XOR = n ^ (n + 1);
   // XOR値の中のセットビットをカウント
   int count = __builtin_popcount(XOR);
   return count;
}
int main(){
   int n = 10;
   cout <<"count is: " <<changedbit(n);
   return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

count is: 1