カテゴリー別アーカイブ: C言語

if文(条件分岐)を使わず、max(a, b) を計算

通常、int max(int a, int b) は以下のように実装される(非テンプレートの場合)。

int max(int a, int b)
{
    return a > b ? a : b;
}
int max(int a, int b)
{
    if( a > b )
        return a;
    else
        return b;
}

これを if文, ?: を使わずに書くにはどうしたらいいだろうか?

実はビット演算を使うとそれが出来てしまうのだ。

答えは以下のとおり(int は 32bit 符号付き整数と仮定)。

int max(int a, int b)
{
    int t = (a - b) >> 31;  // a>=b ならば0, a<b ならば 0xffffffff
    return (a & ~t) | (b & t);
}

符号付き整数を右シフトすると、最上位の符号ビットが維持されたままになる性質を利用している。
ご理解いただけたであろうか?

if文を使わずこんなことをしていったい何の意味があるのかと懐疑的な読者もいることだろう。
実は最近のCPUはパイプライン+分岐予測を行っているので、条件分岐があり、分岐予測に失敗すると、パイプラインをクリアする必要があり、処理が遅くなることがあるのだ。
条件分岐を使わず論理演算だけで済ますと、そういうことがなく処理が高速になることがある。

また、ある種の並列マシンでは、データは並列CPUでアクセスできるのだが、プログラムカウンタが共通、という仕様のものがあるのだそうだ。そういうマシンでは各データごとで異なる条件分岐を行うことができないので、このようなテクニックを使わざるをえないのだそうじゃ。

追記(2014/12/03):

別解も書きましたよ

ニコ生でM氏に、オーバーフローする場合があるというご指摘をいただいだ。
たしかに、a, b の差が0x7fffffff を越えていると、結果が正しくならないようだ。

 

 

ビット演算>ビット順序反転 xor 版

前稿では、ループを and or を用いてビット順序を反転するコードを示した。
本稿では、xor を用いたビット交換を繰り返し行うことでビット順序を反転するコードを紹介する。

まずは2ビットの場合を考えよう。
この場合は、ビット交換テクニックにより交換すればよい。

int x = 2ビットの値;
int t = ((x >> 1) ^ x) & 1;
t |= t << 1;
x ^= t;

これは以前説明した通りだ。
では、次に4ビットの場合はどうするか?

実は上位2ビットと下位2ビットを交換し、ついで隣り合う1ビット同士を交換すると、ビット順序が反転するのだ。

と言われても、はあ?と思う方がほとんどだと思うので、例を示そう。
各ビットの値を a, b, c, d とすると、初期状態は abcd だ。
上位2ビット(ab)と下位2ビット(cd)を交換すると cdab となる。
ついで、隣り合う1ビット同時を交換すると、dcba となる。

どうだい、ちゃんとビット順序が反転しただろ。

これをコードで書くと以下のようになる。

int x = 4ビットの値;
// 上位2ビットと下位2ビットの交換
int t = ((x >> 2) ^ x) & 3;
t |= t << 2; x ^= t; // 隣り合う1ビットの交換 t = ((x >> 1) ^ x) & 1;
t |= t << 1;
x ^= t;

同様にして、32ビットの順序を反転したい場合は、まず上位16ビットと下位16ビットを交換し、ついで8ビットごとに交換、4ビットごとに交換、2ビットごとに交換、1ビットごとに交換、とすればよいのだ。
1回の交換では論理演算を6回行うので、合計30回の論理演算しか行わない。
ループの場合は平均して80回の倫理演算だった。単純に言えば2倍以上高速ということだ。

int x = 32ビットの値;
// 上位16ビットと下位16ビットの交換
int t = ((x >> 16) ^ x) & 0xffff;
t |= t << 16; x ^= t; // 8ビットごとの交換 t = ((x >> 8) ^ x) & 0x00ff00ff;
t |= t << 8; x ^= t; // 4ビットごとの交換 t = ((x >> 4) ^ x) & 0x0f0f0f0f;
t |= t << 4; x ^= t; // 2ビットごとの交換 int t = ((x >> 2) ^ x) & 0x33333333;
t |= t << 2; x ^= t; // 隣り合う1ビットの交換 t = ((x >> 1) ^ x) & 0x55555555;
t |= t << 1;
x ^= t;

演習問題:

  1. 上記コードをビルドし、ビット順序が正しく反転されることを確認しなさい。
  2. 本稿のテクニックを使って、64ビット整数のビット順序を反転するコードを書きなさい。
  3. 上記コードがループでビット順序反転を行う場合に比べてどの程度高速かを計測しなさい。

ビット演算>ビット順序反転

int x; に何らかの値が入っているとき、最上位ビットから最下位ビットまでの順序を反転(0x01234567 → 0xe6a2c480)するにはどう書いたらいいだろうか?

ループと論理積を使えば、以下のように書くことができる。

int x = 何らかの値;
int t = 0;
for(unsigned int mask = 0x80000000; mask != 0; mask>>=1) {
    t <<= 1;    //  結果を1ビット左シフト
    if( (x & mask) != 0 )   //  x の当該ビットが立っていれば
        t |= 1;    //  結果のビットを立てる
}
x = t;    //  結果を x に格納

