K&Rを読もう(32) 演習 2-9 - 2-10 bitcount

GCC

感動した。

演習 2-9

2の補数システムでは、x = x & (x - 1)により、xの最も右の1ビットが消える。何故かを説明せよ。この事実を使って、もっと早いbitcountプログラムを書け。

説明

01110000で説明する。

x - 1をすると、

01110000 - 1 = 01101111

一番右の1が消えて、右側全てのビットが立つことになる。

&を使えば、1 & 1以外は全て0になるので、

x & (x - 1)をすると、

01110000 & 011011111 = 0110000

xの最も右の1ビットが消える。

0になるまで繰り返せば、ビットの立った数がわかる。繰り返し回数 = ビットの立っている数 となるので、ビットシフトするより断然早い断然早い場合がある。

ソース

int bitcount(unsigned char x)
{
    int b;

    for (b = 0; x != 0; x &= x - 1)
        b++;

    return b;
}

感動した。

もっと感動する奴

随想録: ビットカウントのfor文一つでビットカウント

int bitcount(unsigned x)
{
    int b;

    for (b = x; x >>= 1; b -= x);

    return b;
}

難解です・・・。速くはない。

演習 2-10

lowerを三項演算子で書き直す問題。

int lower(int c)
{
    return ('A' <= c && c <= 'Z') ? c + 'a' - 'A' : c;
}

三項演算子は式なので値を返す。if文より断然ステキ。

ナウでヤングなのは「if式」だよね。