Question

Consider the following C functions.

int tob(int b, int* arr) {
  int i;
  for (i=0; b>0; i++) {
    if (b%2) arr[i]=1;
    else arr[i]=0;
    b = b/2;
  }
  return (i);
}

int pp(int a, int b) {
  int arr[20];
  int i, tot=1, ex, len;
  ex = a;
  len = tob(b, arr);
  for (i=0; i<len; i++) {
    if (arr[i]==1) tot = tot*ex;
    ex = ex*ex;
  }
  return (tot);
}

The value returned by pp(3, 4) is ____.

Accepted Answer

The correct answer is 81. tob(4, arr) extracts the binary digits of 4=100₂ from LSB to MSB into arr: 4%2=0→arr[0]=0, b=2; 2%2=0→arr[1]=0, b=1; 1%2=1→arr[2]=1, b=0 (loop stops). Returns len=3. This is exactly the classic binary-exponentiation ('square and multiply') algorithm computing aᵇ: starting tot=1, ex=3, loop over each bit of b from LSB: i=0 (bit 0): skip tot (bit=0), ex=3²=9; i=1 (bit 0): skip tot, ex=9²=81; i=2 (bit 1): tot=1×81=81, ex=81²(unused). Final tot=81 = 3⁴, confirming pp(a,b) computes aᵇ.

Explanation