技術的雑談-技術的雑談-2進数って何ですか？
説明
2進数演算
コンピュータの本を読むと必ず出てくる「0」と「1」の塊の話です。
「10進数」とは、「0〜9」の記号に数量的意味を持たせ、10以上の数量には「桁」で表現をします。
言うまでもなく、「57」とは、「10が5個と7」の量を表します。
つまり、「n進数」と言った場合は、「n進数の表現でabcd」＝a×n^3 + b×n^2 + c×n^1 + d×n^0 ということです。(「^」はべき乗の意味です。これもコンピュータ言語的な表記方法ですが…。 10^3とは 10×10×10の意味です。)
じゃあ、「2進数」とは何かというと、「0〜1」の記号に意味を持たせ、2以上の数量には「桁」で表現をした数値表現方法です。
先程の10進数で57という数は、57 = 1×2^5 + 1×2^4 + 1×2^3 + 0×2^2 + 0×2^1 + 1×2^0 = 111001と表せます。
2進数の表現
いきなり「111001」とだけ書いてあっても、これが「2進数で57」なのか「10進数で11万1千1」なのかわからないですよね？
昔のプログラム本とかでは「111001b」とか「111001B」（bはbinary systemのb。）表記していましたが、今は64bitとか128bitの数値もありうるので、16進数の「b」とも混同してしまうかもしれないので、あまり使われていません。
(C言語でもなぜか2進数表記はなかったしね…。8進数と16進数の表記はあるのに。（汗）)
2何で2進数なの？
コンピュータは電気で動いています。
電気には（現行の技術では）「流れている」「流れていない」のどちらかの状態しかありません。
なので、電気を「記号」とした場合、2種類の「記号」しかないわけです。
だから2進数表現を使うと「作りやすい」わけです。
極端な話、「0ボルトが"0"、1ボルトが"1"、、、、、9ボルトが"9"」とかやってムリヤリ10進数のコンピュータを作ることもできなくは無いでしょうが、電気技術的な諸所の問題でそれは非常に面倒なことになり、また非常に不正確だったりします。
電線にノイズが乗ったり、状態の境界が多くなったり…。
なので、「今のところは」2進数のコンピュータが作られ続けていくわけです。
この先はどうなるかわかりませんが…。
2進数→10進数変換
これはかなり簡単。
- 2進数の一番下の桁(右側)をそのまま取り出します。(0か1)
- 2進数の右から2番目の桁を取り出し、×2^1します。(2をかけます。) それを先の結果に足します。
- 2進数の右から3番目の桁を取り出し、×2^2します。(4をかけます。) それを先の結果に足します。
以下、2進数の桁の数だけ繰り返します。
ってか、16桁の2進数の最大は65535なので、各桁の「重み」を暗記してしまうほうが簡単です。
65536までの2進数の各桁 ： 1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536
(ごめんなさい！8192までしかパッと出てこなかった！！(自爆))
10進数→2進数の変換
いくつか方法がありますが、2で割り続けるという方法がポピュラーなのでしょうか？
例) 10進数100を2進数表記に直す (1) 100 ÷ 2 = 50 余り 0 (2) 50 ÷ 2 = 25 余り 0 (3) 25 ÷ 2 = 12 余り 1 (4) 12 ÷ 2 = 6 余り 0 (5) 6 ÷ 2 = 3 余り 0 (6) 3 ÷ 2 = 1 余り 1 (7) 1 ÷ 2 = 0 余り 1 ← 商が0になったので終了 で、(1)〜(7)の余りを右から順番に並べていきます。
よって10進数100 ＝ 2進数1100100です。
検算すると 1100100 = 64 + 32 + 4 = 100ですね。
いや、10進数256(＝2進数100000000)ぐらいまでならなんとなく暗算で変換できるようになりますよ。(^^)
ヘンクツなやり方では、「片手で31まで数える」とか応用が利きます。
2の補数表現
上の2進数の表記だと、正の数はいいのですが、負の数はどうするんでしょうか？
コンピュータにこの数はプラスかマイナスかの情報を与えてあげないといけませんね。
普通に考えれば「-1111」とか書けば10進数で「-15」と同じ数値を表しますよね？
でも、コンピュータに「この数はマイナスだよ」と教えるにはどうしたら良いのでしょうか？
今日の一般的なコンピュータ(CPU)では、2の補数表現というものを使って負の数を表します。
これは、
- 一番上の桁(左側)は正負の符号とみなす。(0ならプラス、1ならマイナス)
- それ以降の桁は
- プラスの時は、そのまま2進数として読む
- マイナスの時は、「その数と元の数を足すと2進数上で丁度一桁上がる数」として読みます。
……これじゃあワケわからないっすよね？(汗)
実例を出します。
「10進数で-120を2進数表記(2の補数表現)したい」とします。
まず、マイナスなので一番左端は「1」であることが確定です。
次に「120の2の補数」を求める必要があります。
10進数120は1111000です。きっちり1桁上がる数というのは「10000000 ＝ 128」です。
2の補数とはこの場合、「120とその数を足すと、128(=2進数で8桁目)になる数」です。
つまり「8 = 1000」。
なので、120の2の補数は8 = 1000(2進数)となります。
よって、10進数-120の2進数・2の補数表現は「1001000」となります。
……あれ？なんか気が付きませんか？
10進数 120 = 1111000 10進数 8 = 0001000
これって、120の2進数表現を0と1を反転して1を足したのと同じじゃないですか？
10進数 120 = 1111000 1と0を反転 0000111 さらに1を足す 0001000
つまり、2進数に直して、1と0を反転して + 1するとやっても同じなのです。
何で2の補数表現？
多分これを読んで混乱した人が多いと思います。
「何で？」と思う人は多いでしょうが、これは決め事です。
コンピュータの世界での「定理」（物事を成り立たせる為の決め事）なので、覚えるしかないです。
でも、こうしたのには理由があります。
コンピュータは2進数しか理解できません。
「2の補数表現で負の数を表現する」としておくと、足し算だけで引き算を表すことができるのです。
試してみましょう。
例) 10進数134から10進数58を引く
「134 - 58」は「134 + (-58)」と表現できるのは中学校で習ったとおりです。
2進数に直すと、 「10000110 + 11000110」
10000110
+ 11000110
------------
101001100
しかし、一番上は桁あふれなので切り捨てます。 そうすると答えは「01001100 = 76」で、実際の 134 - 58 = 76と同じになります。
つまり、'''2の補数表現で負の数を表すと、足し算だけで引き算を表現することができます。
＝CPU内部に引き算と足し算の回路を共有することができます！
ってことで、そうなっているのだと思います。
ちなみに、10進数でも「10の補数表現」って使えますよ。
これを使うと10進数でも足し算だけで引き算をすることができます。
例) 134 - 58 (10進数編) 58の10の補数表現は42(100 - 58 = 942) 134 + 942 = 1076 ここで、1076の1000は桁あふれなので取り除く。 よって、答えは76。
※nの補数表現が意味を持つのは「限定された同じ桁数同士の数の計算」に限定されます。
ビット演算（論理演算）
2進数が0と1しかないということは、置き換えれば「YesかNoか」だけの世界であるとも言えます。
YesかNoかだけの世界では「論理演算」というものがあります。
基本的なのは4つ。
- NOT
論理を反転させます。
NOT Yes = No NOT No = Yes
- OR
どちらかの論理がYesならYesになります。
主に「ビットを合成したい」ときに使います。
Yes OR Yes = Yes Yes OR No = Yes No OR Yes = Yes No OR No = No
- AND
どちらもYesならYesになります。
主に「ビットにマスクをかけたい」ときに使います。
Yes AND Yes = Yes Yes AND No = No No AND Yes = No No AND No = No
- NOR
NOT + ORの意味を持ちます。
主に、「指定したビットを反転させたい」ときに使います。
Yes NOR Yes = No Yes NOR No = No No NOR Yes = No No NOR No = Yes
論理演算は、2進数の各桁ごとに行われます。
例1）53 AND 28
53 = 110101
28 = 011100
------------
010100 = 20
例2) 53 OR 28
53 = 110101
28 = 011100
------------
111101 = 61
例3) NOT 53
53 = 110101
------------
001010 = 10 ※但し、2の補数表現ではないとする
例4) 53 NOR 63
53 = 110101
63 = 111111
------------
001010 = 10
あれ？
NOT 53の結果と 53 NOR 63は同じ結果ですね。
NORは「ビットの立っている桁を反転させる」という結果になるので、全ビットが立っている状態でNORすると結果的にNOTと同じになります。
2進数での掛け算
10進数の掛け算（割り算）において、10を掛けると桁が1つ左にずれますよね？
例) 12345 × 10 ＝ 123450
実は2進数でも同じ事で、2を掛けると左に1桁ずれます。
逆に2で割ると右に1つずれます。
例) 53 × 2 ＝ 106
110101 × 10 ＝ 1101010 ＝ 106
なので、CPUの中で割り算や掛け算を行う時には、2のべき乗の数で割る時には単にビットをずらすだけでいいことになります。
2進数での足し算
実は2進数の足し算は論理演算だけで行うことが可能です。
論理値Aと論理値Bの2進数足し算は、以下の論理回路で行うことが可能です。
(Sが和、Xが繰り上がりとします。)
S = ((A AND (NOT B)) OR (B AND (NOT A)) X = A AND B
わけがわかりません。検算しましょう。
A = 0, B = 0 の時
S = ((0 AND (NOT 0)) OR (0 AND (NOT 0))
= ( 0 AND 1 ) OR (0 AND 1 )
= 0 OR 0
= 0
X = 0 AND 0
= 0
よって、 0 + 0 = 0 繰り上がり無し
A = 1, B = 0 の時
S = ((1 AND (NOT 0)) OR (0 AND (NOT 1))
= ( 1 AND 1 ) OR (0 AND 0 )
= 1 OR 0
= 1
X = 1 AND 0
= 0
よって、 1 + 0 = 1 繰り上がり無し
A = 1, B = 1 の時
S = ((1 AND (NOT 1)) OR (1 AND (NOT 1))
= ( 1 AND 0 ) OR (1 AND 0 )
= 0 OR 0
= 0
X = 1 AND 1
= 1
よって、 1 + 1 = 0 繰り上がりあり
1桁より大きい足し算をしたい場合は、計算対象のビットをずらして、繰り上がりも足しつつ繰り返せばOKです。
割と簡単でしょ？
ってなわけで、実はCPUの中での「計算」とは、基本的に、
- ビット反転
- 足し算
だけがあればよく、他の演算は全てこれの組み合わせで事足りることになります。
（ただ、これだけでは手数がかかるので、あらかじめこれらを組み合わせた「引き算回路」のようなロジックをあらかじめ作りこんでおくわけですが…。）
結論、CPUは実はビット反転と足し算しかできない！
（正確には「できなくても大丈夫」。）
オマケ
ちなみに、上で紹介した論理回路は「半加算器」と呼ばれます。
なぜ「半」かというと、入力側に下の位からの繰り上がりを受ける口がない為です。
そこで、半加算器に下からの繰り上がりを受け取って加算する機能をつけた「完全加算器」という論理回路があります。
完全加算器は半加算器を2個、ANDとNOTを1つずつ使います。
論理値A,Bと繰り上がり桁Ciの加算演算結果をS、桁上がりをCoとすると、完全加算器の論理式は以下のとおりです。
S = (NOT(NOT(A OR B) OR Ci)) Co = (((A AND B) OR ((NOT(A OR B)) AND Ci)) (本当はNOT-OR(NOR)とかNOT-AND(NAND)を使って書くともうちょっとスッキリします（汗）)
これで2進数一桁同士の足し算ができます。
3桁同士の2進数の足し算論理式は以下のようになります。
- 数値Aを a × 2^2 + b × 2^1 + c × 2^0 (つまり、abcという2進数。)
- 数値Bを d × 2^2 + e × 2^1 + f × 2^0 (つまり、defという2進数。)
- 数値A+Bを w × 2^3 + x × 2^2 + y × 2^1 + z × 2^0 (つまり、wxyzという2進数)
と、した場合、
- 最初の一桁目は下からの繰上りがないので半加算器
z = ((c AND (NOT f)) OR (f AND (NOT c)) q1(繰り上がり1) = (c AND f)
- 2桁目は1桁目の繰り上がりも加えるので完全加算器
y = (NOT(NOT(b OR e) OR q1))
= (NOT(NOT(b OR e) OR (c AND f)))
q2(繰り上がり2) = (((b AND e) OR ((NOT(b OR e)) AND q1))
= (((b AND e) OR ((NOT(b OR e)) AND (c AND f)))
- 3桁目も完全加算器だけど、繰上げはそのままwになる
x = (NOT(NOT(a OR d) OR q2)) = (NOT(NOT(a OR d) OR (((b AND e) OR ((NOT(b OR e)) AND (c AND f))))) w = (((a AND d) OR ((NOT(a OR d)) AND q2)) = (((a AND d) OR ((NOT(a OR d)) AND (((b AND e) OR ((NOT(b OR e)) AND (c AND f)))))
まとめると、
w = (((a AND d) OR ((NOT(a OR d)) AND (((b AND e) OR ((NOT(b OR e)) AND (c AND f))))) x = (NOT(NOT(a OR d) OR (((b AND e) OR ((NOT(b OR e)) AND (c AND f))))) y = (NOT(NOT(b OR e) OR (c AND f))) z = ((c AND (NOT f)) OR (f AND (NOT c))
と、なります。
上記は未確認なので、どなたか何かでプログラムでも組んで確認してみてください(爆)
履歴
2006/02/06 -- 初版
技術的雑談へ戻る