RSS
問題① 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
01 との ビット単位排他的論理和演算を行います。
ビット単位排他的論理和は、２つのビットのいずれか一方だけが 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 が立っていないことが分かります。
() の前後の空白の空け方）( の直後、) の直前に空白を入れない）return 0; を削除（Ｃ言語編全体でのコードの統一）
Programming Place Plus のトップページへ
| はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
| X で ポスト／フォロー | LINE で送る | noteで書く |
|
RSS
|
管理者情報 | プライバシーポリシー |