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

スポンサーリンク

鍛錬 354

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

2の補数表現においては,われわれの itoa プログラムでは,最大の負の数,すなわち \(-(2^{wordsize-1})\) に等しい n の値が処理できない。なぜダメか説明せよ。また,計算機のいかんにかかわらずこの値を正確に印字するように,これを修正せよ。

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

スポンサーリンク

最小値の値が処理できないことについての説明

問題文では、「2の補数表現においては,参考書の itoa プログラムでは最小値の処理ができない。この理由を説明せよ」と指示されています。

int の最小値と最大値

標準ヘッダ limits.h にて、int の最小値と最大値は以下のように定義されています。

signed int

/* Minimum and maximum values a `signed int' can hold.  */
#  define INT_MIN	(-INT_MAX - 1)
#  define INT_MAX	2147483647

つまり int の範囲は、最小値が -2147483648 であり、最大値が 2147483647 となります。

-2147483648 を2の補数表現で表すとどうなるのか

以下は、int の最小値である -2147483648 を2の補数表現で表しています。

-2147483648 = (1000 0000 0000 0000 0000 0000 0000 0000)
= ^(1000 0000 0000 0000 0000 0000 0000 0000) + 1
= (0111 1111 1111 1111 1111 1111 1111 1111) + 1
= (0111 1111 1111 1111 1111 1111 1111 1111) + (0000 0001)
= (1000 0000 0000 0000 0000 0000 0000 0000)
= 2147483648

 
上記に示した通り、int の最小値である -2147483648 を2の補数表現で表すと、

(1000 0000 0000 0000 0000 0000 0000 0000)

すなわち 2147483648 となってしまい、これは int の最大値である 2147483647 を超過してしまいます。

参考書の関数 itoa では符号がマイナスの場合に、n = -n と記述して符号を反転させていますが、仮に n が int の最小値である -2147483648 である場合、2の補数表現で表すと 2147483648 となってしまい、int の最大値を超過してしまいます。

よって、参考書の itoa プログラムでは最小値の処理ができません。

スポンサーリンク

参考書の関数 itoa を修正したプログラム

以下は、参考書の関数 itoa を修正したプログラム kr_3_4.c です。

今回は変換する数値として、int の最小値である -2147483648 をプログラム中で指定しています。

// include
#include <stdio.h>
#include <string.h>
#include <limits.h>

// preprocessor
#define NORMAL  0  // 通常
#define MINIMUM 1  // 最小値

// prototype
void itoa(int n, char s[]);
void reverse(char s[]);

// main
int main(void)
{
	char s[256] = "";
	int n;
	
	n = -2147483648;
	itoa(n, s);
	printf("数値   = %d\n", n);
	printf("文字列 = %s\n", s);
	
	return 0;
}

// ===================================
// @brief      数値を文字列に変換する
// @param[in]  n  変換する数値
// @param[out] s  変換後の文字列
// @return     無し
// @note       無し
// ===================================
void itoa(int n, char s[])
{
	int sign;
	int state;
	int i;
	
	// 状態を初期化(通常)
	state = NORMAL;
	
	if ((sign = n) < 0) {
		if (n == INT_MIN) {
			// 状態を変更(最小値)
			state = MINIMUM;
			n = n + 1;
			n = -n;
		}
		else {
			n = -n;
		}
	}
	
	i = 0;
	do {
		s[i] = n % 10 + '0';
		if (state == MINIMUM && i == 0) {
			s[0] = '8';
		}
		i++;
	} while ((n /= 10) > 0);
	
	if (sign < 0)
		s[i++] = '-';
	s[i] = '\0';
	
	reverse(s);
}

// =============================================
// @brief         文字列を,その位置で逆順にする
// @param[in/out] s  逆順にする文字列
// @return        無し
// @note          無し
// =============================================
void reverse(char s[])
{
	int c, i, j;
	
	for (i=0,j=strlen(s)-1; i < j; i++,j--) {
		c = s[i];
		s[i] = s[j];
		s[j] = c;
	}
}
スポンサーリンク

実行結果

以下は、kr_3_4.c を実行して、int の最小値である -2147483648 を文字列に変換しています。

***@ubuntu:~/***/test/c$ 
***@ubuntu:~/***/test/c$ gcc -Wall -Wextra kr_3_4.c -o kr_3_4
***@ubuntu:~/***/test/c$ ./kr_3_4
数値   = -2147483648
文字列 = -2147483648

 
上記に示した通り、数値の -2147483648 を文字列に変換することができました。

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