link もっと前
   2008年 5月 3日 -
      2008年 5月 3日  
link もっと後

link 未来から過去へ表示(*)
link 過去から未来へ表示

日々

link permalink

何を補うの?

毎回話題がバラバラな日記ですみません。今日は補数の話です。

N 進数の補数は 2つあります。N の補数と、N-1 の補数です。10進数ならば 10 の補数と 10-1 の補数(9の補数ともいう)があります。

N 進数における二つの補数

ある N 進数 x の N の補数 y とは、足すと桁上がりする最小の数値を指します。
10進数でいきますと、x = 123 だとしたら、10 の補数は足すと桁上がり(1,000 になる)する最小の数値ですから 877 です。

要するに y = 1,000 - x = 1,000 - 123 = 877 と計算します。4桁の数字なら 10,000 から引けばいいですし、5桁なら 100,000 から、n 桁なら 10^(n) から引いてください。

ある N 進数 x の N-1 の補数 z とは、足しても桁上がりしない最大の数値を指します。
また 10進数を例に取ると、x = 123 として、10-1 の補数は足しても桁上がり(1,000)に達しない最大の数ですから、876 です。足すと 999 になります。

これも要するに z = (1,000 - 1) - x = 999 - x = 876 と計算します。特徴として、10 の補数から 1 引いても得られますし、逆に 10-1 の補数に 1 を加えると 10 の補数になります(この性質は後ほど重要です)。

補数の活用方法

N の補数は何が嬉しいかというと「負の数の表現として使えば、引き算が不要になる」という点です。

3桁の 10進数 500 - 300 を計算したいとします。「引き算は知らないが 3桁の足し算と 10 の補数を書いた表だけ持ってる」と仮定します。むちゃくちゃに見えますけど、後で意味が分かると思います。

引き算は知りませんので、まずは負の数を消しにかかります。負の数は絶対値の補数に置き換えて消します。表を見ると 300 の 10 の補数は 700(計算で出すなら 1,000 - 300)ですから、
500 - 300 = 500 + 700
こう置き換えます。すると足し算のみになって、計算できるようになります。
500 + 700 = 1,200
4桁目が出てきてしまいましたが、3桁の足し算しか知らんので 4桁目は捨てます。さようなら〜。
1,200 => 200
この結果は 500 - 300 = 200 の結果と一致します。

不思議に見えますが、そもそも補数 y の定義が y = 1,000 - x なので、x = 300 で式を展開すると、
500 + (1,000 - 300) = 1,200 --(4桁目無視)--> 200
となるのは当たり前といわれれば当たり前の結果です。しつこいですが大事なポイントは「引き算が足し算に化ける」という点です。

2進数だと非常に嬉しい

とはいえ、10進数だと補数を計算するために結局引き算が必要で、ありがたみがありません。これはその他の記数法(図では 3進数を例とした)でも同じです。


3進数と 3 の補数、3-1 の補数

ところが 2進数となると非常に嬉しい性質があります。以下の図を見てください。


2進数と 2 の補数、2-1 の補数

2進数においては全桁を反転させる演算(Not 演算)によって、容易に 2-1 の補数を得ることができ、そこに 1 加えれば 2 の補数を得ることができます。つまり Not 演算さえあれば 2 の補数の導出に引き算は不要です。コンピュータだからこそできる技といえましょう。

この性質のためコンピュータに減算器は不要で(※)、加算器の前に Not 演算と 1 加える回路をつけるだけで良いのです。回路が少なくなればコンピュータも安くなります。いやあ、補数って素晴らしいですね。

(※)コンピュータは前章の説明に出てきた「引き算は知らないが 3桁の足し算と 10 の補数を書いた表だけ持ってる」の代表格です。コンピュータの場合 2進数を扱うため 10の補数ではなく 2の補数です。
まとめると「一定桁(32桁、64桁など)の足し算と、2の補数しか知らない」変な奴と言えます。本当は意図的にそう作っていると言った方が正しいですけど…。

負の数を解釈

