import typing


def naive_sqrt_ctz2(x: int) -> typing.Tuple[int, int]:
    """Count trailing zeros, in O(sqrt(zeros)) steps.

    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 implementation is much faster than the naive linear implementation
    for many numbers of reasonable size. Because it looks at windows of
    linearly increasing size, it only needs to perform the square root
    of the number of zeros total steps, and it avoids constructing a number
    with many more bits than x (the logarithmic implementation below can
    compare x against a mask with twice as many bits in the worst case).
    Because it tracks the remaining significant bits of x explicitly, this
    implementation can return them more efficiently than the caller re-doing
    the right shift, so it is provided as a "ctz2".

    We still say this implementation is "naive" because it does not try
    to use any specific optimization tricks besides the sqrt algorithm. For
    some numbers with a very large number of zeros, it may be asymptotically
    worse than the logarithmic algorithm.

    >>> naive_sqrt_ctz2(0)
    (0, 0)
    >>> naive_sqrt_ctz2(1)
    (0, 1)
    >>> naive_sqrt_ctz2(-1)
    (0, -1)
    >>> naive_sqrt_ctz2(2)
    (1, 1)
    >>> naive_sqrt_ctz2(-2)
    (1, -1)
    >>> naive_sqrt_ctz2(40) # 0b101000 = 2**3 * 5
    (3, 5)
    >>> naive_sqrt_ctz2(-40) # 0b1..1011000
    (3, -5)
    >>> naive_sqrt_ctz2(37 << 100)
    (100, 37)

    # Of course the behavior should match for all integers...
    >>> all(naive_ctz2(x) == naive_sqrt_ctz2(x) for x in range(1024))
    True
    """
    if x == 0:
        return 0, 0
    else:
        zmask = 1
        zscale = 1
        zeros: int = 0

        # divide out larger and larger powers, until x % 2**zscale != 0
        while x & zmask == 0:
            x >>= zscale
            zeros += zscale
            zscale += 1
            zmask = (zmask << 1) | 1

        # recover smaller powers
        while zscale > 0:
            zmask >>= 1
            zscale -= 1
            if x & zmask == 0:
                x = x >> zscale
                zeros += zscale

        # Using for with a range may allow Python to produce more efficient
        # bytecode for this loop, but the difference is only a few percent,
        # at least based on some quick testing with CPython 3.6.3.

        # for zscale in range(zscale-1, 0, -1):
        #     zmask >>= 1
        #     if x & zmask == 0:
        #         x = x >> zscale
        #         zeros += zscale

        return zeros, x