Powered by SmartDoc

計算機科学入門

Sat May 03 15:24:35 JST 2003
渡辺隆行
nabe@lab.twcu.ac.jp
http://www.twcu.ac.jp/~nabe/lec/

目次

1 参考文献

「情報科学の基礎知識」、宮内ミナミ、森本喜一郎共著、昭晃堂。

2 2進数入門

2.1 なぜ2進数が必要か

人間は10進数で物を数えます。10のかたまりが2つと半端が7つある数のことを27と書き、2(に)じゅう7(なな)と読みます。10の塊で物を数える方法を10進数といいます。

コンピュータは10本の指を持っていないので、ほかの方法で数を数えます。現代のコンピュータは電気で動いていますから、電気ONの状態を1、電気OFFの状態を0として、ONとOFF2つの状態で数を数えます。これが2進数です。

下表に10進と2進の数の対応表を示しますが、ご覧のとおり2進数はすぐに桁が多くなってしまいますし、とても読みにくいです。そこで10に近い2のべき乗として、8進数や(8は2の3乗です)や16進数を使うことが多いです。16進数の場合、9より1個多い数を表す数字がないので、アルファベットのAを使います。BからFも同様です。ですから16進数で2Fと書いてあったら、これは16の塊が2つと半端がF、つまり15、のことですから、10進数で言うと47になります。

10進数と2進数の変換は少しややこしいですが、2進数と8進数と16進数を相互変換するのはとても簡単です。以下の章で詳しく説明します。

表 2.1.1 10進数と2進数と8進数と16進数の比較
10進数 2進数 8進数 16進数
0 0 0 0
1 1 1 1
2 10 2 2
3 11 3 3
4 100 4 4
5 101 5 5
6 110 6 6
7 111 7 7
8 1000 10 8
9 1001 11 9
10 1010 12 A
11 1011 13 B
12 1100 14 C
13 1101 15 D
14 1110 16 E
15 1111 17 F
16 1 0000 20 10
17 1 0001 21 11
18 1 0010 22 12

2.2 10進数と2進数

234という数字を私たちは「2百3十4」と声に出して読みます。つまり

234 = (2 x 100) + (3 x 10) + 4

というわけです。

ところで100は10の2乗で、10は10の1乗です。また1は10の0乗ですから、先ほどの式は

234 = (2 x 102) + (3 x 101) + (4 x 100)

と書けます。これが10進数の書き方です。つまり、10の塊(100、101、102、...)ごとに分割して数を数えています。

2進数の場合は10の代わりに2の塊で数を数えます。

(101)2

という書き方で、2進数の101を表すことにします。これは、

(101)2 = (1 x 22) + (0 x 21) + (1 x 20)

のことです。つまり、2進数の一番右側の桁(0番目の桁)には20の重みがかかり、その左の桁(1番目の桁)には21の重みがかかります。一般的にn番目の桁には2nの重みがかかります。一番右の桁を0番目と呼ぶことに注意してください。

2.3 2進数を10進数に変換する

2進数を10進数に直すのは簡単です。

2.3.1 正攻法

(101)2 = (1 x 22) + (0 x 21) + (1 x 20) = (1 x 4) + (0 x 2) + (1 x 1) = (5)10

となって、2進数の101は10進数で言うと5であることがわかります。

あるいは

(1010)2 = (1 x 23) + (0 x 22) + (1 x 21) + (0 x 20) = (1 x 8) + (0 x 4) + (1 x 2) + (0 x 1) = (10)10

です。

2.3.2 簡単な方法

実はもっと簡単に求める方法があります.

(101)2

を例にあげて説明します.左端(上位ビット)から右端(下位ビット)に向けて作業します.

  1. 左端の1を2倍して,その右隣のビット(0)と足すと,2になる.
  2. この2を2倍して,その右隣のビット(1)と足すと,5になる.
  3. これでおしまい.答えは5.

(1010)2

だったら,

  1. 左端の1を2倍して,その右隣のビット(0)と足すと,2になる.
  2. この2を2倍して,その右隣のビット(1)と足すと,5になる.
  3. この5を2倍して,その右隣のビット(0)と足すと,10になる.
  4. これでおしまい.答えは10.

