java - Java BigDecimal 中的 Karatsuba 乘法实现

Question

最近我试图为大数实现 Karatsuba 乘法。然后我尝试将我的实现与 Java BigInteger 实现进行比较。我无法遵循这行代码：

// 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);

根据 Karatsuba 算法，result = (p1 * 10 ^ (2*half) ) + ( (p3 -p1 - p2) * 10 ^ (half)) + (p2)

由于实现使用了 int[]，我相信 32 是 Java 整数中的位数。

但我不明白涉及将位向左移动的部分。你能帮我理解这里发生了什么吗？

Answer 1

算术移位

算术移位可用作执行有符号整数乘以或除以 2 的幂的有效方法。n在有符号或无符号二进制数上左移一位具有将其乘以 的效果2^n。n在二进制补码符号二进制数上右移一位具有除以 的效果2^n，但它总是向下舍入（向负无穷大）。