K&R 演習2-9 解答 (プログラミング言語C 第2版)

スポンサーリンク

鍛錬 318

K&R 演習2-9 解答 (プログラミング言語C 第2版)

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

B.W.カーニハン D.M.リッチー 石田晴久 訳 『プログラミング言語C 第2版 ANSI 規格準拠』, (共立出版, 2017), pp.63.

スポンサーリンク

なぜ、x の最も右の 1 ビットが消えるのかについての説明

問題文では、「2 の補数のシステムでは、x=x&(x-1) により、x の最も右の 1 ビットが消える。この理由を説明せよ」と指示されています。

x を 8 ビット の数値である 0100 1110 (10進数表記で 78) として説明します。

問題文で与えられた式「x = x & (x – 1)」について、(x – 1) の部分は以下の通りに書き換えることができます。

(x - 1)
= (x + (-1))

 
書き換え後の (-1) を 2 の補数のシステムで表現すると、以下に示す通りになります。

(x + (-1))
= (x + (^(0000 0001) + 1))
= (x + ((1111 1110) + 1))
= (x + ((1111 1110) + (0000 0001)))
= (x + (1111 1111))

 
上記に示した通り、問題文で与えられた式「x = x & (x – 1)」について、(x – 1) の部分を 2 の補数のシステムで表現すると、(x + (1111 1111)) となりました。

よって、与えられた式 x = x & (x – 1) について 2 の補数のシステムで表現すると、以下に示す通りになります。

(x を 8 ビット の数値である 0100 1110 (10進数表記で 78) として説明します。)

x = x & (x - 1)
x = x & (x + (1111 1111))
x = (0100 1110) & ((0100 1110) + (1111 1111))
x = (0100 1110) & (0100 1101‬)
x = (0100 1100)

 
上記に示した通り、x の最も右の 1 であるビットが消えました。

以下は、「x = x & (x – 1)」の処理を、実行する前と実行した後の差異です。

前後
処理前 0100 1110
処理後 0100 1100
スポンサーリンク

旧バージョンの bitcount 関数

以下は、参考書に記述されている関数 bitcount です。

関数 bitcount は、unsigned x の中の 1 であるビットを数える関数です。

/* bitcount: x の中の 1 であるビットを数える */
int bitcount(unsigned x)
{
	int b;
	
	for (b = 0; x != 0; x >>= 1)
		if (x & 01)
			b++;
	return b;
}

B.W.カーニハン D.M.リッチー 石田晴久 訳 『プログラミング言語C 第2版 ANSI 規格準拠』, (共立出版, 2017), pp.62.

 
上記に示した通り、参考書に記述されている関数 bitcount は、右に 1 ビットシフトしながら全てのビットを順に走査し、(x == 0) になった時点でループから抜けます。

スポンサーリンク

新バージョンの bitcount 関数

問題文では、「もっと速い bitcount プログラムを書け」と指示されています。

以下は、参考書に記述されている関数 bitcount を書き直しています。

関数 bitcount は、unsigned x の中の 1 であるビットを数える関数です。

/* bitcount: x の中の 1 であるビットを数える */
int bitcount(unsigned x)
{
	int b;
	
	for (b = 0; x != 0; b++)
		x = x & (x - 1);
		
	return b;
}

 
上記に示した通り、書き直した関数 bitcount は、全てのビットを走査せずに、x の最も右の 1 であるビットを消していき、(x == 0) になった時点でループから抜けます。

スポンサーリンク

プログラム

以下は、書き直した関数 bitcount を記述したプログラム kr_2_9.c です。

※ x の値を 78 (2進数表記で 0100 1110) に設定しています。

// include
#include <stdio.h>

// prototype
int bitcount(unsigned x);

// main
int main(void)
{
	unsigned x;
	int ret;
	
	// 初期化
	x = 78;  // ビット列
	
	ret = bitcount(x);
	
	printf("%d\n", ret);
	
	return 0;
}

// ============================================
// @brief     x の中の 1 であるビットを数える
// @param[in] x  ビット列
// @return    x -> x の中の 1 であるビットの数
// @note      無し
// ============================================
int bitcount(unsigned x)
{
	int b;
	
	for (b = 0; x != 0; b++)
		x = x & (x - 1);
		
	return b;
}
スポンサーリンク

実行結果

以下は、プログラム kr_2_9.c を実行しています。

今回はプログラム中で x の値を 78 (2進数表記で 0100 1110) に設定しているため、1 であるビットの数として 4 という結果を取得するはずです。

***@ubuntu:~/***/test/c$ 
***@ubuntu:~/***/test/c$ gcc -Wall -Wextra kr_2_9.c -o kr_2_9
***@ubuntu:~/***/test/c$ ./kr_2_9
4

 
上記に示した通り、1 であるビットの数として 4 という結果を取得することができました。

タイトルとURLをコピーしました