import typing


def naive_ctz2(x: int) -> typing.Tuple[int, int]:
    """Count trailing zeros, naively.

    Args:
        x: An int.

    Returns:
        A tuple (zeros, x >> zeros) where zeros is the number of trailing
        zeros in x. I.e. (x >> zeros) & 1 == 1 or x == zeros == 0.

    This is a slow reference implementation for checking correctness. Since
    it never needs to check the bit_length of x or do any multiplication,
    it may be acceptably fast for numbers that have a very small number of
    trailing zeros.

    As it inherently tracks the remaining significant bits of x, this
    implementation returns them as well as the number of zeros, hence its
    name "ctz2".

    >>> naive_ctz2(0)
    (0, 0)
    >>> naive_ctz2(1)
    (0, 1)
    >>> naive_ctz2(-1)
    (0, -1)
    >>> naive_ctz2(2)
    (1, 1)
    >>> naive_ctz2(-2)
    (1, -1)
    >>> naive_ctz2(40) # 0b101000 = 2**3 * 5
    (3, 5)
    >>> naive_ctz2(-40) # 0b1..1011000
    (3, -5)
    >>> naive_ctz2(37 << 100)
    (100, 37)
    """
    if x == 0:
        return 0, 0
    else:
        zeros: int = 0
        while x & 1 == 0:
            x = x >> 1
            zeros += 1
        return zeros, x