補数を負の数として扱うと良いこと(減算がなくなる)があるのは分かっていただけたかとおもいます。残る問題はどこからを負の数と見なすかです。卑近な例で言うと printf したときに、どこからマイナスなのよ?って話です。

前章まで話してきた計算の問題と関係ありそうに見えますが、実は全然関係ありません。ぶっちゃけた話、どこから負の数と見なしても構いません。以下の図をご覧下さい。


2進数から 10進数へ解釈する一方法

この図にある解釈方法ですと 2進数の 101 以上を負の数と見なします。

  • 101 未満の数を表示しなさいと言われたら、そのまま 10進数に変換した値を印字します。
  • 101 以上の数を表示しなさいと言われたら、補数をとって 10進数に変換した値と、マイナスの符号をともに印字します。
例えば 110 を渡されたら、101 以上なので補数を取って 010 とし、010 を 10進数にすると 3 なので、-3 と表示します。

何?ずれてる?いやいや…。このような解釈でも使っている人がウンと言えばそれで良いんです。とはいったものの、この方式ではウンと言う人は少なそうです。この方式は欠点が多すぎます。

桁が増えたときに正負の境界をどう決めるかがあいまいであるがために、境界を見分ける処理が複雑になる可能性があります。プログラマや回路設計者に嫌われますね。それとやたら正の数ばかりが多くて、負の数を使いたい人にも嫌われます。

良い解釈方法はあるか

多くの方が見慣れたパターンは、最上位のビットが 1 なら負の数と見なす、以下のような解釈方法でしょう。


2進数から 10進数へ解釈する効率的な方法

この解釈方法が採用されている理由は、効率的だからだと思われます。この解釈方法であれば、何桁になろうとも「最上位ビットの有無」という同じルールが適用できます。さらに正の数の範囲と負の数の範囲がほぼ同じ(負の数の範囲が 1 広いけど)で使いやすいのです。

[編集者: すずき]
[更新: 2008年 5月 4日 16:51]
link 編集する

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



link もっと前
   2008年 5月 3日 -
      2008年 5月 3日  
link もっと後

管理用メニュー

link 記事を新規作成

合計:  counter total
本日:  counter today

link About www.katsuster.net
RDF ファイル RSS 1.0
QR コード QR コード

最終更新: 9/17 20:03

カレンダー

<2008>
<<<05>>>
----123
45678910
11121314151617
18192021222324
25262728293031

最近のコメント 5件

  • link 18年09月07日
    すずき 「ありがとう!\nこちらこそ、楽しみにして...」
    (更新:09/11 19:30)
  • link 18年09月07日
    よしだあ 「おつかれさまでした!\nまた仕事できるの...」
    (更新:09/11 19:17)
  • link 18年08月15日
    すずき 「うーん、なんか暴走したり、動かなかったり...」
    (更新:08/15 10:52)
  • link 18年08月15日
    すずき 「実行できた。あと実行ファイルパスについて...」
    (更新:08/15 10:42)
  • link 18年08月15日
    すずき 「さすがに x86_64 と arm のク...」
    (更新:08/15 10:35)

最近の記事 3件

link もっとみる
  • link 18年09月13日
    すずき 「[府民から都民へ] 家が決まりました。今月末から東京都民です。さよ...」
    (更新:09/17 20:03)
  • link 18年09月11日
    すずき 「[エアコン浄化] 今年の 7月に(2018年 7月 17日の日記参...」
    (更新:09/17 19:38)
  • link 18年09月10日
    すずき 「[引っ越し準備] 引っ越し用の新品の段ボールが 50箱以上届き、家...」
    (更新:09/17 19:32)

こんてんつ

open/close wiki
open/close Java API

過去の日記

open/close 2002年
open/close 2003年
open/close 2004年
open/close 2005年
open/close 2006年
open/close 2007年
open/close 2008年
open/close 2009年
open/close 2010年
open/close 2011年
open/close 2012年
open/close 2013年
open/close 2014年
open/close 2015年
open/close 2016年
open/close 2017年
open/close 2018年
open/close 過去日記について

その他の情報

open/close アクセス統計
open/close サーバ一覧
open/close サイトの情報