ビットとビット演算

ビットとは

コンピューターは内部的にはすべてのデータを数値として扱っています。
100や3.14なども数値ですが、これらも突き詰めれば0と1の二種類だけで表現されています。
(二進数)

C言語で最もサイズの小さいデータ型はchar型の「1バイト」です。
(signed char型もunsigned char型も同じサイズ)
1バイトは256通りの数値を表せます。

コンピューターで扱う最小のデータ単位はバイトではなくビットという単位です。
1ビットは0か1、つまりオフかオンかの2通りの状態を表せます。
つまり二進数です。

2ビットあれば「00」「01」「10」「11」と、4通りの状態を表すことができます。
3ビットならば「000」「001」「010」「011」「100」「101」「110」「111」の8通りです。
1ビット情報が増えるたびに倍のデータ量を表現できます。

言い換えれば、1ビットは2の1乗、2ビットは2の2乗、3ビットは2の3乗…のデータ量です。
1バイトは8ビットのデータ量なので、2の8乗である256通りの状態を表せるわけです。
(たまに1バイトが8ビットでない環境もあります)

ビット演算

ビット演算は、上図のようなビットの並びを意識して行う演算方法です。
ビット演算には論理演算とシフト演算の二種類があります。

論理演算

ビットの論理演算は、二進数の各桁ごとに行う演算です。
論理演算には以下の四種類があります。

「二進数の各桁ごとに演算する」の例を出してみましょう。

以下の例はすべてunsigned char型で考えてください。
1バイト＝8ビットですから、8桁で数値を表現します。

AND演算子

「5」は二進数で「00000101」です。
「12」は二進数で「00001100」です。

AND演算子(論理積)は、二つの数値の各桁同士を比較して、両者が「1」ならばその桁に「1」をセットします。
それ以外の時は「0」をセットします。
つまり、

• 00000101 (5)
• 00001100 (12)
• ↓
• 00000100 (4)

右から3桁目だけが両方とも「1」なので、結果は「00000100」、つまり「4」となります。

これを確かめるコードが以下です。
AND演算子は&記号を使用します。

#include <stdio.h>

//char型のビット並びを表示
void PrintBitC(unsigned char c)
{
    unsigned char bit = 1 << 7;
    while (bit)
    {
        if (c & bit)
            putchar('1');
        else
            putchar('0');
        bit >>= 1;
    }
    putchar('\n');
}

int main()
{
    unsigned char c5 = 5;
    unsigned char c12 = 12;
    unsigned char ret;

    //retには4が代入される
    ret = c5 & c12;

    //00000101
    printf("%3d: ", c5);
    PrintBitC(c5);

    //00001100
    printf("%3d: ", c12);
    PrintBitC(c12);

    //00000100
    printf("%3d: ", ret);
    PrintBitC(ret);

    getchar();
}

関数PrintBitCは、unsigned char型を二進数で表示する関数です。
この関数の具体的な処理は後に説明するシフト演算子を使用しているので、今は横に置いておきます。

 5: 00000101
12: 00001100
 4: 00000100

OR演算子

OR演算子(論理和)は、二つの数値の各桁同士を比較して、どちらか一方が「1」であればその桁に「1」をセットします。
両方が「0」であれば「0」をセットします。

OR演算子には|記号を使用します。
通常の日本語キーボードならば、Shiftを押しながら「\」キーです。

XOR演算子

XOR演算子(排他的論理和)は、二つの数値の各桁同士を比較して、両方が違う値であればその桁に「1」をセットします。
互いに同じ値であれば「0」をセットします。

XOR演算子には^記号を使用します。
通常の日本語キーボードならば、「\」キーの左側です。

~演算子(補数演算子)

~演算子(否定)は、他の三つの演算子とは違い、ひとつの数値だけで演算を行います。
(単項演算子)
ある桁が「0」ならばその桁に「1」をセットします。
「1」ならばその桁に「0」をセットします。
つまり、完全に反転してしまう演算子です。

~演算子には~記号を使用します。
通常の日本語キーボードならば、Shiftを押しながら「^」キーです。

ちなみに、この演算子は補数演算子と呼ばれることが多いようです。
NOT演算子と呼ぶこともありますが、論理否定(!)と混同の可能性があります。
(if文などの条件判定で、条件を反転させるやつです)

論理演算子のサンプル

これらの論理演算のテストコードを以下に示します。
関数PrintBitCは最初のサンプルと同じですが、最後に改行しないように変更しています。

#include <stdio.h>

//char型のビット並びを表示
void PrintBitC(unsigned char c)
{
    unsigned char bit = 1 << 7;
    while (bit)
    {
        if (c & bit)
            putchar('1');
        else
            putchar('0');
        bit >>= 1;
    }
    //putchar('\n');
}

int main()
{
    unsigned char c5 = 5;
    unsigned char c12 = 12;

    unsigned char and, or, xor, not;

    and = c5 & c12;    //4
    or  = c5 | c12;    //13
    xor = c5 ^ c12;    //9
    not = ~c5;         //250

    //00000101
    printf("%3d: ", c5);
    PrintBitC(c5);
    printf("\n");

    //00001110
    printf("%3d: ", c12);
    PrintBitC(c12);
    printf("\n");

    printf("\n");

    //00000100
    printf("%3d: ", and);
    PrintBitC(and);
    printf(" AND(&)\n");

    //00001101
    printf("%3d: ", or);
    PrintBitC(or);
    printf(" OR (|)\n");

    //00001001
    printf("%3d: ", xor);
    PrintBitC(xor);
    printf(" XOR(^)\n");

    //11111010
    printf("%3d: ", not);
    PrintBitC(not);
    printf(" NOT(~)\n");

    getchar();
}

  5: 00000101
 12: 00001100
 
  4: 00000100 AND(&)
 13: 00001101 OR (|)
  9: 00001001 XOR(^)
