ビット演算 解答ページ | Programming Place Plus C言語編 第49章

トップページC言語編第49章

問題①

問題① unsigned int型の変数num に 0 が格納されていたら 1 に、1 が格納されていたら 0 に変換する処理を、ビット演算を使って書いてください。


この問題のような用途には、ビット単位排他的論理和が利用できます。

#include <stdio.h>

int main(void)
{
    unsigned int num;

    num = 0;
    printf("%u\n", num ^ 1);

    num = 1;
    printf("%u\n", num ^ 1);
}

実行結果

1
0

1 との ビット単位排他的論理和演算を行います。

ビット単位排他的論理和は、2つのビットのいずれか一方だけが 1 のときに、結果も 1 になりますから、元の数が 0 ならば、「0 ^ 1」なので 1 に、元の数が 1 ならば、「1 ^ 1」なので 0 になります。

ちなみに、0 とのビット単位排他的論理和演算をすると、結果は元の数のまま変わりません。

問題②

問題② ある正の整数に、1 が立っているビットがいくつあるかを調べるプログラムを作成してください。


あるビットが 1 かどうかは、ビット積で調べられます。しかし、何個あるかを数えるには、1ビットずつ順番に調べていく必要があります。

1ビットずつ調べるためには、シフト演算を利用します。

#include <stdio.h>

int main(void)
{
    unsigned int num = 1234;
    int count = 0;

    while (num > 0) {
        if (num & 1) {  // 最下位ビットが 1 かどうか
            ++count;
        }
        num >>= 1;  // 次のビットを調べるため、1ビットずらす
    }

    printf("%d\n", count);
}

実行結果

5

これがビット演算を普通に使った正攻法ですが、徹底的に最適化されたアルゴリズムもあります。

#include <stdio.h>

int main(void)
{
    unsigned int num = 1234;

    num = (num & 0x55555555) + (num >>  1 & 0x55555555);
    num = (num & 0x33333333) + (num >>  2 & 0x33333333);
    num = (num & 0x0f0f0f0f) + (num >>  4 & 0x0f0f0f0f);
    num = (num & 0x00ff00ff) + (num >>  8 & 0x00ff00ff);
    num = (num & 0x0000ffff) + (num >> 16 & 0x0000ffff);

    printf("%u\n", num);
}

実行結果

5

ここまで来ると、何をしているのかよく分かりませんが、美しいコードですね。

問題③

問題③ 次の関数は何をしているでしょうか。

int func(unsigned int a, unsigned int b)
{
    return ((a | b ) & ~(a & b));
}


これは、ビット単位排他的論理和演算を、他のビット演算の組み合わせで表現したものです。つまり、以下の2つは同じ結果になります。

ans = a ^ b;
ans = func(a, b);

これは表を書いてみて確認すると良いでしょう。

a b a | b ~(a & b) (a | b) & ~(a & b)
0 0 0 1 0
0 1 1 1 1
1 0 1 1 1
1 1 1 0 0

ビット単位排他的論理和演算は、一方だけが 1 のときに 1 になる演算ですから、それを実現できる組み合わせを探すと、確かに、「a | b」と「~(a & b)」を、ビット積演算で合成すればいいことが分かります。

問題④

問題④ 標準入力から受け取った 10進数の正の整数を、2進法で標準出力へ出力するプログラムを作成してください。


ビット積演算を使って、各ビットが 1 か 0 かを調べていきます。この結果を書き並べれば、それが 2進法による表記になっています。

#include <stdio.h>

int main(void)
{
    puts("正の整数を入力してください。");
    char buf[40];
    unsigned int num;
    fgets(buf, sizeof(buf), stdin);
    sscanf(buf, "%u", &num);


    for (unsigned int mask = 0x8000; mask != 0; mask >>= 1) {
        printf("%d", (num & mask ) ? (1) : (0));
    }
    printf("\n");
}

実行結果

正の整数を入力してください。
1000
0000001111101000

マスクを取るために使うビット列 0x8000 を用意し、これを 1ビットずつずらしながら AND演算を行っています。そのビット積演算の結果が 0 になるならば、演算の対象にしているビットには 1 が立っていないことが分かります。


参考リンク


更新履歴

’2018/3/24 全面的に文章を見直し、修正を行った。

’2011/2/6 新規作成。



第49章のメインページへ

C言語編のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポストフォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る