もう少し例をあげます.

(11001101)2

だったら,

  1. 左端の1を2倍してその右隣のビット(1)と足して3.
  2. この3を2倍してその右隣のビット(0)と足して6.
  3. この6を2倍してその右隣のビット(0)と足して12.
  4. この12を2倍してその右隣のビット(1)と足して25.
  5. この25を2倍してその右隣のビット(1)と足して51.
  6. この51を2倍してその右隣のビット(0)と足して102.
  7. この102を2倍してその右隣のビット(1)と足して205.
  8. これでおしまい.答えは205.

2.4 10進数を2進数に変換する

10進数を2進数に変換するときはどんどん2で割っていきます。たとえば10進数の11を2進数に変換するときは、

このように、2で割った余りを書いていきます。最後に商が0になったら終わりです。そして求めた余りのリストを下から順番に並べます。今の場合なら(1011)です。これで2進数に変換できました。つまり

(11)10 = (1011)2

です。

2.5 ビットとバイト

2進数の一桁のことをビット(bit)といいます。1bitのデータは,何かがあるかないか(あれば1,なければ0)という情報を表すことができます.また8ビットまとめて1バイト(byte)といいます。たとえば2バイトとは16ビットのことで、16桁の2進数です。次節に示すように,アルファベットや数字などの英文タイプライターにあるような文字は1バイトで表すことができます.

これより大きな単位にワード(word)がありますが、ワードが何バイトかはコンピュータによって異なります。

また、重さを量るときに1000グラム(g)のことを1キログラム(kg)といいますが、コンピュータの世界にもキロ(K)やメガ(M)という数え方があります。ただし1キロバイト(KB)は1000バイトではなくて1024バイトになります。なぜ1024などという変な数を使うかというと、210 = 1024だからです。(1KB=1000バイトとなることもありますが,詳細は省略します.)

2.6 8進数と16進数

2進数は10進数よりも桁が長くなり、1と0だけで読みにくいので、8進数や16進数であらわすことが多いです。なぜ8や16かというと、8は2の3乗で16は2の4乗だからです。

2進数を8進数に変換するのは簡単で、2進数の下の桁から3ビットずつをまとめて、それぞれを10進数に変換し、そのまま左側から並べます。

8進数を2進数に変換するときは8進数の各桁を3ビットの2進数に変換し、順に並べるだけです。8進数の一桁は必ず3ビットの2進数に直してください。数が4より小さいときは左側に0を補って3ビットにします。

16進数のときも同じです。今度は4ビットが単位になります。ただし16進数のときは9を超えた数を数えるときに特殊な文字を使います。すなわち、

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F

のように数を数えます。なぜ10の代わりにAを使うかというと、10と書くと (10)16 = (16)10と見分けがつかないからです。

8進数と16進数の変換は間に2進数を入れると簡単にできます。

2.7 練習問題

  1. (11001101)2を10進数に変換する。
  2. (486)10を2進数に変換する。
  3. (110100)2を8進数、10進数、16進数に変換する。
  4. (1A3C)16を2進数、8進数、10進数に変換する。

3 文字コード入門

3.1 文字の表現

コンピュータはどのようにして文字を扱っているのでしょうか?一つ一つの文字に対して2進数の数字が割り当てられてるのです。英文タイプライターにあるような文字や記号には世界共通の決まりがあって、ASCII (American Standard Code for Information Interchange)コードと呼ばれています。英文タイプや英語キーボードには、アルファベットが大文字と小文字あわせて52種類、数字が0から9までの10種類、その他の記号が30種類くらい、合計100種類くらいあります。2の7乗は128なので、7桁(7ビット)の2進数でこれらの文字すべてを表すことができます。

たとえば大文字Aは2進数で(100 0001)、小文字のaは(110 0001)です。数字の0は(011 0000)となります。コンピュータにAという文字が送られたら、この文字はコンピュータの中では、(0100 0001)という2進数で表されているのです。

