16ビット整数の乗算・除算
Z80 では乗算・除算の命令がないため、処理を書く必要があります。この処理を C++ で説明します。16ビット整数の乗算・除算を C++ で書くと以下のようになります。レジスターを節約するため引数と結果をまとめて 16 ビットで表しやすい方法考えます。そのため複数の方法を考えます。
乗算
以下の multiply1 または multiply2 のようになります。bitsize は 16、x、y は 16 ビットの符号なし整数、int は 32 ビット以上あるとします。
int multiply1(int x, int y, int bitsize) { int result = 0; for (int i = 0; i < bitsize; i++) { if (y & 1) { result += x; } x <<= 1; y >>= 1; } return result; }
int multiply2(int x, int y, int bitsize) { int c = 1 << bitsize; int result = 0; for (int i = 0; i < bitsize; i++) { y <<= 1; result <<= 1; if (y & c) { result += x; } } return result; }
除算
以下の divide1 または divide2 のようになります。bitsize は 16、x、y は 16 ビットの符号なし整数、int は 32 ビット以上あるとします。
int divide1(int x, int y, int bitsize) { int result = 0; y <<= bitsize; for (int i = 0; i < bitsize; i++) { y >>= 1; result <<= 1; if (x >= y) { result++; x -= y; } } return result; }
int divide2(int x, int y, int bitsize) { int result = 0; for (int i = 0; i < bitsize; i++) { x <<= 1; result <<= 1; if (x >= y << bitsize) { result++; x -= y << bitsize; } } return result; }
16ビット整数の乗算・除算の説明
説明のため assert を入れたものを掲載します。multiply2 の assert が間違っていることがわかったので、Visual Studio の GitHub Copilot を使って「multiply2 の assert を正しく書き直してください」と入力したら作ってくれました。assert の式が複雑なのでほかの assert も間違っている可能性がありますが、今のところ説明のためには問題ないようなのでこのまま続けます。
乗算
/// <summary> /// 指定したビット数の乗算 /// </summary> /// <param name="x">被乗数</param> /// <param name="y">乗数</param> /// <param name="bitsize">被乗数・乗数のビット数(int のビット数の半分以下)</param> /// <returns>積</returns> int multiply1(int x, int y, int bitsize) { assert(x >= 0 && x < 1 << 16); assert(y >= 0 && y < 1 << 16); assert(bitsize <= 16); // x の初期値を x0、y の初期値を y0 とする int x0 = x; int y0 = y; int result = 0; for (int i = 0; i < bitsize; i++) { // x = x0 << i assert(x == x0 << i); // y = y0 >> i assert(y == y0 >> i); // result = x0 * (y0 の 下位 i ビット) assert(result == x0 * (y0 & ((1 << i) - 1))); if (y & 1) { result += x; } x <<= 1; y >>= 1; // x = x0 << (i + 1) assert(x == x0 << (i + 1)); // y = y0 >> (i + 1) assert(y == y0 >> (i + 1)); // result = x0 * (y0 の 下位 i + 1 ビット) assert(result == x0 * (y0 & ((1 << (i + 1)) - 1))); } // result = x0 * y0 assert(result == x0 * y0); return result; }
/// <summary> /// 指定したビット数の乗算 /// </summary> /// <param name="x">被乗数</param> /// <param name="y">乗数</param> /// <param name="bitsize">被乗数・乗数のビット数(int のビット数の半分以下)</param> /// <returns>積</returns> int multiply2(int x, int y, int bitsize) { assert(x >= 0 && x < 1 << 16); assert(y >= 0 && y < 1 << 16); assert(bitsize <= 16); // x の初期値を x0、y の初期値を y0 とする int x0 = x; int y0 = y; int c = 1 << bitsize; int result = 0; for (int i = 0; i < bitsize; i++) { // x = x0 assert(x == x0); // y = y0 << i assert(y == y0 << i); // result = x0 * (y0 の 上位 i ビットを右シフトして上位 i ビットだけにしたもの) assert(result == x0 * ((y0 >> (bitsize - i)) & ((1 << i) - 1))); y <<= 1; result <<= 1; if (y & c) { result += x; } // x = x0 assert(x == x0); // y = y0 << (i + 1) assert(y == y0 << (i + 1)); // result = x0 * (y0 の 上位 i + 1 ビットを右シフトして上位 i + 1 ビットだけにしたもの) assert(result == x0 * ((y0 >> (bitsize - (i + 1))) & ((1 << (i + 1)) - 1))); } // result = x0 * y0 assert(result == x0 * y0); return result; }
除算
/// <summary> /// 指定したビット数の除算 /// </summary> /// <param name="x">被除数</param> /// <param name="y">除数</param> /// <param name="bitsize">被除数・除数のビット数(int のビット数の半分以下)</param> /// <returns>商</returns> int divide1(int x, int y, int bitsize) { assert(x >= 0 && x < 1 << 16); assert(y >= 0 && y < 1 << 16); assert(bitsize <= 16); // x の初期値を x0、y の初期値を y0 とする int x0 = x; int y0 = y; int result = 0; y <<= bitsize; for (int i = 0; i < bitsize; i++) { // y = y0 << (bitsize - i) assert(y == y0 << (bitsize - i)); // result = x0 を y0 で割った商の 上位 i ビットを右シフトして上位 i ビットだけにしたもの) assert(result == ((x0 / y0) & ((1 << i) - 1)) >> (bitsize - i)); // x = x0 - y0 * (x0 を y0 で割った商の 上位 i ビット) assert(x == x0 - y0 * (((x0 / y0) & ((1 << i) - 1) << (bitsize - i)))); y >>= 1; result <<= 1; if (x >= y) { result++; x -= y; } // y = y0 << (bitsize - (i + 1)) assert(y == y0 << (bitsize - (i + 1))); // result = x0 を y0 で割った商の 上位 i + 1 ビットを右シフトして上位 i + 1 ビットだけにしたもの) assert(result == ((x0 / y0) & ((1 << (i + 1)) - 1)) >> (bitsize - (i + 1))); // x = x0 - y0 * (x0 を y0 で割った商の 上位 i + 1 ビット) assert(x == x0 - y0 * (((x0 / y0) & ((1 << (i + 1)) - 1) << (bitsize - (i + 1))))); } // result = x0 を y0 で割った商 assert(result == x0 / y0); // x = x0 を y0 で割った余り assert(x == x0 % y0); return result; }
/// <summary> /// 指定したビット数の除算 /// </summary> /// <param name="x">被除数</param> /// <param name="y">除数</param> /// <param name="bitsize">被除数・除数のビット数(int のビット数の半分以下)</param> /// <returns>商</returns> int divide2(int x, int y, int bitsize) { assert(x >= 0 && x < 1 << 16); assert(y >= 0 && y < 1 << 16); assert(bitsize <= 16); // x の初期値を x0、y の初期値を y0 とする int x0 = x; int y0 = y; int result = 0; for (int i = 0; i < bitsize; i++) { // y = y0 assert(y == y0); // result = x0 を y0 で割った商の 上位 i ビットを右シフトして上位 i ビットだけにしたもの) assert(result == ((x0 / y0) & ((1 << i) - 1)) >> (bitsize - i)); // x = (x0 - y0 * (x0 を y0 で割った商の 上位 i ビット)) を i ビット左シフトしたもの int q = (x0 / y0) & (((1 << i) - 1)) << (bitsize - i); assert(x == (x0 - y0 * q) << i); x <<= 1; result <<= 1; if (x >= y << bitsize) { result++; x -= y << bitsize; } // y = y0 assert(y == y0); // result = x0 を y0 で割った商の 上位 i + 1 ビットを右シフトして上位 i + 1 ビットだけにしたもの) assert(result == ((x0 / y0) & ((1 << (i + 1)) - 1)) >> (bitsize - (i + 1))); // x = (x0 - y0 * (x0 を y0 で割った商の 上位 i + 1 ビット)) を i + 1 ビット左シフトしたもの int qq = (x0 / y0) & (((1 << (i + 1)) - 1)) << (bitsize - (i + 1)); assert(x == (x0 - y0 * qq) << (i + 1)); } // result = x0 を y0 で割った商 assert(result == x0 / y0); // x = (x0 を y0 で割った余り) << bitsize assert(x == (x0 % y0) << bitsize); return result; }
