技術資料/情報処理全般

論理演算 †

演算法則 †

知っていると、複雑なif文の条件式を簡潔に記述できることがある。
if節とelse節(またはelse if節)に同じようなコードを記述している場合は、再考すべし。

1. 冪等律

   A || A  ==  A && A  ==  A

2. 交換律

   A || B  ==  B || A
   A && B  ==  B && A

3. 結合律

   (A || B) || C  ==  A || (B || C)
   (A && B) && C  ==  A && (B && C)

4. 吸収律

   (A || B) && A  ==  A
   (A && B) || A  ==  A

5. 分配律

   (A || B) && C  ==  (A && C) || (B && C)
   (A && B) || C  ==  (A || C) && (B || C)

6. 補元律

   (A || !A)  ==  TRUE
   (A && !A)  ==  FALSE

7. ド・モルガンの法則

   !(A && B)  ==  !A || !B
   !(A || B)  ==  !A && !B

8. その他

   A || TRUE   ==  TRUE
   A && TRUE   ==  A
   A || FALSE  ==  A
   A && FALSE  ==  FALSE

真理値について †

ブーリアン型は一般的に TRUE(0以外) と FALSE(0) の整数値で表わされる。
ただし、実際にTRUEの値がいくつに定義されているかに注意する必要がある。

バイトオーダ（エンディアン） †

概要 †

リトルエンディアンによるデータの格納 †

• 組み込み型(char, short, long, int, float, double)
  1バイトずつに区切られ、逆向きにメモリに格納される。
• 配列
  1要素ごとに分けて考える。後は組み込み型の場合と同様。
• 構造体
  メンバ変数ごとに分けて考える。後は配列や組み込み型の場合と同様。

文字コード †

構造体メンバのバウンダリ †

C++のクラス(class, struct)の場合は、仮想関数テーブルへのポインタ変数など自動的に含まれてしまうことがあるため、単純に定義したメンバだけでサイズの計算ができないので注意。
ここではC言語の構造体について述べる。

用語 †

バウンダリ

直訳：境界
バイト境界のこと。通常、2の冪乗のバウンダリが用いられる。

アライメント

直訳：位置揃え
バウンダリに合わせて構造体メンバのメモリ配置を揃えること。

パディング

直訳：詰め物
アライメントを行うために、メンバとメンバの間に挿入される暗黙のデータのこと。

考え方 †

以下の構造体を例として、構造体のメンバ変数の相対位置とサイズを考える。

#pragma pack(4) // コンパイラのオプションとしてアライメントを 4 に設定した場合

struct A{
    char    a;
    short   b;
    long    c;
    double  d;
    char    e;
};

1. メンバ変数のアライメントを決定する。
   下記のうちの小さい方が採用される。配列の場合は1つ分の要素について考えること。
   ・コンパイラのオプションで設定されたアライメント。
   ・そのメンバ変数のサイズ。
   

   項目	サイズ	アライメント
   (struct A 全体)
   char a	1	1
   short b	2	2
   long c	4	4
   double d	8	4
   char e	1	1

2. メンバ変数のためのパディングを挿入する。
   2番目のメンバ変数の相対位置が、その変数のアライメントの倍数になるように直前にパディングを挿入する。
   

   項目	サイズ	アライメント
   (struct A 全体)
   char a	1	1
   パディング	1	-
   short b	2	2
   long c	4	4
   double d	8	4
   char e	1	1

3. 構造体のためのパディングを挿入する。
   構造体自体のアライメントは、メンバ変数のアライメントのうちの最大値となる。
   構造体のサイズがアライメントの倍数になるように、末尾にパディングを挿入する。
   

   項目	サイズ	アライメント
   (struct A 全体)	20	4
   char a	1	1
   パディング	1	-
   short b	2	2
   long c	4	4
   double d	8	4
   char e	1	1
   パディング	3	-

これで、構造体のメンバ変数の相対位置とサイズが決定する。

• 配列や構造体変数が含まれる場合。
  

  struct B{
      char        f;
      short       g[2];
      char        h;
      struct A    i;
  };

  別の構造体のメンバ変数が含まれている場合は、内側の構造体から同様に考えていけばよい。
  

  項目	サイズ	アライメント
  (struct B 全体)	28	4
  char f	1	1
  パディング	1	-
  short g[2]	4	2
  char h	1	1
  パディング	1	-
  strcut A i	20	4

浮動小数点数 †

IEEE 754 †

