C/C++アルゴリズム

C・C++のビット操作

このレッスンでは、整数の各ビットを立てる、消す、反転する、調べる操作で、複数のオン・オフの状態を保存します。

はじめに

整数の各ビットには、真か偽の値を1つ保存できます。そのため、符号なし整数1つに、フラグ（flag）と呼ばれる独立したオン・オフの設定を複数まとめて入れられます。このビットマスク（bit mask）の手法は、システムプログラミングや組み込み開発でとてもよく使われます。

大切なポイント

空のデータ、要素が1つのデータ、重複を含むデータ、並べ替え済みのデータで試しましょう。
まず正しく動かし、最適化はその後にしましょう。
実際のコードでは、標準ライブラリの既製の関数を優先しましょう。

CとC++のコード例

実行 →

main.c

#include <stdio.h>

int main(void) {
    unsigned flags = 0;
    flags |= 1u << 1;
    flags |= 1u << 3;
    flags ^= 1u << 1;
    printf("flags=%u bit3=%u\n", flags, (flags >> 3) & 1u);
}

実行結果

flags=8 bit3=1

C++

実行 →

main.cpp

#include <bitset>
#include <iostream>

int main() {
    std::bitset<4> flags;
    flags.set(1);
    flags.set(3);
    flags.flip(1);
    std::cout << "flags=" << flags
              << " bit3=" << flags.test(3) << '\n';
}

実行結果

flags=1000 bit3=1

CとC++の比較

式1u << nは、n番目のビットだけが1の数を作ります。演算子|=はビットを立て、^=はビットを反転し、(flags >> 3) & 1uは3番目のビットを調べます。1番目と3番目のビットを立ててから1番目をもう一度反転すると、3番目のビットだけが残るので、flagsは8になります。ビットシフトの結果を予測しやすくするため、符号なし（unsigned）の型を使いましょう。C++のstd::bitsetはset()やflip()のようなわかりやすいメソッドを持ち、結果を2進数で表示できます。

ループ、ポインタ、長さ、一時的なバッファをすべて明示的に書きます。

C++

イテレーターと標準アルゴリズムが、処理とデータの保存方法を切り離します。

発展問題

両方のバージョンを実行し、コードを書き換えて、それぞれの言語がもたらす安全性の違いを観察しましょう。

比較を1回ずつ紙の上でたどってみましょう。
重複した値や、とても大きい値・小さい値で試しましょう。
自分で書いたコードの実行時間を測り、標準ライブラリと比べましょう。

チャレンジで練習する

このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。

すべてのチャレンジ