|
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())
|