size.py

def ilog256_speed(original_num):
    # Exponential search to find upper bound
    ilog_upper = 8
    while (original_num >> ilog_upper) > 0:
        ilog_upper = ilog_upper << 1

    # The lower bound is the previuse step
    ilog_lower = ilog_upper >> 1

    # Binary search between bounds to find ilog2
    while ilog_upper - ilog_lower > 1:
        ilog = (ilog_upper + ilog_lower) // 2
        if (original_num >> ilog) > 0:
            ilog_lower = ilog
        else:
            ilog_upper = ilog

    # Convert ilog2 to ilog256
    return ilog >> 3


print('%8s %8s' % ('correct', 'output'))
for power in [0, 1, 2, 3, 4, 16, 256, 1024, 2048, 65536]:
    print('%8d %8d' % (
        power, ilog256_speed(256**power)
    ))