C++のビット操作徹底解説！押さえておきたい重要テクニック集

本記事では、まずビットとビット演算子の基本をおさらいした上で、実際の開発や競技プログラミングで役立つ重要なビット操作のテクニックを、具体的なコード例とともにわかりやすく解説します。

ビットとビット演算子の基礎知識

ビット（bit）とは「binary digit（2進数の一桁）」の略称で、コンピュータが理解できるデータの最小単位です。ビットが取りうる値は 0（OFFを表す）と 1（ONを表す） の2通りだけです。

ビット演算子とは、プログラム内でビットレベルに直接働きかける演算子の総称です。これらの演算子を使うことで、データを構成する個々のビットを自在に操作できます。

C/C++には、主に次の6種類のビット演算子が用意されています。

• ビットAND（&）
• ビットOR（|）
• ビットXOR（^）
• 左シフト（<<）
• 右シフト（>>）
• ビットNOT（~）

それでは、ビットを扱う際にぜひ覚えておきたい重要なテクニックを順番に見ていきましょう。

XOR演算子を使って2つの数値を入れ替える

一時変数を使わずに、ビットXOR演算子だけで2つの値を入れ替えることができます。実装例は以下の通りです。

サンプルコード

#include <stdio.h>
int main(){
    int x = 41;
    int y = 90;
    printf("Values before swapping! \n");
    printf("x = %d \t", x);
    printf("y = %d \n", y);
    x = x ^ y;
    y = y ^ x;
    x = x ^ y;
    printf("Values after swapping! \n");
    printf("x = %d \t", x);
    printf("y = %d \n", y);
    return 0;
}

実行結果

Values before swapping!
x = 41 y = 90
Values after swapping!
x = 90 y = 41

最上位ビット（MSB）を効率的に求める方法

任意の整数値について、OR演算子とシフト演算子を組み合わせることで、最上位ビット（MSB: Most Significant Bit）を効率的に求められます。この手法ならO(1)の時間計算量でMSBを取得できるのが大きな魅力です。

なお、プログラムを作成する際は、扱う整数のビット幅をあらかじめ決めておく必要があります。

サンプルコード

32ビット整数のMSBを求めるプログラムです。

#include <stdio.h>
int findMSB(int x){
    x |= x>>1;
    x |= x>>2;
    x |= x>>4;
    x |= x>>8;
    x |= x>>16;
    x = x+1;
    return(x >> 1);
}
int main(){
    int x = 49;
    printf("The number is %d\n", x);
    int msb = findMSB(x);
    printf("MSB of the number is %d\n", msb);
}

実行結果

The number is 49
MSB of the number is 32

1からnまでの全数値のXORを直接計算する

0からnまでのXORの結果を注意深く観察すると、一般パターンを導き出せます。nを4で割った余りに応じて結果が決まるため、ループ処理なしで定数時間（O(1)）で計算可能です。

サンプルコード

#include <stdio.h>
// 1からnまでの全数値のXORを直接求める
int findXORuptoN(int n){
    switch( n%4){
        case 0: return n;
        case 1: return 1;
        break;
        case 2: return n+1;
        break;
        case 3: return 0;
        break;
        default: break;
    }
}
int main(){
    int n = 9870;
    int xorupton = findXORuptoN(n);
    printf("XOR of all number up to %d is %d\n", n, xorupton);
}

実行結果

XOR of all number up to 9870 is 9871

和とXORが等しくなる、n以下の数値の個数を直接求める

ある数nに対して、「各ビットの和」と「XOR」が等しくなるようなn以下の非負整数の個数は、ビットシフト演算子を使えば簡単に求められます。nの2進表現において0になっているビットの数を数え、その個数だけ2の累乗を計算すれば答えが得られます。

サンプルコード

#include <stdio.h>
int countValues(int n){
    int unset=0;
    while (n){
        if ((n & 1) == 0)
            unset++;
        n=n>>1;
    }
    return (1<<unset);
}
int main(){
    int n = 32;
    printf("%d", countValues(n));
}

実行結果

32

整数の先頭・末尾にある0の個数を調べる

