hil

整数四則演算の所要ビット数

オーバーフローの可能性を机上検討したときのメモです。

 

 0以上の整数 n, mで表せる整数 x, y
   0 \leq x \leq 2^{n - 1}
   0 \leq y \leq 2^{m - 1}
とするとき、
   x  op  y
の計算結果の最大ビット数は以下になります。

op n = m n > m n < m
+ n + 1 n + 1 m + 1
- n + 1 m + 1 m + 1
* n + m n + m n + m
/ n n n

※ 計算結果が負のとき、符号ビットを1ビットとします。

 

例1)n = m = 8のとき:

  op が + なら、255 + 255 = 510 (9bit)

  op が - なら、0 - 255 = -255 (9bit)

  op が * なら、255 * 255 =  65025 (16bit)

  op が / なら、255 / 1 = 255 (8bit)

 

例2)n = 8 かつ m = 7のとき:

  op が + なら、255 + 127= 404 (9bit)

  op が - なら、0 - 127= -127 (8bit)

  op が * なら、255 * 127= 32385 (15bit)

  op が / なら、255 / 1 = 255 (8bit)

 

例3)n = 7 かつ m = 8のとき:

  op が + なら、127+ 255= 404 (9bit)

  op が - なら、0 - 255= -255 (9bit)

  op が * なら、127 * 255 = 32385 (15bit)

  op が / なら、127/ 1 = 127 (7bit)