C++で2つの整数の2進加算において最初にキャリーが発生する右端のビット位置を求める

この問題では、2つの正の整数 N と M が与えられます。目的は、N と M を2進数で加算したときに最初に桁上げ（キャリー）が発生するビット位置のうち、最も右側（最下位側）にあるものを求めて出力することです。

問題の例

入力： N = 5、M = 14

出力： 3

説明：

(5)₂ = 0101、(14)₂ = 1110

    0101
+   1110
--------
   10011

加算の過程を追うと、右から3番目のビット位置で初めて桁上げが発生していることが分かります。

解法のアプローチ

ブール代数の基本的な性質から、次のことが導けます。

• 2進数の加算で桁上げが発生するのは、同じ桁の両方のビットが 1 のときだけである。
• したがって、N と M の論理積（AND）を計算すれば、桁上げが発生しうるすべてのビット位置が分かる。
• あとは、その結果の中で最も右側にあるセットビット（1 のビット）の位置を求めれば、それが答えとなる。

具体例で確認してみましょう。

N = 5、M = 14
N & M = 0101 & 1110 = 0100

0100 の最も右側のセットビットは右から 3 番目にあります。したがって答えは 3 です。

最下位のセットビットの求め方

x & -x というビット演算を使うと、x の最下位のセットビットだけを取り出せます。これは2の補数表現の性質を利用した定番テクニックです。さらに log2 を取ることで、そのビットの位置（1始まり）を求められます。

C++での実装

#include <iostream>
#include <math.h>
using namespace std;

// 最下位のセットビットの位置（1始まり）を返す
int rightSetBit(int N) {
    int bitIndex = log2(N & -N) + 1;
    return bitIndex;
}

// 最初にキャリーが発生する右端のビット位置を出力する
void rightCarryBit(int N, int M) {
    int carryIndex = rightSetBit(N & M);
    cout << carryIndex;
}

int main() {
    int N = 5, M = 14;
    cout << N << " と " << M << " の和において最初にキャリーを発生させる右端のビットの位置は ";
    rightCarryBit(N, M);
    return 0;
}

出力

5 と 14 の和において最初にキャリーを発生させる右端のビットの位置は 3

処理の流れと計算量

このコードでは、まず N & M でキャリーが発生しうるビット位置を特定し、続いて N & -N でその中の最下位のセットビットを抽出し、log2 により位置を算出しています。

• 時間計算量： O(1)
• 空間計算量： O(1)

なお、N と M の AND が 0（どこにもキャリーが発生しないケース）では log2(0) が数学的に未定義となるため、実運用ではその場合のチェックを追加しておくと安全です。