ビット単位の処理　解答ページ | Programming Place Plus　新C++編

問題１　（確認★） 🔗

次の変数は、どのような値で初期化されますか？

unsigned int value {~0u};

~ は、ビット単位NOT の演算子です（本編解説）。ビット単位NOT は、オペランドのすべてのビットをビット反転します。つまり、ビットが 0 のところは 1 に、1 のところは 0 になります。

~0u は、0u という整数リテラルのすべてのビットをビット反転しようとしています。0u は unsigned int型になるので（本編解説）、仮に 32ビットの大きさだとすると、そのビット構成は 00000000 00000000 00000000 00000000 となります（見やすいように 8ビットずつに区切っています）。これをビット反転するので、その結果は 11111111 11111111 11111111 11111111 です。これはつまり、32ビットで表現できるもっとも大きい整数値のことです。

実際に値を出力してみるとこうなります。

#include <iostream>

int main()
{
    unsigned int value {~0u};

    std::cout << value << "\n";
}

実行結果：

4294967295

問題２　（確認★） 🔗

次のコードはどのような意味を持つでしょう？

auto value = 1u;
value ^= 1;
value ^= 1;

^ は、ビット単位XOR の演算子で、^= はその複合代入演算子です（本編解説）。ビット単位XOR は、２つのビットが同じなら 0、同じでないなら 1 にする演算です。

問題のコードでは、value に 1 が入った状態で、1 とのビット単位XOR を２回繰り返しています。32ビットだとすると、00000000 00000000 00000000 00000001 ^ 00000000 00000000 00000000 00000001 という演算です。ビットが同じところは 0、同じでないところが 1 になるのですから、この演算の結果は、00000000 00000000 00000000 00000000、つまり 0 です。

そのあともう１度、同じ演算を行います。今度は 00000000 00000000 00000000 00000000 ^ 00000000 00000000 00000000 00000001 ですから、その結果は 00000000 00000000 00000000 00000001、つまり 1 です。

このように、1 に対して 1 とのビット単位XOR を行うと 0 になります。また、0 に対して 1 とのビット単位XOR を行うと 1 になります。したがって、繰り返し実行することで、1 と 0 を交互に行き来することになります。この挙動は、ON/OFF を繰り返すスイッチのような動作を実現するために利用できます。

問題３　（基本★★） 🔗

次のコードはどのような演算を行っているか説明してください。

result = (a | b) & ~(a & b);

| はビット単位OR（本編解説）、& はビット単位AND の演算子です（本編解説）。(a | b) はビット単位OR、~(a & b) はビット単位AND をした結果をビット反転していることになります。

ビット単位OR は、２つのビットのいずれかか両方が 1 のときに 1 に、そうでないときに 0 になる演算です。ビット単位AND は、２つのビットの両方ともが 1 のときに 1 に、そうでないときに 0 になる演算です。

a と b がそれぞれ 1ビットしかないとして、すべてのパターンを書きだしてみましょう。

a と b の組み合わせと、それぞれのときの最終的な結果をよく見てみましょう。すると、a と b が同じときに 0 になり、同じでないときに 1 になっていることが分かります。これはちょうど、ビット単位XOR と同じ結果です。つまり、(a | b) & ~(a & b) は、ビット単位XOR を ^ を使わずに表現にしたものということになります。

問題４　（応用★★） 🔗

ある unsigned int型の整数に、1 が立ったビットが何ビットあるか調べる関数を作成してください。

実現する方法はさまざまありますが、このページで学んだ方法を素直に使えば、次のように書けます。

#include <iostream>

// 1が立っているビットを数える
// bits: 調べるビット列
// 戻り値: 1 が立っているビットの個数
int count_one(unsigned int bits)
{
    int count = 0;

    while (bits != 0) {
        if ((bits & 0b1) != 0) {
            ++count;
        }
        bits >>= 1;
    }
    return count;
}