2進数で書くと桁が長くなって扱いにくいので、16進数で書くことにします。すると、大文字Aは16進数の(41)。小文字aは(61)、数字の0は(30)と書くことができます。ではほかの英数字や記号はどの16進数に対応しているのでしょうか?それを示したのが以下に示すASCIIコードの表です。この表は2桁の16進数の上位の桁が横方向に、下位の桁が縦方向に展開されています。たとえば16進数の(41)に対応する文字を知りたかったら、横方向は4、縦方向は1の見出しに対応するマスを探してください。そこにはAと書いてあるはずです。逆に小文字のaの文字コードを知りたかったら、aと書いてあるマスの横の見出し、すなわち6、と縦の見出し、すなわち1、を組み合わせて、(61)となります。

表 3.1.1 ASCIIコード
0 1 2 3 4 5 6 7
0 NULL 空白(SP) 0 @ P ` p
1 ! 1 A Q a q
2 " 2 B R b r
3 # 3 C S c s
4 $ 4 D T d t
5 % 5 E U e u
6 & 6 F V f v
7 警告(BEL) ' 7 G W g w
8 後退(BS) ( 8 H X h x
9 水平タブ ) 9 I Y i y
A 改行(LF) * : J Z j z
B 垂直タブ + ; K [ k {
C 書式送り , < L \ l |
D 復帰(CR) - = M ] m }
E . > N ^ n ~
F / ? O _ o (DEL)

この表の左2列には見慣れない文字が並んでいます。重要なものだけ説明します。

3.2 日本語の表現

3.2.1 文字コードと文字化け

電子メールやWWWを使ったことがある人は、「文字化け」という言葉を聞いたことがあるかもしれません。ここでは文字コードと文字化けの関係について説明します。

前述したように,数字やアルファベットやタイプライターにあるような記号はASCIIコードで2進数に変換します。このASCIIコードは日本を含む世界中で使われているので、数字やアルファベットが文字化けすることはありません。

問題は日本語です。日本語には何千種類もの漢字がありますが、どの漢字をどの2進数で表現するかというルールが何種類もあるのです。

JISコード(ISO-2022-JP)
7ビット2つで一文字の日本語を表現する方法。8ビット目を使わないため、インターネットでの利用に適しており、電子メールの日本語はこのJISコードで送信される。WebページもJISコードで表現するのが望ましいと言われている。
シフトJIS (Shift_JIS)
2バイト(つまり16ビット)で一文字の日本語を表現する方法。Microsoft社のWindows(やApple社のMacintosh)で使われている。パソコンでのデフォルト方法といってよいが、円記号(\)と重複しているなどの問題点もある。
日本語EUC (EUC-JP)
2バイト(つまり16ビット)で一文字の日本語を表現する方法。UNIX系OSで使われる。シフトJISの改良版といってもよい。
Unicodeで使われる方法
UTF-8などの方法では、日本語1文字に3バイト使用する。世界中の文字を統一的に表現しようというのがUnicode。将来はこの方式が主流になると思われる。2003年度後半から情報教育で使用するMac OS XもUnicode(UTF-8)を使用する.

同じ漢字に対応する2進数が何種類もあるのが、文字化けの原因です。たとえばWindowsパソコンで作成した日本語の文章をUnixで表示させると、まったく意味不明の文字の羅列になってしまい読めません。これはシフトJISで2進数に変換した日本語を日本語EUCのルールで日本語に戻そうとしたために文字の対応がずれてしまったのです。またシフトJISと日本語EUCは似ているので、Webブラウザーなどがデータの文字コードの判断を誤ってしまい、文字化けして表示されることもあります。実はある文字コードから別の文字コードに変換するのは簡単なので、このような文字化けが起きても、nkfなどのソフトウェアで正しい文字コードに変換することができます。

Emacsのように,データの文字コードのパターンを手がかりに使用されている文字コードを判別して,文字化けなく画面に表示できるアプリケーションもあります.IEやNetscapeなどのWebブラウザも,この機能を持っています.またHTMLやXMLなどのデータ記述方式では,データに使われている文字コードを明示する機能もあります.

4 論理演算

4.1 真理値表

表 4.1.1 真理値表
条件1 条件2 条件1 &&条件2 (論理積AND) 条件1 ||条件2 (論理和OR)
(1)
(2)
(3)
(4)
図 4.1.1 集合

4.2 論理演算の例