C/C++アルゴリズム

ビット操作

Bit maskは複数のboolean optionをunsigned integerへまとめます。

ビット操作とは？

Bit maskは複数のboolean optionをunsigned integerへまとめます。

Flagをset、clear、toggle、testします。

重要なポイント

空、1要素、重複、ソート済み入力をテストします。
正しさと最適化を分けます。
実務ではstandard libraryを優先します。

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++の比較

予測可能なshiftにはunsignedを使います。Cはmask、C++ bitsetは名前付き操作とbinary表示を提供します。

loop、pointer、length、bufferを明示します。

C++

iteratorとalgorithmが操作と格納方法を分離します。

練習課題

両方を実行して変更し、言語ごとの保証を確認します。

各比較を手で追跡します。
重複と極値をテストします。
standard libraryとbenchmarkします。