ビット演算で遊ぼう

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倍っていうことか！！！』

桜木花道もびっくり@_@

ちょっと話が脱線しましたが、下がソースです。

ビット演算初心者向けです。かなり基本ですが動きを自分で見て確認するにはいいかと。。

あと、どのような演算を施すと何が起きるのかをしっかり把握できます。一度自分で同じようなものを作ってみるといいでしょう。

view plainprint?

1. void getBin(int n, char bin[]) {  
2.     REP (i, 16)  
3.         bin[15 - i] = (n >> i & 1) + '0';  
4.     bin[16] = '\0';  
5. }  
6.   
7. int main() {  
8.     int n, bit;  
9.     char calc, bin[16 + 1];  
10.   
11.     cout << "Input an integer." << endl;  
12.     cin >> n;  
13.     getBin(n, bin);  
14.     printf("%s\n", bin);  
15.   
16.     // Input one of the manipulations below:  
17.     // q       exit  
18.     // u bit   change bit-th bit to '1'  
19.     // d bit   change bit-th bit to '0'  
20.     // x bit   reverse bit-th bit  
21.     // c       reverse all bits  
22.     // where q, u, d, x and c are characters themselves, bit is an integer and 0-based.  
23.     while (cin >> calc) {  
24.         switch (calc) {  
25.         case 'q':  
26.             cout << "Bye!" << endl;  
27.             return 0;  
28.         case 'u':  
29.             cin >> bit;  
30.             n |= 1 << bit;  
31.             break;  
32.         case 'd':  
33.             cin >> bit;  
34.             n &= ~(1 << bit);  
35.             break;  
36.         case 'x':  
37.             cin >> bit;  
38.             n ^= 1 << bit;  
39.             break;  
40.         case 'c':  
41.             n = ~n;  
42.             break;  
43.         default:  
44.             cerr << "Syntax Error." << endl;  
45.             cerr << "Try again." << endl;  
46.             continue;  
47.         }  
48.         getBin(n, bin);  
49.         printf("%s\n", bin);  
50.     }  
51.     return 0;  
52. }  

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;
}