Реализация умножения Карацубы в Java BigDecimal

Question

Недавно я пытался реализовать умножение Карацубы для больших чисел. Затем я попытался сравнить мою реализацию с реализацией 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);

Согласно алгоритму Карацубы, result = (p1 * 10 ^ (2*half) ) + ( (p3 -p1 - p2) * 10 ^ (half)) + (p2)

Поскольку в реализации используется int[], я считаю, что 32 - это число битов в Java integer.

Но я не понял той части, которая предполагает сдвиг битов влево. Можете ли вы помочь мне понять, что здесь происходит?

Answer 1

Арифметический сдвиг

Арифметические сдвиги могут быть полезны в качестве эффективных способов выполнения умножения или деления целых чисел со знаком на степени двойки. Сдвиг оставил n Биты двоичного числа со знаком или без знака приводят к умножению его на 2^n, Сдвиг вправо n биты двоичного числа со знаком дополнения до двух имеет эффект деления его на 2^n, но всегда округляется (в сторону отрицательной бесконечности).