C++で整数の1の補数(nビット)を求める方法

1の補数とは

本記事では、整数の「1の補数」を求める方法について解説します。C++には補数演算子(~)が用意されており、これを使えば非常に高速に補数を計算できます。ただし、この演算子は32ビット(4バイト)全体に対して補数を求めてしまうため、ここでは「与えられた数値のビット数分だけの補数」を取得する方法を考えます。

例として、22という数値を取り上げます。22の2進表現は「10110」であり、その1の補数は「01001」、つまり10進数の9になります。では、この値はどのようにして求めればよいのでしょうか。

求め方の手順

まず、対象の数値のビット数を求めます。この値をcとします(22の場合、c = 5)。次に、5桁すべてが1の数「11111」を作成します。これは、1を左へc回シフトした後、1を減算することで実現できます。1を左に5回シフトすると「100000」になり、そこから1を引けば「11111」が得られます。最後に、この「11111」と元の数値「10110」のXOR(排他的論理和)を計算することで、目的の1の補数が求まります。

サンプルコード

#include <iostream>
#include <cmath>
using namespace std;
int findComplement(int n) {
    int bit_count = floor(log2(n))+1;
    int ones = ((1 << bit_count) - 1);
    return ones ^ n;
}
int main() {
    int number = 22;
    cout << "One's Complement of " << number << " is: " << findComplement(number);
}

出力結果

One's Complement of 22 is: 9