● 講義・実習・課題提出に関する重要な注意
• 必ずしも多くはないが, 講義に遅刻してくる学生がいるが,出席カードを回収した後（９時頃）に来 た学生に関しては「出席した」とはみなさい. 実習に関しても同様である.
• 実習は「提出課題のみを行う」場ではない. 実習資料の内容を理解し,それらを順に行うことが必要 である.
• 提出された課題の回答が不十分なもの,または,提出された課題が不足しているものに関しては,課題 を提出したとはみなさない.
● 先週の授業のキーポイント
【整数の計算機内部での表現】
• 計算機内部では,全てのデータは「ビットの列」として表現される. そのビット列が「どのよう なデータ」をあらわしているかを判断するために,プログラム中では「値」に対して「型」を定 めている.
• 「整数」のデータの「ビット列」は「2 進表現」であらわされている. ある「整数」をあわら す型のビット数がN であるとき,「ビット列」と値との対応は以下のようになっていることが 多い.
・ 符号なし整数 ビット列が(aN−1 aN−2 . . . a1 a0)であるとき,対応する数値は
N−1
k=0 ak2k である.
・ 符号つき整数 ビット列が(aN−1 aN−2 . . . a1 a0)であるとき,対応する数値は
−aN−12N−1+N−2
k=0 ak2k である. これを「2 の補数による表現」と呼ぶ. この場合,最上 位ビットaN−1が 0の時には非負であり, 1の時には負であることから,最上位ビットを符 号ビットと呼ぶ.
• ビット列が(aN−1 aN−2 . . . a1 a0)であり,それがあらわす数値がnであるとき,nの1 の補数nとはビット列(1−aN−1 1−aN−2 . . . 1−a1 1−a0)があらわす数値のことで ある.
• 考えている数の体系が k ビットであるとき, 0 ≤n <2k をみたす整数 n の2 の補数 n˜ とは n˜= 2k−nのことである.
• 1 の補数と2 の補数の間には, ˜n=n+ 1なる関係がある.
• 「2の補数による表現」を用いた負の数の表現は, 0≤n <2N−1 に対して, −nを n˜ があらわ すビット列で表現したものに他ならない.
【文字コードと文字型オブジェクト】
• 計算機内部では「文字」は「数値」に置き換えてデータとして格納している. この「置き換えの ルール」,すなわち,どの文字をどのような数値としてあらわすか,または,数値を文字として考 えたとき,各数値がどの文字をあらわすかを決めたルールを「文字コード体系」と呼ぶ.
• 日本語文字などを含まない,計算機における基本文字集合の文字コード体系のひとつにASCII コードがある. 現在利用されている計算機の多くはASCII コード体系を用いている.
• 基本文字集合のコード体系を用いることにより,「文字」を「整数値」と考えることができる. この意味で「文字型のオブジェクト」は「整数」とみなすことができる.
【汎整数型オブジェクト】
• Cにおいて「整数」とみなされる型には以下のものがある.
・ 符号つき型 short,int,long
それぞれが定めるオブジェクトのバイト数には
1 =sizeof(signed char)≤sizeof(short)≤sizeof(int)≤sizeof(long), intのビット数≥16, longのビット数≥32
というルールのみが定められている.
・ 符号なし整数 unsigned char,unsigned short,unsigned int,unsigned long それぞれが定めるオブジェクトのバイト数には
1 =sizeof(unsigned char)≤sizeof(unsigned short)≤sizeof(unsigned int)
≤sizeof(unsigned long),
unsigned int のビット数≥16, unsigned longのビット数≥32 というルールのみが定められている.
charはsigned charまたはunsigned charのいずれか. （これは処理系によって異なる.）
• 「符号なし整数」の算術演算は,N をその型のビット数とした時, 2N を法とした演算が保証さ れる. しかし,「符号付き整数」の算術演算で桁あふれが生じた場合の演算結果は処理系依存で ある.
● 講義資料
★ Ｃの演算子
詳しくはK&Rの「付録Ａ」を参照のこと.
優先順位１ （左結合）
() 優先順位を変更する括弧 [] 配列参照演算子† -> アドレス演算子† . 間接演算子† 優先順位２ （右結合）
! 論理否定演算子
~ １の補数演算子
++, -- インクリメント演算子 +, - 単項プラス・マイナス演算子
& ポインタ参照演算子†
(type) キャスト（型変換）演算子
sizeof sizeof演算子 優先順位３ （左結合）
*, /,% 乗法演算子 優先順位４ （左結合）
+, - 加法演算子 優先順位５ （左結合）
>>,<< シフト演算子 優先順位６ （左結合）
>, <,>=,<= 比較演算子 優先順位７ （左結合）
==, != 等置演算子 優先順位８ （左結合）
& ビットAND演算子 優先順位９ （左結合）
^ ビットXOR演算子 優先順位１０ （左結合）
| ビットOR演算子
優先順位１１ （左結合）
&& 論理AND演算子 優先順位１１ （左結合）
|| 論理OR演算子
優先順位１２ （左結合）
?: 条件演算子‡ 優先順位１３ （右結合）
=
+=,-=, *=,/=,%=
&=,~=, ^=
<<=,>>= 代入演算子 優先順位１４ （左結合）
, コンマ演算子‡
【注意】
• この中で †がついているものは講義の後半で解説する.
• この中で ‡がついているものは講義では特に解説しないので,各自で調べておくこと.
• それ以外のものは今回及び次回で解説する.
演算子の優先順位(cf. K&R p. 65)
演算子 結合規則
() [] -> . ⇒
! ~ ++ -- +（単項） -（単項） & (type) sizeof ⇐
* / % ⇒
+ - ⇒
>> << ⇒
> < <= >= ⇒
== != ⇒
& ⇒
^ ⇒
| ⇒
&& ⇒
|| ⇒
?: ⇐
= += -= *= /= %= &= |= ^= <<= >>= ⇒
, ⇒
• よくある間違い：“i&1 == 0”
これは “(i&1) == 0”のつもりで書くことが多いが, “i&(1 == 0)”と解釈される.
“i&1 == 0”の値は常に0となるのでバグに気が付くが, “i&1 == 1” は“(i&1) == 1”と結果が同 じになるので間違いに気が付かない.
★ 算術演算を行う場合の変換
詳しくはK&Rの「付録Ａ」を参照のこと.
▼ 整数への格上げ
char,shortは,符号つきも符号なしも,整数が使える式で使ってよい. この時,元の型の全ての値がint で表現できる時には, その値は intに変換される. int で表現できない時には unsigned int に変換さ れる.
▼ 汎整数型の間の変換
汎整数型をもつ値を他の汎整数型に変換する場合には, 以下の規則が用いられる. 1. 値が新しい型で表現可能ならば,その値は変化しない.
2. 符号付き整数を,それと等しいか,より多いビット数の符号なし型に変換する場合, (a) その符号付きの整数が正ならば値は変化しない.
(b) そうでない場合, 符号なしの整数のビット数が大きいならば,符号付きの整数は,その符号なし 整数と同じ大きさの符号付き整数にまず拡張する. それから,符号なし整数型で表現しうる最大 の数に1 を加えた数を加えることによって符号なし整数に変換する.
3. 汎整数型をもつ値をより少ないビット数の符号なし整数に変換する場合,変換後の値は, その少ない ビット数の型で表現しうる最大の符号なし数より 1だけ大きな数で割った余りとする.
4. 汎整数型をもつ値をより少ないビット数の符号付き整数に変換するか,符号なし整数を同じビット数 の符号付き整数に変換する場合,変換後の値を表現できないならば,その値は処理系定義.
▼ 算術変換
1. いずれかの被演算数がlong doubleならば,他もlong doubleにする.
2. いずれかの被演算数がdoubleならば, 他もdoubleにする.
3. いずれかの被演算数がfloatならば, 他もfloatにする.
4. 上のいずれも一致しない時には,整数への格上げを行なって,以下の変換を行なう. (a) いずれかの被演算数がunsigned longならば,他もunsigned longにする. (b) いずれかの被演算数がlongで,他がunsigned intである時には,次を調べる.
i. longがunsigned intの全ての数を表現できれば,unsigned intの被演算数はlong int にする.
ii. そうでない時には,全ての被演算数はunsigned longに変換される. (c) いずれかの被演算数がlongならば, 他もlongにする.
(d) いずれかの被演算数がunsigned intならば,他もunsigned intにする. (e) 上のいずれかも当てはまらない時には,被演算数をintとして計算する.
● 実習内容
【Ｃ言語】
1. 以下のex05-1.cを入力してコンパイルおよび実行を行ってみよう.
これは unsigned int型の値の偶奇を判定しているものだが, int型の値に関しても同じ条件
判断式を使うことができるかどうかを考えてみよう.
2. 以下のex05-2.cを入力してコンパイルおよび実行を行ってみよう.
このプログラムは算術変換が行われている例である.
3. 以下のex05-3.cを入力してコンパイルおよび実行を行ってみよう.
このプログラムは各種の演算を行った結果の値を表示している.
4. 以下のex05-4.cを入力してコンパイルおよび実行を行ってみよう.
このプログラムは「論理演算」を行っているが,必ずしも正しい結果を出力しているわけではな い. それがなぜかを考えてみよう.
電子メールで「今日の講義の感想や意見」を送ってください.
★
ex05-1.c
の内容
/* $Id: ex05-1.c,v 1.2 2005-05-17 10:01:19+09 naito Exp $ */
#include <stdio.h>
int main(int argc, char **argv) {
unsigned int n=10 ;
if (n&1) printf("n = %u is odd\n", n) ; else printf("n = %u is even.\n", n) ; return 0 ;
}
★
ex05-2.c
の内容
/* $Id: ex05-2.c,v 1.3 2005-05-17 12:47:34+09 naito Exp $ */
#include <stdio.h>
int main(int argc, char **argv) {
int i,j ;
double x,y,z ;
i = 3 ; j = 2 ; x = 3.0 ; y = 2.0 ; z = i/j ; printf("%f\n", z) ; z = (double)i/j ; printf("%f\n", z) ; z = i/(double) j ; printf("%f\n", z) ; z = (double)(i/j) ; printf("%f\n", z) ; z = x/j ; printf("%f\n", z) ; z = i/y ; printf("%f\n", z) ; z = x/y ; printf("%f\n", z) ; return 0 ;
}
★
ex05-3.c
の内容
/* $Id: ex05-3.c,v 1.3 2005-05-18 13:06:25+09 naito Exp $ */
#include <stdio.h>
int main(int argc, char **argv) {
int i=1,j,k ;
printf("%d\n", k=j=i) ; printf("%d\n", k+=1) ;
/* printf("%d\n", i=k,k=j) ; */
i = 1 ;
printf("%d\n", i++) ; j = 1 ;
printf("%d\n", --j) ; printf("%d\n", j?!0:0) ; return 0 ;
}
修正あり. コメントになっている１行を削除.
★
ex05-4.c
の内容
/* $Id: ex05-4.c,v 1.3 2005-05-18 13:06:47+09 naito Exp $ */
#include <stdio.h>
int main(int argc, char **argv) {
int n, n2, n3 ; int k2, k3 ;
for(n=0;n<10;n++) { printf("n = %d\n", n) ;
n2 = n3 = k2 = k3 = -1 ;
if ((n%2 == 0)&&(n%3 == 0)) printf("n は 6 の倍数\n") ;
else if (n%2 == 0) printf("n は 2 の倍数だが 3 の倍数ではない\n") ; else if (n%3 == 0) printf("n は 3 の倍数だが 2 の倍数ではない\n") ; else printf("n は 2 の倍数でも 3 の倍数でもない\n") ;
/* if ((n&2 == 0)&&(n%3 == 0)) printf("n は 6 の倍数\n") ; */
/* else if (n&2 == 0) printf("n は 2 の倍数だが 3 の倍数ではない\n") ; */
if ((n&1 == 0)&&(n%3 == 0)) printf("n は 6 の倍数\n") ;
else if (n&1 == 0) printf("n は 2 の倍数だが 3 の倍数ではない\n") ; else if (n%3 == 0) printf("n は 3 の倍数だが 2 の倍数ではない\n") ; else printf("n は 2 の倍数でも 3 の倍数でもない\n") ;
k2 = n%2 ; k3 = n%3 ;
if ((k2 == 0)&&(k3 == 0)) printf("n は 6 の倍数\n") ;
else if (k2 == 0) printf("n は 2 の倍数だが 3 の倍数ではない\n") ; else if (k3 == 0) printf("n は 3 の倍数だが 2 の倍数ではない\n") ; else printf("n は 2 の倍数でも 3 の倍数でもない\n") ;
if (((n2 = n%2) == 0)&&((n3 = n%3) == 0)) printf("n は 6 の倍数\n") ; else if (n2 == 0) printf("n は 2 の倍数だが 3 の倍数ではない\n") ; else if (n3 == 0) printf("n は 3 の倍数だが 2 の倍数ではない\n") ; else printf("n は 2 の倍数でも 3 の倍数でもない\n") ;
}
return 0 ; }
修正あり. コメントになっている２行を次の２行に修正.
【課題】
★ exercise-05-1 与えられた非負整数の2進表示を,逆順で出力するプログラムを書きなさい.「逆
順」とは,例えば対象の非負整数が14 = (1110)2であるとき,0111と出力することを意味する.
★ exercise-05-2 与えられた整数の2進表示を,逆順で出力するプログラムを書きなさい. このプ
ログラムではunsigned int 型のオブジェクトが32ビットであること,負の整数は 2 の補数 で表現されていることを仮定してよい.
★ exercise-05-3 ２つのint型のオブジェクトの値の積の値を,次の式を利用して,加減算とビッ
ト演算のみで求めるプログラムを書きなさい.
b=−2N−1bN−1+ 2N−2bN−2+· · ·+ 2b1+b0
= 2N−1(bN−2−bN−1) + 2N−2(bN−3−bN−2) +· · ·+ 2(b0−b1)−b0.
このプログラムに関しては「桁あふれ」を考慮する必要はない. また,このプログラムではint 型のオブジェクトが 32ビットであることを仮定してよい.
★ exercise-05-4 ２つのunsigned int型のオブジェクト a,bに対して,a/bの値（この場合は
「商」となる）と剰余を,加減算とビット演算のみで求めるプログラムを書きなさい. このプロ グラムではunsigned int型とint型のオブジェクトが32ビットであることを仮定してよい. また,除数bは0x10000未満（16ビット以内）であることを仮定する.
● 前回の課題の解答例
★ exercise-04-3 標準入力から文字を読み,その文字が「アルファベット」（すなわち,AからZまたは
aからz）であれば,それを１３文字後ろにずらしたアルファベットを出力し,「アルファベット」以
外の文字であれば, その文字をそのまま出力するプログラムを書きなさい. 例えば, “XYZ”を１文字 後ろにずらすとは “YZA” とすることである. “A quick brown fox jumps over the lazy dog.” を１３文字後ろにずらすと“N dhvpx oebja sbk whzcf bire gur ynml qbt.” となる. このプロ グラムは文字コード体系が ASCIIであることを仮定してよい.
★ 方針 入力された文字が「英大文字」または「英小文字」の場合にのみ１３文字をずらす操作を 行い, 文字を出力すればよい. 文字コードが ASCII 体系と仮定されているため, A から Z, a から z はそれぞれ連続した文字コードを持つことを利用すれば, １３文字ずらす操作はc = (c-’A’+13)%(’Z’-’A’+ 1)+ A’またはc = (c-’a’+ 13)%(’z’-’a’+1)+’a’で実現できる.
★ 解答例 上の方針を使えば,解答例としては次のプログラムになる.
/* ROT13 */
/* $Id: exer-04-3.c,v 1.1 2005-05-16 16:06:03+09 naito Exp $ */
#include <stdio.h>
int main(int argc, char **argv) {
int c ;
while((c = getchar()) != EOF) { if ((c >= ’A’)&&(c <= ’Z’)) {
c = (c - ’A’ + 13)%(’Z’ - ’A’ + 1) + ’A’ ; }
else if ((c >= ’a’)&&(c <= ’z’)) {
c = (c - ’a’ + 13)%(’z’ - ’a’ + 1) + ’a’ ; }
printf("%c", c) ; }
return 0 ; }
ここで,(c - ’A’ + 13)および(c - ’a’ + 13)はそれぞれのif節の中では,途中の計算が 負にならないことは保証できる.
★ 提出されたプログラムに対するコメント 全体に非常にわかりにくいプログラムが多い.
• ’A’の文字コード値 0x41と書くことは,必ずしもわかりやすいプログラムにはならない. ましてや10進数値65と書いたら,何をしているプログラムかわからなくなるだろう.
• ((c >= ’A’ && c <= ’M’) || (c >= ’a’ && c <= ’m’)) という条件式（または類似 のもの）を使っているものも多く見られた. これは１３文字ずらすことを考えているのだ と思われるが,問題が「１８文字ずらす」と変更されたときにどう対処するのかを考えてみ よう.
★ exercise-04-4 ２つのunsigned int型のオブジェクトの値の積の値を,加算とビット演算のみで求
めるプログラムを書きなさい. このプログラムに関しては「桁あふれ」を考慮する必要はない.
★ 方針 非常に簡単な問題であるが, 初心者には難しいかもしれない. 小学生の頃を思い出して, 10 進数値の掛け算を「筆算」でやってみよう.
1 2 1
* 1 2
2 4 2
1 2 1
1 4 5 3
この計算をよくみてみると次の操作を行っている.
1. 乗数12の1桁目の 2を取出し,それと被乗数121を掛ける.
2. 乗数12の2桁目の 1を取出し,それと被乗数を一桁ずらした数値1210を掛ける. 3. それらの値を加える.
これを2 進で考えれば,
1 1 1 1 0 0 1
* 1 1 0 0
1 1 1 1 0 0 1
1 1 1 1 0 0 1
1 0 1 1 0 1 0 1 1 0 0
となる. したがって,
1. 乗数1100の 1桁目の0を取出し,それと被乗数11110001を掛ける.
2. 乗数1100の2桁目の0を取出し,それと被乗数を一桁ずらした数値111100010を掛ける. 3. 乗数 1100 の 3 桁目の1 を取出し, それと被乗数を一桁ずらした数値 1111000100 を掛
ける.
4. 乗数1100の 4 桁目の 1 を取出し, それと被乗数を一桁ずらした数値 11110001000を掛 ける.
5. それらの値を加える.
ところが2 進で考えていることを使うと「乗数の考えている桁が0 なら何もせず,1なら被乗 数をずらした数値を「積」の値の変数に加える」ことで十分であることがわかる. また,乗数の 考えている桁を見るためには,「乗数を一桁づつ右にずらた時の一桁目」を見ればよいことがわ かる.
これらをまとめると次のようにすればよい. 1. 「積」の値を格納する変数を0で初期化する. 2. 乗数が0でない限り,次を繰り返す.
(a) 乗数の一桁目が1ならば,被乗数を「積」に加える. (b) 乗数を一桁右にずらす.
(c) 被乗数を一桁左にずらす.
3. 終了時には「積」の値は「乗数と被乗数の積」に等しい.
★ 解答例 上の方針を使えば, 解答例としては次のプログラムになる. これら２つのプログラムは
while文を使うか,for文を使うかの差異しかないが,while文を使ったものの方が標準的だと
思われる.
/* $Id: exer-04-4-1.c,v 1.1 2005-05-11 19:29:24+09 naito Exp $ */
#include <stdio.h>
int main(int argc, char **argv) {
unsigned int i, j, m ;
i = 100 ; j = 200 ; m = 0 ; while(i != 0) {
if ((i&1) == 1) m += j ; j <<= 1 ; i >>= 1 ; }
printf ("%u\n", m) ; return 0 ;
}
/* $Id: exer-04-4-2.c,v 1.1 2005-05-11 19:30:30+09 naito Exp $ */
#include <stdio.h>
int main(int argc, char **argv) {
unsigned int i, j, m ;
i = 100 ; j = 200 ;
for(m=0;i!=0;j<<=1,i>>=1) { if ((i&1) == 1) m += j ; }
printf ("%u\n", m) ; return 0 ;
}
上記のプログラム中で i >>= 1は i = i>>1,j <<= 1は j = j<<1と等価である. その気に なれば,もっと短く書くことも可能であるが,必ずしもわかりやすいものにはならない可能性が ある.
★ 提出されたプログラムに対するコメント いろいろと苦労のあとが見えるプログラムが多く見ら れた.
• 繰り返し回数をカウントして,その分だけシフトを行っているプログラムが非常に多かった. 例えば,
while((i>>n) != 0){
if((i>>n)&1 ==1){
k+=(j<<n);
} n+=1;
}
のようなものである.
• unsigned int型のオブジェクトのビット数を利用しているものも多かった.
少なくとも乗算に関しては, ビット数の情報は必要ない. なぜなら,unsigned int 型の値 を順に右シフトしていけば,いつかは0になるからである.
