2.10 代入演算子と式, 演習2-9 K&R プログラミング言語C

2.10 代入演算子と式

/* 右端のビットが 1 の場合 b をインクリメントする
 * x = 141 : 1000 1101 => 141 inc
 * x >>= 1 : 0100 0110 => 70
 * x >>= 1 : 0010 0011 => 35 inc
 * x >>= 1 : 0001 0001 => 17 inc
 * x >>= 1 : 0000 1000 => 8
 * x >>= 1 : 0000 0100 => 8
 * x >>= 1 : 0000 0010 => 2
 * x >>= 1 : 0000 0001 => 1 inc
 * x >>= 1 : 0000 0000 => 0
 *
 * y = 238 : 1110 1110 => 238
 * y >>= 1 : 0111 0111 => 119 inc
 * y >>= 1 : 0011 1011 => 59 inc
 * y >>= 1 : 0001 1101 => 29 inc
 * y >>= 1 : 0000 1110 => 14
 * y >>= 1 : 0000 0111 => 7 inc
 * y >>= 1 : 0000 0011 => 3 inc
 * y >>= 1 : 0000 0001 => 1 inc
 * y >>= 1 : 0000 0000 => 0
 */

#include <stdio.h>

int bitcount(unsigned x);

int main(int argc, char *argv[])
{
    unsigned x, y;

    x = 141; /* 1000 1101 */
    y = 238; /* 1110 1110 */
    printf("x = 141\nbitcount(x) => %u\n", bitcount(x)); /* => 4 */
    printf("y = 238\nbitcount(y) => %u\n", bitcount(y)); /* => 6 */

    return 0;
}

/* bitcount : x の中の 1 であるビットを数える */
int bitcount(unsigned x)
{
    int b;

    for (b = 0; x != 0; x >>= 1) {
        if (x & 01) {
            b++;
        }
    }

    return b;
}

実行結果

$ ./bitcount
x = 141
bitcount(x) => 4
y = 238
bitcount(y) => 6

演習2-9

最も右の 1 であるビットから右端のビットまでを反転させると 1 減算する
1 減算すると、最も右端にある 1 であるビットから右端のビットまでが反転される。
1 減算したものとの AND をとっていくと最も右端にある 1 であるビットが 0 になってゆく。
ループの回数は 1 であるビットの現われる回数となる。

/* x = 141 : 1000 1101 &= 140 : 1000 1100 => 140 : 1000 1100
 * x = 140 : 1000 1101 &= 139 : 1000 1011 => 136 : 1000 1000
 * x = 136 : 1000 1000 &= 135 : 1000 0111 => 128 : 1000 0000
 * x = 128 : 1000 0000 &= 127 : 0111 1111 => 0   : 0000 0000
 *
 * x = 238 : 1110 1110 &= 237 : 1110 1101 => 236 : 1110 1100
 * x = 236 : 1110 1100 &= 235 : 1110 1011 => 232 : 1110 1000
 * x = 232 : 1110 1000 &= 231 : 1110 0111 => 224 : 1110 0000
 * x = 224 : 1110 0000 &= 223 : 1101 1111 => 192 : 1100 0000
 * x = 192 : 1100 0000 &= 191 : 1011 1111 => 128 : 1000 0000
 * x = 128 : 1000 0000 &= 127 : 0111 1111 => 0   : 0000 0000
 */

#include <stdio.h>

int bitcount(unsigned x);

int main(int argc, char *argv[])
{
    unsigned x, y;

    x = 141; /* 1000 1101 */
    y = 238; /* 1110 1110 */
    printf("x = 141\nbitcount(x) => %u\n", bitcount(x)); /* => 4 */
    printf("y = 238\nbitcount(y) => %u\n", bitcount(y)); /* => 6 */

    return 0;
}

int bitcount(unsigned x)
{
    int b;

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

    return b;
}

実行結果

$ ./ex2-9
x = 141
bitcount(x) => 4
y = 238
bitcount(y) => 6
プログラミング言語C 第2版 ANSI規格準拠
B.W. カーニハン D.M. リッチー
共立出版
売り上げランキング: 9726
«
»