int main()
{
    std::cout << count_one(0b1100'1101'0010'1010) << "\n";
}

実行結果：

8

1 が立っているかどうかは、ビット単位AND を使って判定できるのでした（本編解説）。しかし、これで分かるのは、対象のビットが 1 なのかどうかだけであって、そうしたビットが全部で何個あるのかまでは分かりません。そこで、対象のビット列を 1ビットずつ右シフトしながら、最下位ビットにだけ注目して（0b1 とのビット単位AND を取る）判定していきます。

この方法は素直なやり方ではありますが、効率的ではありません。効率的で美しいアルゴリズムも存在しますが^[3]、すでにある実装を利用するのが簡単ですし、信頼もあります。

たとえば、std::bitset の countメンバ関数を利用できます^{[4] [5]}。

#include <bitset>
#include <iostream>

// 1が立っているビットを数える
// bits: 調べるビット列
// 戻り値: 1 が立っているビットの個数
int count_one(unsigned int bits)
{
    return std::bitset<sizeof(unsigned int)*8>(bits).count();
}

int main()
{
    std::cout << count_one(0b1100'1101'0010'1010) << "\n";
}

実行結果：

8

【C++20】もっとシンプルな std::popcount関数が追加されています^{[6] [7]}。

問題５　（応用★★★） 🔗

コンピュータで扱う色を、光の三原色（赤・緑・青）の強さを数ビットずつ使って表現することがあります（RGB形式）。たとえば、それぞれに 8ビットを使い、赤・緑・青の順に並べる形式では、真っ赤な色を 11111111 00000000 00000000 のように表せます（16進数で 0xff0000）。これは全部で 24ビットですが、あえて上位に 8ビットの未使用領域を加えた 32ビットの整数型（ここでは Color_t型とする）で扱うものとして、以下のような関数を作成してください。

1. 赤・緑・青のそれぞれの強さを指定して、Color_t型の変数の値を変更する関数
2. Color_t型の値を渡すと、赤・緑・青それぞれの強さに分解する関数

たとえば次のように書けます。

#include <cstdint>
#include <iomanip>
#include <iostream>

// カラー型
using Color_t = std::uint32_t;

// Color_t型の値を設定
void set_color(Color_t& color, std::uint8_t red, std::uint8_t green, std::uint8_t blue)
{
    color = (red << 16) | (green << 8) | (blue);
}

// Color_t型から RGB を取り出す
void get_rgb(Color_t color, std::uint8_t& red, std::uint8_t& green, std::uint8_t& blue)
{
    red = (color >> 16) & 0xff;
    green = (color >> 8) & 0xff;
    blue = color & 0xff;
}

// Color_t型の RGB を出力
void print_rgb(std::uint8_t red, std::uint8_t green, std::uint8_t blue)
{
    std::cout << std::setw(2) << std::setfill('0') << std::hex << std::uppercase << static_cast<unsigned int>(red) << " ";
    std::cout << std::setw(2) << std::setfill('0') << std::hex << std::uppercase << static_cast<unsigned int>(green) << " ";
    std::cout << std::setw(2) << std::setfill('0') << std::hex << std::uppercase << static_cast<unsigned int>(blue) << "\n";
}

int main()
{
    Color_t color {0xff0000};
    std::uint8_t red {};
    std::uint8_t green {};
    std::uint8_t blue {};

    get_rgb(color, red, green, blue);
    print_rgb(red, green, blue);
    
    set_color(color, 0x0f, 0xff, 0xf0);
    get_rgb(color, red, green, blue);
    print_rgb(red, green, blue);
}

実行結果：

FF 00 00
0F FF F0

必ず 32ビットだということで、今回は std::uint32_t を使いました（「整数型」のページを参照）。<cstdint> で定義されている整数型を使わない方針なら、unsigned int型など、その処理系に合った 32ビットの整数型を選んでください。同様に、RGB（赤・緑・青）それぞれは 8ビットずつなので、ste::uint8_t で表現しています。

RGB それぞれの値を指定して、Color_t型の値を設定するには、それぞれの 8ビットをうまく結合する必要があります。最上位の 8ビットが未使用領域、次の 8ビットが赤、その次の 8ビットが緑、そして下位の 8ビットが青でした。したがって、赤は 16ビット、緑は 8ビットだけ左シフトして、適切な位置まで導く必要があります。そして、それぞれのビットをビット単位OR で結合すればいいということになります。

Color_t型から RGB を取り出すときは反対で、赤は 16ビット、緑は 8ビットだけ右シフトしないと、8ビットの大きさの値として取り出すことができません。また、右シフトするだけでなく、余分な上位ビットを取り除く必要があります。たとえば、0xff8800 という Color_t型の値から、緑の部分を取り出すなら、その結果は 0x88 になるはずです。8ビット右シフトするだけでは 0xff88 になるので、上位にある ff が邪魔です。これを取り除くために、0xff とのビット単位AND が必要です。