Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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)
))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.