Page List

Search on the blog

2010年10月2日土曜日

ビット演算で遊ぼう

Hi, folks. How's it going?
I made an application that deals with some bit operations. Guess it's downright interesting.
If you're unfamiliar with bit operations, I recommend you try the application below.

どうやら、アメリカからもアクセスがあるみたいなので、ちょっとだけ英語でも書いてみました。
今日はビット演算がテーマです。

世の変態天才プログラマーたちは、ビット演算を巧みに扱います。ビット演算の魔術師と言っても過言ではありません。
私も最近ビット演算のすごさに気付きました。ビットというのは2進数なのでいろいろなことに使えます。例えばバイナリサーチの応用のようなこと(※)もビット演算で出来ます
(※ 「のようなこと」と書いたのは少なくとも私のイメージではという意味です。0か1かを常に2つに1つの可能性を選んでデータを構築していて、探索時はO(log n)で出来るという意味です。詳しくは「ビット演算を用いたべき乗計算の高速化」参照のこと。)

『ビット演算を制するものはプログラムを制する!』
『そうか、ビット演算を使えば、コードの量も1/2になり、実行速度も2倍になる。
つまり、おれがビット演算を使えば、その働きは4倍っていうことか!!!』
桜木花道もびっくり@_@

ちょっと話が脱線しましたが、下がソースです。
ビット演算初心者向けです。かなり基本ですが動きを自分で見て確認するにはいいかと。。
あと、どのような演算を施すと何が起きるのかをしっかり把握できます。一度自分で同じようなものを作ってみるといいでしょう。




void getBin(int n, char bin[]) {
    REP (i, 16)
        bin[15 - i] = (n >> i & 1) + '0';
    bin[16] = '\0';
}

int main() {
    int n, bit;
    char calc, bin[16 + 1];

    cout << "Input an integer." << endl;
    cin >> n;
    getBin(n, bin);
    printf("%s\n", bin);

    // Input one of the manipulations below:
    // q exit
    // u bit change bit-th bit to '1'
    // d bit change bit-th bit to '0'
    // x bit reverse bit-th bit
    // c reverse all bits
    // where q, u, d, x and c are characters themselves, bit is an integer and 0-based.
    while (cin >> calc) {
        switch (calc) {
        case 'q':
            cout << "Bye!" << endl;
            return 0;
        case 'u':
            cin >> bit;
            n |= 1 << bit;
            break;
        case 'd':
            cin >> bit;
            n &= ~(1 << bit);
            break;
        case 'x':
            cin >> bit;
            n ^= 1 << bit;
            break;
        case 'c':
            n = ~n;
            break;
        default:
            cerr << "Syntax Error." << endl;
            cerr << "Try again." << endl;
            continue;
        }
        getBin(n, bin);
        printf("%s\n", bin);
    }
    return 0;
}

0 件のコメント:

コメントを投稿