import random


def gen_random(n: int) -> int:
    return random.randint(0, (1 << n) - 1)


def as_bits(a: int, n: int) -> list[int]:
    return list(map(int, bin(a)[2:].zfill(n)))


def from_bits(bits: list[int]) -> int:
    s = ''.join(list(map(str, bits)))
    return int(s, 2)


if __name__ == "__main__":
    random.seed(0)

    # Length of numbers in bits
    n = 64

    # Generate random integers
    a = gen_random(n)
    b = gen_random(n)

    print(f'a = {a}')
    print(f'b = {b}')

    # Represent integers as bits
    a_bits = as_bits(a, n)
    b_bits = as_bits(b, n)

    print(f'a_bits = {a_bits}')
    print(f'b_bits = {b_bits}')

    # Step 1. Sum and carry
    s_bits = [(ai ^ bi) for (ai, bi) in zip(a_bits, b_bits)]
    c_bits = [(ai & bi) for (ai, bi) in zip(a_bits, b_bits)]

    # Step 2. Set uncertainty 2 to c_bits
    c_bits = [
        2 if s_bits[i] == 1 else ci
        for i, ci in enumerate(c_bits)
    ]

    # Step 3. Calculate carries of the blocks
    d = 1
    while d < n:
        for i in range(0, n, 2 * d):
            if c_bits[i] == 2:
                c_bits[i] = c_bits[i + d]
        d *= 2

    # Step 4. Resolve uncertainty of the blocks
    d = n
    while d > 0:
        for i in range(d, n, 2 * d):
            if c_bits[i] == 2:
                c_bits[i] = c_bits[i + d] if i + d < n else 0
        d //= 2

    # Step 5. Update s_bits considering the calculated carries
    s_bits = [
        si ^ c_bits[i + 1] if i < n - 1 else si
        for i, si in enumerate(s_bits)
    ]
    print(f's_bits = {s_bits}')

    # Check the result
    print(from_bits(s_bits), '=', (a + b) & (2**n - 1))
    assert from_bits(s_bits) == (a + b) & (2**n - 1)