【C++】直前の数値が1の補数と一致するかどうかを判定する方法

整数 n が与えられたとき、n の直前の数（n − 1）がn の1の補数と一致しているかどうかを判定するのが、この問題の目的です。

具体例で問題を理解する

入力: 12
出力: No
解説: (12)10 = (1100)2
      直前の数 11 = (1011)2
      12 の1の補数 = (0011)2

入力: 4
出力: Yes
解説: 4 = (100)2
      直前の数 3 = (011)2
      4 の1の補数 = (011)2

単純なアプローチ

最も素直な方法は、n − 1 を計算し、n の各ビットを反転して得られる1の補数と直接比較することです。しかし、この方法ではビット列を生成・保持する必要があるため、時間とメモリの両面で非効率になります。

効率的な解法：2のべき乗だけが条件を満たす

実は、この条件を満たすのは2のべき乗のみです。
例えば n = 4 = (100)₂ の場合、直前の数 3 = (011)₂ であり、4 の1の補数も (011)₂ となるため両者は一致します。
一般に n = 2^k のとき、n − 1 は下位 k ビットがすべて1になり、n の1の補数（有効ビット幅内で反転した値）もまったく同じ形になるため、必ず等しくなります。

したがって、「n が2のべき乗かどうか」を判定できれば十分です。これはビット演算 (n & (n - 1)) == 0 を使えば定数時間 O(1) で求められます。n と n − 1 のANDを取ると、2のべき乗の場合にのみ結果が0になるという有名なテクニックです。

実装例

#include <iostream>
using namespace std;

bool sameBits(unsigned long int n){
    // n & (n - 1) が 0 なら n は 2 のべき乗
    if ((n & (n - 1)) == 0)
        return true;
    return false;
}

int main(){
    unsigned long int n = 64;
    if(sameBits(n))
        cout<<"Both are the same";
    else
        cout<<"Both aren't the same";
    return 0;
}

実行結果

Both are the same

n = 64 = 2⁶ は2のべき乗であるため、直前の数 63 = (0111111)₂ と 64 の1の補数 (0111111)₂ は一致し、「Both are the same」と出力されます。