import sys

def popcount(i):
	i = i - ((i >> 1) & 0x55555555)
	i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
	return ((((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) & 0xFFFFFFFF) >> 24

def main():
	print 'Popcount Algorithm Overview\n'
	
	#i = i - ((i >> 1) & 0x55555555);
    #i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    #return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
	
	uint = raw_input('Enter a 32 bit unsigned number> ')
	if uint.startswith('0x'):
		uint = int(uint, 16) & 0xFFFFFFFF
	else:
		uint = int(uint) & 0xFFFFFFFF
	print

	#i = i - ((i >> 1) & 0x55555555);
	print 'Step  0: Input number:                                       {:>10d} -- hex: 0x{:08X}'.format(uint, uint)
	op_step1 = (uint >> 1)
	print 'Step  1: (i >> 1):                                           {:>10d} -- hex: 0x{:08X}'.format(op_step1, op_step1)
	op_step2 = op_step1 & 0x55555555
	print 'Step  2: ((i >> 1) & 0x55555555):                            {:>10d} -- hex: 0x{:08X}'.format(op_step2, op_step2)
	op_step3 = uint - op_step2
	print 'Step  3: i - ((i >> 1) & 0x55555555):                        {:>10d} -- hex: 0x{:08X}'.format(op_step3, op_step3)
	print
	
	#i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
	op_step4 = op_step3 & 0x33333333
	print 'Step  4: (i & 0x33333333):                                   {:>10d} -- hex: 0x{:08X}'.format(op_step4, op_step4)
	op_step5 = op_step3 >> 2
	print 'Step  5: (i >> 2):                                           {:>10d} -- hex: 0x{:08X}'.format(op_step5, op_step5)
	op_step6 = op_step5 & 0x33333333
	print 'Step  6: ((i >> 2) & 0x33333333):                            {:>10d} -- hex: 0x{:08X}'.format(op_step6, op_step6)
	op_step7 = op_step4 + op_step6
	print 'Step  7: (i & 0x33333333) + ((i >> 2) & 0x33333333):         {:>10d} -- hex: 0x{:08X}'.format(op_step7, op_step7)
	print
	
	#ans = (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24
	op_step8 = op_step7 >> 4
	print 'Step  8: (i >> 4):                                           {:>10d} -- hex: 0x{:08X}'.format(op_step8, op_step8)
	op_step9 = op_step7 + op_step8
	print 'Step  9: (i + (i >> 4)):                                     {:>10d} -- hex: 0x{:08X}'.format(op_step9, op_step9)
	op_step10 = op_step9 & 0x0F0F0F0F
	print 'Step 10: ((i + (i >> 4)) & 0x0F0F0F0F):                      {:>10d} -- hex: 0x{:08X}'.format(op_step10, op_step10)
	op_step11 = (op_step10 * 0x01010101) & 0xFFFFFFFF
	print 'Step 11: (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101):       {:>10d} -- hex: 0x{:08X}'.format(op_step11, op_step11)
	op_step12 = op_step11 >> 24
	print 'Step 12: (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24: {:>10d} -- hex: 0x{:08X}'.format(op_step12, op_step12)
	print
	print 'Popcount: {:d}'.format(popcount(uint))
	
if __name__ == '__main__':
	sys.exit(main())