浮動小数点で一般的に利用されている表現方式。
小数を正規化(「1.xxx * 2^n」の形にすること)して符号、指数部、仮数部に分けて格納する。
代表的なのは、32ビット単精度(single/float)と64ビット倍精度(double)の2種類。

表現できる範囲 †

符号部/指数部/仮数部 †

• 符号部

  ＋なら0、－なら1。

• 指数部

  2を基数として正規化した数「1.xxx… * 2^n」の n を格納する。
  負の数を表現するために、バイアス方式を用いる。単精度なら127、倍精度なら1023を加える。
  2の補数を用いない理由は、浮動小数点同士の比較を単純に行うため。

• 仮数部

  正規化した数「1.xxx… * 2^n」の xxx… の部分を格納する。

• ビットの格納位置

  <32ビット単精度>
   1     8               23            ビット幅
  +-+--------+-----------------------+
  |S|  Exp   |  Fraction             |
  +-+--------+-----------------------+
  31 30    23 22                    0  ビット番号
  
  <64ビット倍精度>
   1     11                                52                          ビット幅
  +-+-----------+----------------------------------------------------+
  |S|  Exp      |  Fraction                                          |
  +-+-----------+----------------------------------------------------+
  63 62       52 51                                                 0  ビット番号
  
  S は符号部、Exp は指数部、Fraction は仮数部

浮動小数点への変換手順（単精度の例） †

1. 符号、指数、仮数に分割していく。
   

   例：「-5.25」

2. 値の正負によって符号を決定。
   

   例：- なので「1」

3. 以降は変換対象の値を絶対値で考える。
   

   例：「5.25」

4. 値を二進数で表現する。
   

   例：「5.25」→「101.01」

5. 正規化を行う。
   

   例：「101.01」→「1.0101 * 2^2」

6. 仮数を左詰めで格納し、足りない部分は 0 を埋める
   

   例：「0101」→「01010000000000000000000」

7. 指数にバイアスを加え、二進数で表現する。
   

   例：「2+127=129」→「10000001」

8. 各部に格納して完成。
   

   例：「1 10000001 01010000000000000000000」→「0xC0A80000」

正規化数以外の表現 †

∞など

float型からdouble型へのキャスト †

符号/指数部/仮数部それぞれ、変換して格納される。

• 符号

  0 か 1 をそのまま格納する。

• 指数部

  バイアスを考慮した変換を行う。（127引いて、1023加える）
  

• 仮数部

  29ビット増えることになるため、0 で埋める。これによって小数点以下7桁目近辺の値にゴミが発生することがある。（最初からdouble型で表現しているときよりもゴミが大きくなるか、同じ値になる）

関数(サブルーチン)コールの仕組み †

引数 †

全て32bitに拡張され、呼出規約に従ってスタックに積まれ、使用後にクリアされる。

戻り値 †

• 戻り値は32bitに拡張され、EAXで返される。(※浮動小数点数は違うらしい)
  
• 32bitより大きい場合は戻り値はいったんどこかにコピーされ、そのアドレスがEAXを使って返される。
  
• 64bitの構造体の場合のみEDX,EAXのペアで返される。

呼出規約(Calling Convention)の種類 †

• 可変引数リストは呼び出し側でスタックのクリアを行う規約でしか使用できない。呼び出された側ではいくつ引数がスタックに積まれるか分からず、スタッククリアのコードを作れないためと思われる。
• 速度重視や他の言語と連携するDLL等はstdcall、可変引数リスト使用時はcdeclのように使い分ける。（プログラマが意識しなくても、可変引数リストを使用した関数は自動的にcdeclとしてコンパイルされる）
• fastcallは現在あまり使用されない。
• 他に、pascal、fortran、syscallといった呼出規約が存在するが、現在は使用されない。

ソート †

安定ソートと非安定ソート †

一致するデータが存在する場合のソート結果が定まっているものを安定ソート、未定義のものを非安定ソートと呼ぶ。
バブルソートは安定ソート、クイックソートは非安定ソートである。
非安定ソートであっても、比較処理を工夫することで安定化できる場合がある。（各データにユニークな値が必要）

比較処理の例

• Ａの身長＞Ｂの身長：1を返す
• Ａの身長＜Ｂの身長：-1を返す
• Ａの身長＝Ｂの身長
  • Ａの社員番号＞Ｂの社員番号：1を返す
  • Ａの社員番号＜Ｂの社員番号：-1を返す
  • Ａの身長＝Ｂの身長はありえない