Karatsuba multiplication implementation in Java BigDecimal

Question

Recently I was trying to implement Karatsuba multiplication for large numbers. Then I tried comparing my implementation with the Java BigInteger implementation. I could not follow this line of code:

// result = p1 * 2^(32*2*half) + (p3 - p1 - p2) * 2^(32*half) + p2
BigInteger result = p1.shiftLeft(32*half).add(p3.subtract(p1).subtract(p2)).shiftLeft(32*half).add(p2);

According to Karatsuba algorithm, result = (p1 * 10 ^ (2*half) ) + ( (p3 -p1 - p2) * 10 ^ (half)) + (p2)

Since the implementation used int[], I believe 32 is the number of bits in Java integer.

But I didn't understand the part that involves shifting the bits to the left. Can you someone help me understand what is going on here?

Answer 1

Arithmetic shift

Arithmetic shifts can be useful as efficient ways to perform multiplication or division of signed integers by powers of two. Shifting left by n bits on a signed or unsigned binary number has the effect of multiplying it by 2^n. Shifting right by n bits on a two's complement signed binary number has the effect of dividing it by 2^n, but it always rounds down (towards negative infinity).