ループは int のビット数分なので、32回。1回のループでは論理演算が2回または3回だ。
平均2.5回だとすると、合計80回の論理演算ということになる。

このコードで何も問題なさそうだが、実は前稿で紹介したビット交換テクニックを使うと演算回数を大幅に減らせるのだ。
実際にどうやるかは次稿で。

ビット演算>xor(排他的論理和)を用いたビットの交換(2)

前稿 では、異なる変数の同じ位置のビットを交換したが、ひとつの変数内のビットを交換することも出来るぞ。
下記は、変数 x の下位4ビット(bit0~bit3)とその上4ビット(bit4~bit7)を交換するコードだ。

x = 何らかの値;
int t = (x ^ (x >> 4)) & 0xf;    //  x の下位4ビットとその上4ビットの xor を計算
t |= t << 4;    //  xor 値を bit4~bit7 にもコピー
x ^= t;    // xor を取ることでビットを交換

論理演算の回数はわずか6回だ。
どうだい、こんな簡潔なコードでビットの交換ができるなんて感激しないか?

 演習問題:

  1. 上記コードをビルド・デバッガで実行し、ビットが交換されていることを確認しなさい。
  2. 論理積と論理和を使って上記と同じコードを書いてみなさい。
  3. 変数x の bit4~bit7 と bit12~bit15 を交換(x = 0x1234; ならば x = 0x3214 となる)するコードを書きなさい。

ビット演算>xor(排他的論理和)を用いたビットの交換

前稿 で、and, or を用いたビット交換方法を示したが、xor を用いると、より簡潔に書けるぞ。

int x = 何らかの値;
int y = 何らかの値;
const int t = (x ^ y) & 0xf;   //  x と y の下位8ビットの xor
x ^= t;    //  下位8ビットが x^(x^y) = y になる
y ^= t;    //  下位8ビットが y^(x^y) = x になる

どうだろう?ご理解いただけるであろうか?
前稿の方法と比べて、非常に簡潔になったでしょ。

交換したい部分の xor(排他的論理和)をとり、それを元の変数に xor することで、ビットを交換できるということだ。

筆者がはじめてこのテクニックを見たときはかなりびっくりした。言われてみればあたりまえなのだが、ビットを交換するときに方法が思いつかず、前稿の方法を使っていたからだ。

演習問題:

  1. 上記コードをビルド・デバッガで実行し、正しく交換されることを確認しなさい。

ビット演算>and(論理積), or(論理和)を用いたビットの交換

int x, int y に何らかの値が入っている時、下位8ビットの値を交換するコードは以下のように記述することが出来る。

int x = 何らかの値;
int y = 何らかの値;
const int mask = 0xf;    // 交換する部分のマスク
int tx = x & mask;    // x の下位8ビットを取り出す → tx に保存
int ty = y & mask;    // y の下位8ビットを取り出す → ty に保存
x &= ~mask;    // x の下位8ビットを0に
x |= ty;    // x の下位8ビットを y の下位8ビットの値にする
y &= ~mask;    // y の下位8ビットを0に
y |= tx;    // y の下位8ビットを x の下位8ビットの値にする

これまでに説明した、論理積・論理和のテクニックを使用している。ご理解いただけるであろうか?
よくわからない人はこれまでの解説を是非読み返して欲しい。

演習問題:

  1. 上記コードをビルドし、デバッガで動きを確認しなさい。

ビット演算>xor(排他的論理和)を使った値の交換

ここまでは基礎編だったが、ここからは中級編だ。少し難しくなるかもしれない。
が、マスターすれば便利な機能なので、ぜひマスターしてワンランク上のビット演算氏になってもらいたい。

排他的論理和 のところで一応説明したのだが、もう一度書いておくと、排他的論理和には以下の様な性質がある。

  • x ^ 0 = 0 ^ x = x   // 0 との排他的論理和は値を変えない
  • x ^ x = 0    // 同じものを xor すると結果は 0
  • (x ^ y) ^ z = x ^ (y ^ z)   // 結合法則
  • x ^ y = y ^ x    // 交換法則

なので、 (x ^ y) ^ x = (y ^ x) ^ x = y ^ (x ^ x) = y ^ 0 = y となる。

この性質を使うと、下記のコードで2つの変数を入れ替えることが出来る。

int x = 何らかの値;
int y = 何らかの値;
x ^= y;
y ^= x;
x ^= y;

狐に摘まれた方も少なくないと思うが、上記のコードで x, y に入っている値はしっかり入れ替わる。

x,y の初期値を x0, y0 として説明する。
最初に x ^= y; を実行すると、x には x0 ^ y0 が入る。
次に y ^= x; を実行すると、y0 ^ (x0 ^ y0) = x0 なので、y には x の初期値 x0 が入る。
次に x ^= y; を実行すると、x には (x0 ^ y0)、y には x0 が入っているので、(x0 ^ y0) ^ x0 = y0 となり、x には無事 y0 が入り、x と y の値が交換されることになる。

