[PYTHON] Fast bit count is bin (). count ('1')

We are implementing reversi using BitBoard. The number of stones is calculated by counting (bit counting) the number of standing bits.

I compared several implementations, but the easy implementation is fast.

bin_count

def count1(board):
    return bin(board).count('1')

At first, I thought it might be slow because it goes through a character string, but I think it is optimized and fast. The code I tried is below.

python

#Dummy function for call overhead measurement
def dummy(board):
    return 0

#implementation of popcount
def count2(board):
    board = (board & 0x5555555555555555) + (board >> 1 & 0x5555555555555555)
    board = (board & 0x3333333333333333) + (board >> 2 & 0x3333333333333333)
    board = (board & 0x0f0f0f0f0f0f0f0f) + (board >> 4 & 0x0f0f0f0f0f0f0f0f)
    board = (board & 0x00ff00ff00ff00ff) + (board >> 8 & 0x00ff00ff00ff00ff)
    board = (board & 0x0000ffff0000ffff) + (board >> 16 & 0x0000ffff0000ffff)
    return (board & 0x00000000ffffffff) + (board >> 32)

#Stupid way
def count3(board):
    result = 0
    while board:
        board >>= 1
        result += board & 1
    return result

def main():
    board = 0b0010000000100000000011000011010000111100000110000000000000000000

    import time

    temp = time.time()
    for i in range(100000):
        dummy(board)
    print(f"dummy : {time.time() - temp}")

    temp = time.time()
    for i in range(100000):
        count1(board)
    print(f"count1: {time.time() - temp}")

    temp = time.time()
    for i in range(100000):
        count2(board)
    print(f"count2: {time.time() - temp}")

    temp = time.time()
    for i in range(100000):
        count3(board)
    print(f"count3: {time.time() - temp}")

if __name__ == "__main__":
    main()

The result is below.

dummy : 0.010009050369262695
count1: 0.0470428466796875
count2: 0.152146577835083
count3: 1.0559582710266113

count1 can be calculated in the same order as the overhead of the call (dummy). The count2 algorithm uses an O (logN) algorithm called popcount, which is slow. The difference is clear when compared to count3.