桁あふれがわかりません

負数を2の補数で表現する符号付き16ビットの2進数を16進法で表示したもののうち，4倍するとあふれが生じるものはどれか。


ア　1FFF　　　イ　DFFF　　　ウ　E000　　　エ　FFFF

（平成１９年春　問３）


この問題の解説は以下の通りです。

DFFFの２進数表示は、1101 1111 1111 1111　で、４倍すると0111 1111 1111 1100　となり、負数が正数になるのであふれが生じる。

このように書いてありました。

１つ目の質問は、４倍すると1111 1111 1111 1100　となり、正数にはならないのではないか、ということです。
２つ目の質問は、直接この問題には関係ないかもしれないのです。
「元の数が負数のとき、左シフトで０が消えたとき、桁あふれという」と習ったのですが、なぜ０が消えると桁あふれとなるのでしょうか。

以上です。宜しくお願い致します。

No.4 ベストアンサー 回答者： Tann3 回答日時： 2013/03/13 21:15

　2進法の負数の表記法をしっかりと理解できていないようですね。

　2進数の負数は、「2の補数」という表記法を取ります。ここまではよいですよね？
　つまり、一番左のビットが「0」のとき正数、「1」のとき負数とするお約束です。
　ただし、これは一番左を「符号ビット」として固定して使用するというわけではありません。あくまで。一番左のビットも含めて「数値」を表しているのです。
　従って、2倍、4倍で左シフトするときにも、全体を左シフトし、符号を表す一番左のビットだけ特別扱いするものではありません。

　これは、「正数」のときはすんなり納得できるはずです。

　たとえば、十進数で「43」（例なのでいくつでもかまいません）は、2進数で

　　　0000　0000　0010　1011

です。これを、2倍、4倍すれば、

　2倍→　　0000　0000　0101　0110　（十進数で「86」）
　4倍→　　0000　0000　1010　1100　（十進数で「172」）

で、上位桁は「0」なので桁あふれはしていません。

　これが、左シフトを繰り返して、

　　　0101　0110　0000　0000

になったところで、さらに2倍すると、

　　　1010　1100　0000　0000

となり、一番左が「0→1」となって桁あふれします（補数表記だと「負数」になってしまう）。要するに、大きくなりすぎて「表記範囲逸脱」となるわけです。

　これが「負数」の場合だと、「0」と「1」の関係が逆転するわけです。つまり、「-43」は、補数表記（2の補数）で

　　　1111　1111　1101　0101

となります。これを2倍、4倍すると、
　　　　　　
　2倍→　　1111　1111　1010　1010　（十進数で「-86」）
　4倍→　　1111　1111　0101　0100　（十進数で「-172」）

となります。上の方に書いた「正数」とは、それぞれ2の補数であることが分かりますよね。

　つまり、「正数」では「0が桁あふれしても問題ない」のと同じように、負数では「1が桁あふれしても問題ない」のです。何故なら、補数表記だからです。

　これが正数と同じように、左シフトを繰り返して、

　　　1010　1010　0000　0000

になったところで、さらに2倍すると、

　　　0101　0100　0000　0000

となり、一番左が「1→0」となって桁あふれします（突然「正数」になってしまう）。マイナス側に大きくなりすぎて「表記範囲逸脱」となるわけです。

　ということで、非常に長くなりましたが、「正数の0の桁上がりは桁あふれではない」のと同じように、補数表記だと「負数の1の桁上がりは桁あふれではない」ということを理解すれば、納得できるのではないでしょうか。


　ご質問に対しては、

＞１つ目の質問は、４倍すると1111 1111 1111 1100　となり

→いいえ、1101 1111 1111 1111　を４倍すると、単に２桁左シフトで　0111 1111 1111 1100　となります。
　上に書いたように、一番左のビットが「符号ビットで固定」と考えるのは間違いです。

＞２つ目の質問：
＞「元の数が負数のとき、左シフトで０が消えたとき、桁あふれという」と習った

→正確には、「元の数が負数のとき、左シフトで数値としての０が消えたとき（数値としての0が符号ビットの位置になってしまったとき）、桁あふれという」ということかと思います。

