Recursive Multiply

作者 QIFAN 日期 2016-10-01
Recursive Multiply

Write a recursive function to multiply two positive integers without using the * operator (or / operator). You can use addition, subtraction, and bit shifting, but you should minimize the number of those operations.

思路

要求minimize运算的次数。
假设n = small * bigger

若small为偶,n = (small/2 * bigger) * 2
若small为奇,n = (small/2 * bigger) * 2 + bigger

解题

public int product(int a, int b) {
if(a == 0 || b == 0) return 0;
int small = (a < b) ? a : b;
int bigger = (a > b) ? a : b;
return helper(smaller, bigger);
}
public int helper(int smaller, int bigger) {
if (smaller == 0) return 0;
if (smaller == 1) return bigger;
int half = helper((smaller >> 1), bigger);
if (smaller % 2 == 0) {
return half << 1;
}
return (half << 1) + bigger;
}

复杂度分析

时间log(N)