ご理解いただけたであろうか?

演習問題:

  1. 変数の値を入れ替えるコードをビルド・デバッガで実行し、本当に中身が入れ替わることを確認しなさい。

ビット演算>右シフト

右シフトとは、下図のように、各ビットをひとつ右にずらし、最上位ビットに0を入れることだ。最下位ビットの値は捨てられる。
ただし、シフトされる対象が符号付きの場合、最上位ビットの値はそのまま残る。

temp

1ビット 左シフトとが2倍することだったことの裏返しで、1ビット右シフトは2で割る(余りは切り捨て)ことと同等だ。符号付き整数を右シフトした場合、最上位ビットがそのまま残るのは、マイナスの数値の符号を維持するためだ。

C/C++ では 二項演算子 >> が右ビットシフトを表す。
シフトするビット数は1だけとは限らず、「x >> 2」 の様にシフトするビット数を付加して記述することが出来る。

int x = 0xff00 >> 4;  // 0xff00 を4ビットシフトした値を x に代入
x >>= 2;  //  x を 2ビット左シフトし、それを x に代入

上記は C/C++ での右シフトの使用例だ。

前稿 で、左シフトを使って、全ビットを検査するコードを示したが、左シフトでは最下位ビットから最上位ビットに向かって、順に処理を行うことになる。場合によっては、最上位ビットから下位ビットに向かって、処理を行いたい場合がある。その場合は、右シフトを用いる。

int x = 何らかの値;
for(unsigned int mask = 0x80000000; mask != 0; mask>>=1) {
  if( (x & mask) != 0 ) {  // x の mask ビットが立っていたら
    何らかの処理;
  }
}

注意すべきは、mask は符号付きではなく、符号なし(unsigned)を用いないといけないという点だ。符号付だと、最上位ビットが残ってしまい、うまくループしてくれない。

演習問題:

  1. int x = 100; を宣言し、x を1ビット右シフトした値を表示し、値が半分になっていることを確認しなさい
  2. int x = -100; を宣言し、x を1ビット右シフトした値を表示し、値が半分になっていることを確認しなさい
  3. int x; に何らかの値が入っているとき、中身のビットを逆順にするコードを書きなさい。例:0xff00aa03 → 0xc05500ff;

演習問題解答例

ビット演算>左シフトと論理積による全ビット検査

左シフト(<<)と論理積(&)を使って、全ビットを検査するコードはよく使うので紹介しておく。

int x;
x に何らかの値を設定;
int bitCount = 0;
for(int mask=1; mask != 0; mask<<=1) {
  if( (x & mask) != 0 )
    ++bitCount;
}

上記は、x の全ビットを調べ、ビットの値が1であれば bitCount をインクリメントすることで、 x の中の値が1のビットの数を計算するコードだ。
mask の値は最初 1 で、ループ毎に左にシフトされて行き、上位ビットから溢れた時点でループを終了する。

このように、ループとシフトとビット演算を使うことはよくあるので、ちゃんと理解し、マスターしてほしい。

ビット演算>左シフト

左シフトとは、下図のように、各ビットをひとつ左にずらし、最下位ビットに0を入れることだ。最上位ビットの値は捨てられる(最上位ビット1で、それが捨てられることを「ビット溢れ」と呼ぶ)。

shift-left

C/C++ では 二項演算子 << が左ビットシフトを表す。
シフトするビット数は1だけとは限らず、「x << 2」 の様にシフトするビット数を付加して記述することが出来る。

int x = 0xff << 4;  // 0xff を4ビットシフトした値を x に代入
x <<= 2;  //  x を 2ビット左シフトし、それを x に代入

上記は C/C++ での左シフトの使用例だ。

2進数の各ビットの値を b[i] とすると、値は Σ (b[i] * 2^i) である。
1ビット左シフトするということは b[i+1] = b[i] を実行することなので、ビット溢れがなければ、シフト後の値は Σ (b[i] * 2^(i+1)) = Σ (b[i] * 2^i)*2) = 2 * Σ (b[i] * 2^i) となる。

つまり、ビット溢れが無い場合は、1ビット左シフトするということは値を2倍することを意味する。
2ビット左シフトなら4倍、3ビット左シフトなら8倍、4ビット左シフトなら16倍・・・ というわけだ。

このことがよく理解出来ない人は、10進数を考えるといいかもしれない。
例えば「123」を一桁左シフトすると「1230」となる。もとの値の10倍だ。これは10進数だからである。
2進数なら1ビット左シフトは2倍、N進数なら1桁左シフトはN倍ということだ。

演習問題:

  1. int x = 100; を宣言し、x を1ビット左シフトした値を表示し、値が2倍になっていることを確認しなさい
  2. char c = 5; を宣言し、c <<= 6 を実行すると、c の値はいくつになるかを事前に予想してから、結果を確かめなさい。
  3. int x; に何か数値が入っているとき、掛け算を使わず、左シフトを使って x を10倍にするコードを書きなさい。

 演習問題解答例