ビット演算　解答ページ | Programming Place Plus　Ｃ言語編　第４９章

トップページ – Ｃ言語編 – 第４９章

問題①

問題①　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 との 排他的論理和演算を行います。
排他的論理和は、２つのビットのいずれか一方だけが 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 ) );
}


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

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　新規作成。


第４９章のメインページへ

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

Programming Place Plus のトップページへ

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