31. Multiply two integers without using loops, multiplication, bitwise, division, and operators
The solution to this problem can start from the following algebraic formula, also known as the special binomial product formula:
Figure 1.24: Extracting a*b from a binomial formula
Now that we have the a*b product, there is only one issue left. The formula of a*b contains a division by 2, and we are not allowed to explicitly use the division operation. However, the division operation can be mocked in a recursive fashion, as follows:
private static int divideByTwo(int d) {
if (d < 2) {
return 0;
}
return 1 + divideByTwo(d - 2);
}
Nothing can stop us now from using this recursive code to implement a*b, as follows:
public static int multiply(int p, int q) {
// p * 0 = 0, 0 * q = 0
if (p == 0 || q == 0) {
return 0;
}
int pqSquare = (int) Math.pow(p + q, 2);
int pSquare = (int) Math.pow(p, 2);
int qSquare = (int) Math.pow(q, 2);
int squareResult...