ビット操作の応用により、整数の先頭および末尾に連続する0の個数を、GCCの組み込み関数を使って簡単に調べられます。先頭の0は__builtin_clz()、末尾の0は__builtin_ctz()で取得できます。

サンプルコード

#include <stdio.h>
int main(){
    int n = 32;
    printf("The integer value is %d\n", n);
    printf("Number of leading zeros is %d\n", __builtin_clz(n));
    printf("Number of trailing zeros is %d\n", __builtin_ctz(n));
}

実行結果

The integer value is 32
Number of leading zeros is 26
Number of trailing zeros is 5

数が2の累乗かどうかを判定する

ビット演算子を使えば、ある数が2の累乗かどうかも簡単に判定できます。「n & (n-1)」が0になるのは、nが2の累乗の場合だけという性質を利用します。

サンプルコード

#include <stdio.h>
int isPowerof2(int n){
    return n && (!(n&(n-1)));
}
int main(){
    int n = 22;
    if(isPowerof2(n))
        printf("%d is a power of 2", n);
    else
        printf("%d is not a power of 2", n);
}

実行結果

22 is not a power of 2

集合のすべての部分集合のXORを求める

ここでは「要素が2つ以上ある場合、すべての部分集合のXORは必ず0になり、要素が1つの場合はその要素自身の値になる」という性質を利用します。これにより、部分集合を実際に列挙することなく即座に答えを得られます。

サンプルコード

#include <stdio.h>
int findsubsetXOR (int set[], int size){
    if (size == 1){
        return set[size - 1];
    }
    else
        return 0;
}
int main (){
    int set[] = { 45, 12 };
    int size = sizeof (set) / sizeof (set[0]);
    printf ("The XOR of all subsets of set of size %d is %d\n", size,
    findsubsetXOR (set, size));
    int set2[] = { 65 };
    size = sizeof (set2) / sizeof (set2[0]);
    printf ("The XOR of all subsets of set of size %d is %d\n", size,
    findsubsetXOR (set2, size));
}

実行結果

The XOR of all subsets of set of size 2 is 0
The XOR of all subsets of set of size 1 is 65

2進数を整数に変換する

C++ではautoキーワードと2進リテラル（0b接頭辞）を組み合わせることで、2進数を簡単に整数として扱えます。

サンプルコード

#include <stdio.h>
int main (){
    auto integer = 0b0110110;
    printf("The integer conversion of binary number '0110110' is %d", integer);
}

実行結果

The integer conversion of binary number '0110110' is 54

数値の全ビットを反転させる

すべてのビットが1になっている数から対象の数を引くことで、全ビットを反転できます。マスクとなる「全ビット1」の数は、シフトとORの組み合わせで生成できます。

Number = 0110100
The number will all bits set = 1111111
Subtraction -> 1111111 - 0110100 = 1001011 (number with flipped bits)

サンプルコード

#include <stdio.h>
int main (){
    int number = 23;
    int n = number;
    n |= n>>1;
    n |= n>>2;
    n |= n>>4;
    n |= n>>8;
    n |= n>>16;
    printf("The number is %d\n", number);
    printf("Number with reversed bits %d\n", n-number);
}

実行結果

The number is 23
Number with reversed bits 8

ビットが交互パターン（0101…）になっているか確認する

ビットXOR演算を使うと、数値のビットが交互パターン（0と1が交互に並ぶ状態）になっているかどうかを判定できます。n と n>>1 のXORを取った結果のすべてのビットが1になっていれば、元の数は交互パターンであると判断できます。

サンプルコード

#include <stdio.h>
int checkbitpattern(int n){
    int result = n^(n>>1);
    if(((result+1)&result) == 0)
        return 1;
    else
        return 0;
}
int main (){
    int number = 4;
    if(checkbitpattern(number) == 1){
        printf("Bits of %d are in alternate pattern", number);
    }
    else
        printf("Bits of %d are not in alternate pattern", number);
}

実行結果

Bits of 4 are not in alternate pattern

以上のように、ビット演算を活用すると、一見複雑な処理でも少ない計算量で効率的に実装できます。競技プログラミングやパフォーマンスが求められる場面で、ぜひこれらのテクニックを活用してみてください。