Calculate the execution times of popcount functions

time_popcount.py

# coding: utf-8

def dummy(n):
    return 0


def popcnt0(n):
    c = 0
    for i in range(64):
        c += (n >> i) & 1
    return c


def popcnt1(n):
    return bin(n).count("1")


def popcnt2(n):
    return "{:b}".format(n).count("1")


#https://qiita.com/ocxtal/items/01c46b15cb1f2e656887
def popcnt3(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c


#http://www.valuedlessons.com/2009/01/popcount-in-python-with-benchmarks.html
POPCOUNT_TABLE8 = [0] * 2**8
for index in range(len(POPCOUNT_TABLE8)):
    POPCOUNT_TABLE8[index] = (index & 1) + POPCOUNT_TABLE8[index >> 1]

def popcnt4(v):
    return (POPCOUNT_TABLE8[ v        & 0xff] +
            POPCOUNT_TABLE8[(v >> 8)  & 0xff] +
            POPCOUNT_TABLE8[(v >> 16) & 0xff] +
            POPCOUNT_TABLE8[(v >> 24) & 0xff] +
            POPCOUNT_TABLE8[(v >> 32) & 0xff] +
            POPCOUNT_TABLE8[(v >> 40) & 0xff] +
            POPCOUNT_TABLE8[(v >> 48) & 0xff] +
            POPCOUNT_TABLE8[ v >> 56        ])


POPCOUNT_TABLE16 = [0] * 2**16
for index in range(len(POPCOUNT_TABLE16)):
    POPCOUNT_TABLE16[index] = (index & 1) + POPCOUNT_TABLE16[index >> 1]

def popcnt5(v):
    return (POPCOUNT_TABLE16[ v        & 0xffff] +
            POPCOUNT_TABLE16[(v >> 16) & 0xffff] +
            POPCOUNT_TABLE16[(v >> 32) & 0xffff] +
            POPCOUNT_TABLE16[(v >> 48)         ])


import gmpy2
popcnt6 = gmpy2.popcount


if __name__ == "__main__":
    import random
    def randloopf(f):
        return lambda: f(random.getrandbits(64))
        
    for n in range(100000):
        rand = random.getrandbits(64)
        assert popcnt0(rand) == popcnt1(rand) == popcnt2(rand) == popcnt3(rand) == popcnt4(rand) == popcnt5(rand) == popcnt6(rand)
        
    import timeit
    number=1000000
    #timeit.timeit(randloopf(popcnt0), number=number) # warm up
    print("dummy:", timeit.timeit(randloopf(dummy), number=number))
    print("popcnt0:", timeit.timeit(randloopf(popcnt0), number=number))
    print("popcnt1:", timeit.timeit(randloopf(popcnt1), number=number))
    print("popcnt2:", timeit.timeit(randloopf(popcnt2), number=number))
    print("popcnt3:", timeit.timeit(randloopf(popcnt3), number=number))
    print("popcnt4:", timeit.timeit(randloopf(popcnt4), number=number))
    print("popcnt5:", timeit.timeit(randloopf(popcnt5), number=number))
    print("popcnt6:", timeit.timeit(randloopf(popcnt6), number=number))