1__all__ = ['popCount'] 2 3 4def popCount(v): 5 """Return number of 1 bits (population count) of an integer. 6 7 If the integer is negative, the number of 1 bits in the 8 twos-complement representation of the integer is returned. i.e. 9 ``popCount(-30) == 28`` because -30 is:: 10 11 1111 1111 1111 1111 1111 1111 1110 0010 12 13 Uses the algorithm from `HAKMEM item 169 <https://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item169>`_. 14 15 Args: 16 v (int): Value to count. 17 18 Returns: 19 Number of 1 bits in the binary representation of ``v``. 20 """ 21 22 if v > 0xFFFFFFFF: 23 return popCount(v >> 32) + popCount(v & 0xFFFFFFFF) 24 25 # HACKMEM 169 26 y = (v >> 1) & 0xDB6DB6DB 27 y = v - y - ((y >> 1) & 0xDB6DB6DB) 28 return (((y + (y >> 3)) & 0xC71C71C7) % 0x3F) 29