250: 11111010 NOT(~)

シフト演算

ビットのシフト演算は、二進数の各桁をそのまま左右にずらしてしまう演算方法です。
シフト演算には左シフトと右シフトの二種類があります。

a << b

aを左にb桁シフトする。
空いた桁には0をセットする。

a >> b

aを右にb桁シフトする。

「桁を左右にシフトする」とは、以下の図のようなイメージです。

見た目の通り、桁をごそっと左右に動かすのがシフト演算です。
移動の結果はみ出した桁は無視(削除)されます。

左に1桁シフトすると、値は倍になります。
右に1桁シフトすると、値は半分になります。

これは10進数の時と考え方は同じです。
10進数で「300」を左に1桁移動すると「3000」となり「10倍」になります。
反対に、「300」を右に1桁移動すると「30」となり、「1/10倍」になります。

10進数の場合は「10倍、1/10倍」、2進数の場合は「2倍、1/2倍」ということです。
ただし余りは切り捨てられます。

これを確認するサンプルコードです。

#include <stdio.h>

//char型のビット並びを表示
void PrintBitC(unsigned char c)
{
    unsigned char bit = 1 << 7;
    while (bit)
    {
        if (c & bit)
            putchar('1');
        else
            putchar('0');
        bit >>= 1;
    }
    //putchar('\n');
}

int main()
{
    unsigned char c = 25;
    unsigned char left, right;
    int index = 2;

    left  = c << index; //100
    right = c >> index; //6

    //00011001
    printf("%3d: ", c);
    PrintBitC(c);
    printf("\n");

    printf("\n");

    //01100100
    printf("%3d: ", left);
    PrintBitC(left);
    printf(" (%d << %d)\n", c, index);

    //00000110
    printf("%3d: ", right);
    PrintBitC(right);
    printf(" (%d >> %d)\n", c, index);

    getchar();
}

論理シフトと算術シフト

シフト演算の方法には論理シフトと算術シフトの二通りがあります。

論理シフト

論理シフトは、すべての桁をそのまま移動し、空いた桁を0で埋める方法です。

符号付き整数では最上位ビット(一番左の桁)が0ならば正数、1ならば負数を表しているので、負数を右シフトすると最上位ビットが0から1に変わるため、正負が逆転してしまいます。
左シフトは数学的に正しくシフト可能です。

算術シフト

算術シフトは、右シフトの場合は空いた桁にはシフト前の最上位ビットと同じ値で埋めます。
つまり最上位ビットが1だった場合は1で埋めます。
左シフトの場合は常に0で埋めます。

この方法は負数の場合でも数学的に正しくシフト可能です。
しかし符号なし整数を右シフトした場合は数学的に正しい結果にならないことがあります。
(最上位ビットが1だった場合)

確認コード

論理シフトと算術シフトの確認コードは以下となります。

#include <stdio.h>

//char型のビット並びを表示
void PrintBitC(unsigned char c)
{
    unsigned char bit = (1 << 7);
    while (bit)
    {
        if (c & bit)
            putchar('1');
        else
            putchar('0');
        bit >>= 1;
    }
    //putchar('\n');
}

//signed char型
void printC()
{
    char c = -127;
    char left, right;
    int index = 1;

    left  = c << index; //2
    right = c >> index; //-64

    //10000001
    printf("%4d: ", c);
    PrintBitC(c);
    printf("\n");

    printf("\n");

    //00000010
    printf("%4d: ", left);
    PrintBitC(left);
    printf(" (%d << %d)\n", c, index);

    //11000000
    printf("%4d: ", right);
    PrintBitC(right);
    printf(" (%d >> %d)\n", c, index);
}

//unsigned char型
void printUC()
{
    unsigned char c = 129;
    unsigned char left, right;
    int index = 1;

    left  = c << index; //2
    right = c >> index; //64

    //10000001
    printf("%4d: ", c);
    PrintBitC(c);
    printf("\n");

    printf("\n");

    //00000010
    printf("%4d: ", left);
    PrintBitC(left);
    printf(" (%d << %d)\n", c, index);

    //01000000
    printf("%4d: ", right);
    PrintBitC(right);
    printf(" (%d >> %d)\n", c, index);
}

int main()
{
    printf("char\n\n");
    printC();

    printf("\n\nunsigned char\n\n");
    printUC();

    getchar();
}

char

-127: 10000001

   2: 00000010 (-127 << 1)
 -64: 11000000 (-127 >> 1)


unsigned char

 129: 10000001

   2: 00000010 (129 << 1)
  64: 01000000 (129 >> 1)

C言語の仕様では、どの演算の場合にどちらの方法でシフトされるかは定められていません。
Visual Studio(Visual C++)では、右シフトは「符号なし整数の場合には論理シフト」「符号付き整数の場合には算術シフト」となっているようです。
つまりどちらの場合でも数学的に正しい結果が得られます。
しかし、これは他の環境でも同じとは限らないので注意が必要です。
特に負数のシフト演算は、環境によって実行結果が異なる可能性があるので避けるべきとされています。

なお、シフト演算子の右辺(シフトする桁数の指定)に負数を指定することは未定義動作です。