整数の内部表現

Asir では任意桁数の整数 (いわゆる bignum) を扱うことができるが, CPU が直接扱えるのは32 bit (2 進数 32桁) または 64 bit (2 進数 64 桁) というある決まった大き さ (1 ワードと呼ぶことにする) の整数で, それより大きな整数を扱うにはソ フトウェアの手助けが必要となる. Asir においては, 大きな整数(多倍長整数) は, ワードを単位とする配列として表現される. 1 ワードが 32 bit = 4 byte とするとき, 自然数 $a$ は次のように表現される. まず, $a$ の $2^{32}$ 進表示を考える.

$$a = a_0 2^0 + a_1 2^1 + a_2 2^2 + \cdots + a_{N-1} 2^{N-1}\quad (0 \le a_i \le 2^{32}-1, a_{N-1} \neq 0)$$

これに対し, 長さ $N$ のワード配列 $w$, すなわち, 長さが $4N$ byte のメモリ上の連続領域を確保して,

$$w[i] = a_i \quad (0 \le i \le N-1)$$

とする. これで自然数が表現できる. 実際には, Asir においては, 長さ $N+1$ のワード配列を確保し, 先頭に長さ $N$ が書かれ, 残りに $2^{32}$ 進表示の各桁が書かれる.

1 ワードを構成する複数の byte がどういう順序でメモリに書かれているか は CPU に依存する. 下位 byte が下位アドレスに書かれる場合 little endian, 下位 byte が上位アドレスに書かれる場合 big endian と呼ばれる. Intel 80386 系 CPU は little endian であり, たとえば

$$987654321 = {\tt0x3a} \cdot (2^8)^3 + {\tt0xde} \cdot (2^8)^2 + {\tt0x68} \cdot (2^8)^1 + {\tt0xb1} \cdot (2^8)^0$$

は, アドレスの下位から上位に向かい b1 68 de 3a と並ぶ.