Let's break down the issues with your current code and walk through the simplest fixes, including a bitwise-optimized approach that sticks to your constraints of no strings or math.pow.

Issues in the Current Code #

1. Broken Base Case:
   Your base case return x&y only works for non-negative 0/1 values. For negative numbers (e.g., -1 & 1 = 1, but -1 * 1 = -1) or numbers larger than 1 (e.g., 3 & 2 = 2, but 3 * 2 = 6), this returns the wrong result. This is a critical bug that flies under the radar for small positive inputs but breaks entirely with negatives.

2. Unhandled Negative Values:
   Karatsuba's algorithm is designed for non-negative integers. When you pass negative numbers, arithmetic right shifts (>>) fill with 1s, leading to incorrect splits of a/b and c/d in recursive calls. Combined with the bad base case, this amplifies errors drastically.

Simplest Fix: Symbol Tracking + Corrected Base Case #

The most straightforward fix is to:

• Track the result's sign (negative if inputs have opposite signs, positive otherwise)
• Compute the product of absolute values using the fixed Karatsuba logic
• Apply the sign to the final product

Here's the revised code:

def karatsuba(x, y):
    # Track if the result should be negative (XOR of input signs)
    result_sign = -1 if (x < 0) ^ (y < 0) else 1
    
    # Work with absolute values (Karatsuba expects non-negatives)
    x_abs = abs(x)
    y_abs = abs(y)
    
    n = max(x_abs.bit_length(), y_abs.bit_length())
    # Fixed base case: return actual product, not bitwise AND
    if n < 2:
        return result_sign * x_abs * y_abs
    
    n = (n + 1) >> 1
    b = x_abs >> n
    a = x_abs - (b << n)
    d = y_abs >> n
    c = y_abs - (d << n)
    
    ac = karatsuba(a, c)
    bd = karatsuba(b, d)
    abcd = karatsuba(a + b, c + d)
    
    product = ac + ((abcd - ac - bd) << n) + (bd << (n << 1))
    return result_sign * product

# Test cases
print(karatsuba(23, 24))   # Output: 552
print(karatsuba(-29, 31))  # Output: -899 (correct result of -29*31)

Bitwise-Optimized Alternative for Absolute Values #

If you want to avoid Python's built-in abs() and stick purely to bitwise operations, you can compute absolute values using sign-bit manipulation:

• For non-zero integers, arithmetic right shift by x.bit_length() gives 0 for positives and -1 for negatives.
• XORing x with this sign bit flips all bits for negatives (equivalent to ~x), then subtracting the sign bit adds 1 (since -(-1) = 1), resulting in the absolute value.

Here's the fully bitwise version:

def abs_bitwise(x):
    if x == 0:
        return 0
    # Get sign bit: 0 for positive, -1 for negative
    sign_bit = x >> x.bit_length()
    # Compute absolute value via bitwise operations
    return (x ^ sign_bit) - sign_bit

def karatsuba(x, y):
    # Track result sign using XOR of input signs
    result_sign = -1 if (x < 0) ^ (y < 0) else 1
    
    x_abs = abs_bitwise(x)
    y_abs = abs_bitwise(y)
    
    n = max(x_abs.bit_length(), y_abs.bit_length())
    if n < 2:
        return result_sign * x_abs * y_abs
    
    n = (n + 1) >> 1
    b = x_abs >> n
    a = x_abs - (b << n)
    d = y_abs >> n
    c = y_abs - (d << n)
    
    ac = karatsuba(a, c)
    bd = karatsuba(b, d)
    abcd = karatsuba(a + b, c + d)
    
    product = ac + ((abcd - ac - bd) << n) + (bd << (n << 1))
    return result_sign * product

Quick Note #

Your original comment # 381 for -29 * 31 was incorrect— the correct result is -899, which the fixed code returns as expected.

内容的提问来源于stack exchange，提问作者hardfork