by Fedor Iskhakov, ANU
Description: Parity of a number, bitwise operations in Python. Finding maximum in an array.
Whether a decimal number is divisible by 10 can be easily seen from its last digit.
Similarly, whether a binary number is divisible by 2 can be easily seen from its last digit.
If last digit of a number is 0, it is divisible by its base!
This algorithm only applies to integers
# bitwise logic
a,b = 3,5 # 3=0011, 5=0101
print(' a = {0:d} ({0:04b})\n b = {1:d} ({1:04b})'.format(a,b))
print('a&b = {0:d} ({0:04b})'.format(a&b))
# print('a|b = {0:d} ({0:04b})'.format(a|b))
# print('a^b = {0:d} ({0:04b})'.format(a^b))
a = 3 (0011) b = 5 (0101) a&b = 1 (0001)
Is it possible? Which operations can be done in this geeky way?
# bit shifts
a = 0b11100011
b = a >> 1
print(' a = {0:4d} ({0:016b})\n b = {1:4d} ({1:016b})\n'.format(a,b))
b = a << 2
print(' a = {0:4d} ({0:016b})\n b = {1:4d} ({1:016b})\n'.format(a,b))
a = 227 (0000000011100011) b = 113 (0000000001110001) a = 227 (0000000011100011) b = 908 (0000001110001100)
# arythmetic operations with bit shifts
a = 0b11100011
print(' a = {0:4d} ({0:016b})'.format(a))
for i in range(1,10):
x = 2**i
d = a//x
s = a>>i
print('a//%d = %d, a>>%d = %d' % (x,d,i,s))
a = 227 (0000000011100011) a//2 = 113, a>>1 = 113 a//4 = 56, a>>2 = 56 a//8 = 28, a>>3 = 28 a//16 = 14, a>>4 = 14 a//32 = 7, a>>5 = 7 a//64 = 3, a>>6 = 3 a//128 = 1, a>>7 = 1 a//256 = 0, a>>8 = 0 a//512 = 0, a>>9 = 0
Run a single bitwise AND operation to compare against 0b0000001 which is simply 1 in decimal
Complexity is constant because only one bit must be checked!
However, when running AND are all bits checked?
# parity check
def parity (n,verbose=False):
'''Returns 1 if passed integer number is odd
'''
pass
# check parity of various numbers
for n in [2,4,7,32,543,671,780]:
print('n = {0:5d} ({0:08b}), parity={1:d}'.format(n,parity(n)))
n = 2 (00000010), parity=0 n = 4 (00000100), parity=0 n = 7 (00000111), parity=1 n = 32 (00100000), parity=0 n = 543 (1000011111), parity=1 n = 671 (1010011111), parity=1 n = 780 (1100001100), parity=0
def parity (n,verbose=False):
'''Returns 1 if passed integer number is odd
'''
if not isinstance(n, int): raise TypeError('Only integers in parity()')
if verbose: print('n = {:08b}'.format(n)) # print binary form of the number
return n & 1 # bitwise and operation returns the value of last bit
def maximum_from_list (vars):
'''Returns the maximum from a list of values
'''
pass
# find maximum in some random lists
import numpy as np
for i in range(5):
list = np.random.uniform(low=0.0, high=100.0, size=10)
m = maximum_from_list(list)
print('Maximum in {} is {:.2f}'.format(list,m))
Maximum in [40.36631825 33.1923305 4.85928511 31.26526949 38.56821075 92.47304391 61.57887596 12.81310827 92.20711143 45.12116267] is 92.47 Maximum in [36.19221981 68.39217716 71.45549904 59.94828759 17.04806836 42.36644573 65.48883833 91.13163144 57.13898149 67.50339454] is 91.13 Maximum in [75.48095297 70.96067478 15.19709572 94.50537863 79.74015518 99.65516414 88.51336519 38.89378926 22.89769873 4.56590212] is 99.66 Maximum in [46.96531804 30.02051975 20.0643693 11.77139318 77.8880612 1.88485342 82.53652171 56.93653459 79.10377169 33.83294574] is 82.54 Maximum in [ 3.46403787 25.77379166 79.32433345 96.9859477 41.5598842 17.76082696 34.37472047 2.59704741 71.6989639 43.67998844] is 96.99
def maximum_from_list (vars):
'''Returns the maximum from a list of values
'''
m=float('-inf') # init with the worst value
for v in vars:
if v > m: m = v
return m