【python】第2回 チキチキ プログラミング初心者のための型に関する考察 ~負の整数~【学習】
第2回 チキチキ プログラミング初心者のための型に関する考察 ~負の整数~
はじめに
第1回では、正の整数と2進数の関係、、2進数とビット数の関係、オーバーフローなどについて考えてみました。
- 型
- 型とはメモリ内での数値表現のこと
- 大きく分けて、整数、実数、文字型などがある
- 整数型は2進数で表現され、その表現できる範囲はbit数で決まる
- 整数型の型の違いは主に、bit数の違い
- 桁あふれが起こると、あふれた桁は捨てられる
- 型変換
- n進数について
- 10進数とn進数の変換方法
- n進数から10進数に変換する方法
などを、実例を交えて考えてみました。
今回は、整数型の負の数について考えてみたいと思います。
おそらくpythonプログラマにはあまり必要ない知識かと思いますが、その表現法や仕組みは情報処理技術者試験に頻出ですので、すこし掘り下げてみましょう!
応用情報技術者平成25年秋期 午前 問3 負の整数を表現する代表的な方法として,次の3種類がある。 a. 1の補数による表現 b. 2の補数による表現 c. 絶対値に符号を付けた表現(左端ビットが0の場合は正,1の場合は負) 4ビットのパターン1101を a~c の方法で表現したものと解釈したとき, 値が小さい順になるように三つの方法を並べたものはどれか。
ア | a, c, b |
---|---|
イ | b, a, c |
ウ | b, c, a |
エ | c, b, a |
こんな感じの問題が基本除法技術者試験や、応用情報技術者試験にぽろぽろと出題されます。
符号付と符号なし整数
pythonでは、符号あり、符号なしの指定を整数につけることはできません。また、bit数による範囲の制限がないため、pythonコーダーの皆さんは、特に整数の型について意識することなくコーデイング出来るということは、前にも書きました。
しかしながら、世の中のこれまでの主流プログラミング言語(C/C++,C#,Javaなど)でのコーデイングの際には、コーダーはそのデータの型の値域を考えて、また、メモリ使用量をなるべく少なくするために適切な型を考えながら書いていくのが通常でした。
(最悪、浮動小数点数よりも整数の方が計算が何倍も速いということで、小数点数を整数で計算するギミックなんかを作ったり。。。)
ということで、整数型では、同じビット幅で同じビット列でも2種類の読み方ができてしまいます。
10001000 | 136 | 符号なし |
---|---|---|
10001000 | -120 | 符号あり |
pythonでは、ほとんど考えに及びませんが、Cプログラマなどは、この差を考えながらコーデイングしているってわけです。
実際には、例えばC言語の場合は変数を宣言するときに、以下のように宣言することになっています。
signed/ unsigned | 型 | 変数名 | ; | 実際の宣言文(全部繋げたやつ) |
signed | int | bar | ; | signed int bar; |
unsigned | int | bar | ; | unsigned int bar; |
signed | char | cbar | ; | signed char cbar; |
unsigned | char | cbar | ; | unsigned char cbar; |
signedが符号あり、unsignedが符号なしを表します。
(実数型では、その表現法の内容からsigned,unsignedの区別が持てません)
signed, unsignedは整数型の修飾子ということになります。
また、デフォルトでは変数はsignedとして宣言されることになっているので、signedとあえて書くことはあまりありません。
符号ありと、符号なしの整数値
前回の、説明で以下のような表がありました。
型名 | 種類 | サイズ | 範囲 | 備考 |
---|---|---|---|---|
int | 整数 | 4byte | -2147483648 〜 2147483647 | 負数は2の補数表現 |
short | 整数 | 2byte | -32768 〜 32767 | 負数は2の補数表現 |
char | 整数 | 1byte | -128~127 | 負数は2の補数表現 |
これは、すべてsignedの時の表となっています。それでは、unsignedの時はどうなるのでしょうか?
型名 | 種類 | サイズ | 範囲(signed) | 範囲(unsigned) | 備考 |
---|---|---|---|---|---|
int | 整数 | 4byte | -2147483648 〜 2147483647 | 0 ~ 4,294,967,295 | 負数は2の補数表現 |
short | 整数 | 2byte | -32768 〜 32767 | 0 ~ 65,535 | 負数は2の補数表現 |
char | 整数 | 1byte | -128~127 | 0 ~ 255 | 負数は2の補数表現 |
実際の詳しいビット数とデータ範囲の関係については、MSDocsにまとまっています。
データ型の範囲 | Microsoft Docs
次は、実際にメモリ内で負の数がどう表現されているか見てみます。
3つの負数表現
負の数の表現には大きく分けて、3種類あります。
初めに貼った、応用情報技術者試験の問題ではその3つがフル出題されています。
詳しくは以下の3つです。
- 負数の表現
- 符号付絶対値表現
- 1の補数表現
- 2の補数表現
それぞれの表現法を見ていきましょう。
負の数の表現:符号付絶対値表現
数値を符号と絶対値に分けて表現する方法です。
算数などで習う計算法と同じ表現法なので、非常にわかりやすいです。
符号:(+、-)
絶対値:(0~9の数字の羅列)
- 100, -100など
これはわかりやすいですね、ただ、(型にうるさい)コンピュータの世界では、0と1しか使えずビット数が決まっています。
例えば8ビット整数(char)で、10進数の-15を表すときに、
10進数 | 2進数 | 16進数 |
-15 | -00001111 | -0F |
と出来ればいいですが、+、-という符号はプログラミング言語(高級言語)では使えても、CPUの命令のレベルでは使えません。
そこで、8ビット中の上位の1ビットを符号として犠牲にして、残りの7ビットで絶対値を表します。
符号 | 数値 |
+ | 0 |
- | 1 |
絶対値は7ビットですので、0~127(2^7 - 1)まで表せます。
- 105と-105を作ってみましょう
まず、絶対値として、7ビットで10進数の105を作ります。
105(10進数)→ 1101001(2進数)
10進数 | 符号 | 絶対値 | 符号付絶対値表現 |
+105 | 0 |
1101001 | 01101001 |
-105 | 1 |
1101001 | 11101001 |
と、表現するのが符号付絶対値表現です。わかりやすいですよね。
しかし、10進数の0を表現するときに、
10進数 | 符号 | 絶対値 | 符号付絶対値表現 | |
0 | + | 0000000 | 00000000 | |
0 | - | 0000000 | 10000000 |
+0と、-0が出てきます。
さらに、
+105 | 01101001 |
||
+ | -105 | + | 11101001 |
0 |
101010010 |
10進数は足すと0になるのに、2進数では足しても0になりません。
人間にはわかりやすい表現法ですが、コンピュータが計算を行うためにはいろいろ工夫が必要そうです。
負の数の表現:1の補数表現
次は、補数を使う方法です。
一般的にn進数には、2つの補数があります。nの補数と(n-1)の補数です。
10進数なら10の補数と9の補数があり、2進数なら2の補数と1の補数がある。
8進数なら8の補数と、7の補数がある。
ってな感じです。
nの補数 |
(n-1)の補数 |
足したときにぎりぎりすべての桁が桁上げされる数 | 足したときにぎりぎりすべての桁が桁上げしない数 |
10進数の場合は、
元の数 | 10の補数 | 9の補数 |
456 | 544 | 543 |
10の補数:456+544 = 1000
9の補数:456+543 = 999
8進数の場合は
元の数 | 8の補数 | 7の補数 |
456 | 322 | 321 |
8の補数:456+322 = 1000
7の補数:456+321 = 777
2進数の場合は
元の数 | 2の補数 | 1の補数 |
1001 | 0111 | 0110 |
2の補数:1001+0111 = 10000
1の補数:1001+0110 = 1111
となります。どの補数も nの補数=(n-1)の補数+1とな
っています。
2進数の場合数字のバリエーションが0と1しかないのでとても簡単で、
1の補数→元の数のすべてのビットをビット反転
101001 → 010110
2の補数→1の補数+1
101001 -(1の補数)-> 010110 -(1の補数+1)-> 010111
となります。
ここでやっと、負の数の話に戻りますが、このうち元の数を1の補数に変換したものを負の数として使うものが1の補数表現です。(=ビット反転したらその数の負の数バージョン)
10進数の59で考えてみます
59の2進表現は 00110011
このとき-59は 00110011 -(ビット反転)-> 11001100
となります。また、最左ビットが1のものを負の数、0のものを正の数として扱います。
つまり、
00001101 => 最左ビットが0なので正の数なので、そのまま10進数に変換して+13を表している。
11110010 => 最左ビットが1なので負の数、 ビット反転してからマイナス符号をつけて10進数に直すと
11110010 -(ビット反転)-> 00001101 -> -13
ということになります。
ただし、この方法でも、
00000000 -> +0
11111111 -> - 0
のプラスマイナスの2つの0が存在してしまします。
つぎに、+13 と -13 を足してみます。
00001101
+11110010
11111111
- 13は+13をビット反転したものなので、当たり前のように全ビット1になりますが、これは1の補数表現では -0 なので、計算上は正しく計算できているということになります。
1の補数の世界で、正確に足し算を行うためには、普通に足し算を行って、
最上位で桁上りがない場合 = そのまま答え
最上位で桁上りがある場合 = 桁上りを最右ビットに足す
例1)桁上りなしの場合
10進数: 13 + 8 = 21
2進数: 00001101 + 00001000 = 00010101 => 10進数で 13 + 8 = 21
例2)桁上りありの場合
10進数: 13 + (-8) = 5
2進数: 00001101 + (11110111) = 100000100
桁上り1 (1)(00000100)
最右に桁上りを足す 00000101 => 10進数で 13-8 = 5
このように、演算的に比較的簡単に正しい結果を導けるので、一昔前のコンピュータでは1の補数を使って負の数を表すものもありました。近年では、次に説明する2の補数表現のものが多いと思います。
負の数の表現:2の補数表現
2の補数の作り方については、上で説明したとおりです。1の補数に1を足してできた2の補数を元の数の負の数バージョンとして使う方法です。
先ほどと同様に、10進数の59で考えてみます。
59の2進表現は 00110011
このとき-59は 00110011 -(ビット反転)-> 11001100 -(+1)-> 11001101
となります。また、最左ビットが1のものを負の数、0のものを正の数として扱います。
つまり、10進数との対応を考えると
00001101 => 最左ビットが0なので正の数なので、そのまま10進数に変換して+13を表している。
11110010 => 最左ビットが1なので負の数、 ビット反転してからマイナス符号をつけて10進数に直すと
11110010 -(-1)->11110001 -(ビット反転)-> 00001101 -> -13
この方法では、0は 00000000 のみです。
また、2つの数の足し算の結果は以下のように求められます。
最上位で桁上りがない場合 = そのまま答え
最上位で桁上りがある場合 = 桁あふれを捨てると答え
例1)桁上りなしの場合
10進数: 13 + 8 = 21
2進数: 00001101 + 00001001 = 00010101 => 10進数で 13 + 8 = 21
例2)桁上りありの場合
10進数: 13 + (-8) = 5
2進数: 00001101 + (11111000) = 100000101
桁上り1 (1)(00000101)
最右に桁上りを捨てる 00000101 => 10進数で 13-8 = 5
第1回でも説明しましたが、桁上りではみ出てしまったビットは自動的に捨てられます。
つまり、2の補数表現では負の数が混じっても、通常の足し算を行うだけで計算の結果が得られる。
ということです。
ここまでくれば、初めに提示した、応用情報技術者試験の問題解けますよね?
ちょっと問題解いてみる
応用情報技術者平成25年秋期 午前 問3 負の整数を表現する代表的な方法として,次の3種類がある。 a. 1の補数による表現 b. 2の補数による表現 c. 絶対値に符号を付けた表現(左端ビットが0の場合は正,1の場合は負) 4ビットのパターン1101を a~c の方法で表現したものと解釈したとき, 値が小さい順になるように三つの方法を並べたものはどれか。
ア | a, c, b |
---|---|
イ | b, a, c |
ウ | b, c, a |
エ | c, b, a |
ここで出てくる3つの負の数の表現法は、前の節の通りの3つですね。
そのうえで、4ビットのビット列1101を3つのパターンで解釈したときに、その示す値がちいさい順に並べたのはどれか、って問題です。
値を実際に計算してみます。
a. 1の補数による表現:1101 ->最左ビット1なので負の数 -(bit反転)-> 0010 -> -2
b. 2の補数による表現:1101 ->最左ビット1なので負の数 -(-1)-> 1100 -> (bit反転) -> 0011 -> -3
c. 符号付絶対値表現だった場合:1101 ->最左ビット1なので負の数 -> (符号)(絶対値) =(1) (101) -> -5
a | -2 |
b | -3 |
c | -5 |
なので、c, b, aとなり、答えは「エ」ですね。