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

スポンサーリンク

鍛錬 313

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

整数 x の値を右に n ビット回転する関数 rightrot(x,n) を書け。

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

スポンサーリンク

プログラム

以下は、整数の値を、指定したビットだけ右に回転させるプログラム、kr_2_8.c です。

(※ unsigned int のサイズを 4byte(32bit) としています)

// include
#include <stdio.h>

// prototype
unsigned int rightrot(unsigned int x, int n);

// main
int main(void)
{
	unsigned int x;
	int n;
	
	// 初期化
	x = 123;  // ビット列
	n = 3;    // 回転するビット数
	
	x = rightrot(x, n);
	
	printf("%d\n", x);
	
	return 0;
}

// ================================================
// @brief     整数 x の値を右に n ビット回転させる
// @param[in] x  ビット列
// @param[in] n  回転するビット数
// @return    x -> 回転後ビット列
// @note      無し
// ================================================
unsigned int rightrot(unsigned int x, int n)
{
	unsigned int tmp;
	unsigned int storage;
	unsigned int ui_size;
	int i;
	
	// unsigned int のサイズを 4byte(32bit) とする
	ui_size = 4;
	
	for (i = 0; i < n; i++) {
		storage = x;
		x = x & ~(~0 << 1);
		tmp = x << (ui_size * 8 - 1);
		x = storage;
		x = x >> 1;
		x = x ^ tmp;
	}
	
	return x;
}
スポンサーリンク

実行結果の予測

上記に示した kr_2_8.c は、各パラメータを以下の通りに設定しています。

int n;

// 初期化
x = 123;  // ビット列
n = 3;    // 回転するビット数

x = rightrot(x, n);
 
項目 値 (10進数) 値 (2進数)
x:ビット列 123 0000 0000 0000 0000 0000 0000 0111 1011
n:右に回転するビット数 3

 
よって、関数 rightrot(x,n) のビット演算を行うと、以下に示す結果となるはずです。

1. storage = x

storage = x
storage = (0000 0000 0000 0000 0000 0000 0111 1011)

2. x = x & ~(~0

x = x & ~(~0 << 1)
x = (0000 0000 0000 0000 0000 0000 0111 1011) & ~(1111 1111 1111 1111 1111 1111 1111 1111 << 1)
x = (0000 0000 0000 0000 0000 0000 0111 1011) & ~(1111 1111 1111 1111 1111 1111 1111 1110)
x = (0000 0000 0000 0000 0000 0000 0111 1011) & (0000 0000 0000 0000 0000 0000 0000 0001)
x = (0000 0000 0000 0000 0000 0000 0000 0001)

3. tmp = x

tmp = x << (ui_size * 8 - 1)
tmp = (0000 0000 0000 0000 0000 0000 0000 0001) << (4 * 8 - 1)
tmp = (0000 0000 0000 0000 0000 0000 0000 0001) << 31
tmp = (1000 0000 0000 0000 0000 0000 0000 0000)

4. x = storage

x = storage
x = (0000 0000 0000 0000 0000 0000 0111 1011)

5. x = x >> 1

x = x >> 1
x = (0000 0000 0000 0000 0000 0000 0111 1011) >> 1
x = (0000 0000 0000 0000 0000 0000 0011 1101)

6. x = x ^ tmp

x = x ^ tmp
x = (0000 0000 0000 0000 0000 0000 0011 1101) ^ (1000 0000 0000 0000 0000 0000 0000 0000)
x = (1000 0000 0000 0000 0000 0000 0011 1101)

7. 上記 1 ~ 6 を、i < n 回の条件を満たす限り繰り返す

今回は n = 3 に設定しているので、あと 2 回、上記 1 ~ 6 を行います。

2回目

x = (1100 0000 0000 0000 0000 0000 0001 1110)

3回目

x = (0110 0000 0000 0000 0000 0000 0000 1111)

8. 結果予測

以上の結果より、プログラムを実行すると以下の値を取得できるはずです。

n進数
2進数 0110 0000 0000 0000 0000 0000 0000 1111
10進数 1610612751

 
上記の予測される結果は、以下に示す通り、「整数の値を、指定したビットだけ右に回転させる」ことができています。

入出力
入力 0000 0000 0000 0000 0000 0000 0111 1011
出力 0110 0000 0000 0000 0000 0000 0000 1111
スポンサーリンク

実行結果

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

***@ubuntu:~/***/test/c$ 
***@ubuntu:~/***/test/c$ gcc -Wall kr_2_8.c -o kr_2_8
***@ubuntu:~/***/test/c$ ./kr_2_8
1610612751

 
上記に示した通り、予測通り10進数の 1610612751 (2進数の場合は 0110 0000 0000 0000 0000 0000 0000 1111) を取得することができました。

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