この回答へのお礼

回答ありがとうございます。

＞一番左のビットが「符号ビットで固定」と考えるのは間違いです。

この助言で全てが解決しました！詳しく分かりやすい解説に本当に感謝します。ずっと勘違いしていたみたいです。
また、２つ目の質問にも丁寧に教えて下さり大変感謝いています。

お礼日時：2013/03/14 02:38

No.3 回答者： koujikuu 回答日時： 2013/03/13 19:54

補足２です、

マシン語レベルで考えると、最上位ビットを変えずに左シフト（×２）する命令はありません
符号付シフト命令は、
左シフト（×２）　8086 SAL命令 Z-80 SLA命令 AVR LSL命令　に相当します
右シフト（÷２）　8086 SAR命令 Z-80 SRA命令 AVR ASR命令　に相当します

左シフト命令は、全ビットを上位にシフトさせ、最下位に０が入ります
右シフト命令は、全ビットを下位にシフトさせ、最上位にシフトさせる前の最上位ビットがはいります

（左シフト命令は、符号付でも、符号無しでも動作は変わりません）

詳しくは命令表を参照して下さい。
http://software.aufheben.info/kouza/beginner/kou …
http://www.zilog.com/docs/z80/um0080.pdf
http://www.avr.jp/user/DS/PDF/AVRinst.pdf

この回答へのお礼

＞左シフト命令は、全ビットを上位にシフトさせ、最下位に０が入ります
　右シフト命令は、全ビットを下位にシフトさせ、最上位にシフトさせる前の最上位ビットがはいります

（左シフト命令は、符号付でも、符号無しでも動作は変わりません）

おっしゃる通りに覚えておきます。

何度も回答ありがとうございました！

お礼日時：2013/03/14 02:26

No.2 回答者： koujikuu 回答日時： 2013/03/13 09:32

補足です、

数学上はマイナス値を二倍にしてもプラスになることはありません
符号付は数値部１５ビットで表します、１５ビットで表せない数になると、オーバーフローエラーです
左シフト（×２）して、最上部ビットが変わらなければ、オーバーフロー無しと判断できます
「右シフト（÷２）では、最上部ビットを変えずにシフトする命令があります」

この回答へのお礼

回答ありがとうございます。

＞左シフト（×２）して、最上部ビットが変わらなければ、オーバーフロー無しと判断できます

最上部ビット＝符号ビットと解釈しても大丈夫ですか？
このように解釈するとき、

「左シフトのとき、最上部ビット（符号ビット）はシフトされ、
　右シフトのとき、最上部ビット（符号ビット）はシフトされない」

ということでしょうか。符号ビットは左シフトにしろ、右シフトにしろシフトされないと学習したのですが。。
もしかして論理シフトで議論すべき問題だったのでしょうか。
論理シフトならば最上部ビットはシフトされるのでつじつまが合うと思います。

お手数かけます。。

お礼日時：2013/03/13 17:49

No.1 回答者： koujikuu 回答日時： 2013/03/13 00:27

1) 符号付の場合　最上位ビットが、正負を表します

0xDFFF = B'1101111111111111'
0xBFFE = B'1011111111111110' *2
0x7FFC = B'0111111111111100' *4 最上位ビットが変化する行あふれ、正の数になる

0x0000-0x7FFF = 0 ～ 32767
0x8000-0xFFFF = -32768 ～ -1　補数を表します

補数とは加算するだけで、減算と同じ結果になります

0x0001 + 0xFFFF = 0x0000
1 + (-1) = 0 と同じことです

この回答への補足

回答ありがとうございます。
最上位ビット即ち符号ビットはシフトしないと考えているので、

元の数
[1]101 1111 1111 1111

を４倍して、

10[1]111 1111 1111 1100

即ち1111 1111 1111 1100
になると考えているのですがこれが間違ってますか？符号ビットは[]で分かりやすくしています。

このように考えれば、正から負になることはありえないと思ってしまうんですが。。

補足日時：2013/03/13 00:58