Skip to content

Instantly share code, notes, and snippets.

@Arcensoth
Last active November 25, 2016 20:09
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Arcensoth/3213208b51bb7ec64a8228ae8060fd41 to your computer and use it in GitHub Desktop.
Save Arcensoth/3213208b51bb7ec64a8228ae8060fd41 to your computer and use it in GitHub Desktop.
while True:
try:
inp = input('>') # input flags in binary, like this: 01110010
except KeyboardInterrupt:
print('\ngoodbye')
break
n = len(inp) # could also be locked (for example, at n=32 for integer capacity)
try:
flags = int(inp, 2)
except:
print('invalid input')
continue
print('you entered {inp} ({flags})'.format(inp=inp, flags=flags))
for i in range(1, n + 1):
p = 2 ** i
q = 2 ** (i - 1)
m = flags % p
flag = m >= q
print('{i_str} {flag_str} p={p}, q={q}, m={flags}%{p}={m}, {m} {sign} {q}'.format(
i_str=str(i).ljust(4), flag_str=str(flag).ljust(8), flags=flags, p=p, q=q, m=m, sign='>=' if flag else '<'))
@Arcensoth
Copy link
Author

Credits to @Arth2000 for providing an explanation and for reducing the number of basic operations from 3 down to 2:

Both of these ways use 3 cbs though (1 copy, 1 division and 1 modulus). It is actually possible to reduce it to 2: If you want to check if the kth flag is on then you take the bitmask modulus 2^k and you check if the result is at least 2^(k - 1). This is assuming you that if the kth bit is on then the kth flag is on, so no inverted bit mask. If you really want to use the inverted bitmask then you have to check if the result is smaller than 2^(k-1). It works because when you take the modulus by 2^k you are in fact wiping out all the bits from the kth to the latest. By example if your bitmask is 0b10110 and we want to check if the 2nd flag is on then we take the modulus by 2^2 = 4 which wipes out all the bits but the first 2 and we get as result 0b10. Then you check if the result is at least 2^(2-1) = 2^1 = 2. As 0b10 = 2 it is the case. And because the sum of the n first powers of 2 including 2^0 is equal to 2^(n+1) - 1 you can be sure than even if all the bits before the one we care about are on the result will still be smaller than 2^(k - 1).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment