The Exponent Zero Case

This fast-exponentiation routine is supposed to return xyx^y for y≥0y \ge 0:

int f(int x, int y) {
  int r = 1;
  int b = x;   /* base     */
  int e = y;   /* exponent */
  while (e > 1) {
    if (e % 2 == 1) { r = b * r; }
    b = b * b;
    e = e / 2;
  }
  return r * b;
}

Tracing f(2, 7) shows the quantity r⋅ber \cdot b^{e} never moves:

iteration b e r beb^{e} r⋅ber \cdot b^{e}
0 2 7 1 128 128
1 4 3 2 64 128
2 16 1 8 16 128

The loop exits with e == 1, and return r * b reads off 8⋅16=128=278 \cdot 16 = 128 = 2^7. Which call still returns the wrong answer?

A

None of them; the invariant r⋅be=xyr \cdot b^{e} = x^{y} holds on every path, so the routine is correct for every y≥0y \ge 0.

B

f(2, 0), which returns 2 instead of 1.

C

f(2, 1), which returns 1 instead of 2.

D

f(0, 5), which returns 1 instead of 0.