bit_manipulation.count_number_of_one_bits

Functions

benchmark(→ None)	Benchmark code for comparing 3 functions, with different length int values.
get_set_bits_count_using_brian_kernighans_algorithm(→ int)	Count the number of set bits in a 32 bit integer
get_set_bits_count_using_lookup_table(→ int)	Count the number of set bits in a 32-bit integer using a precomputed lookup table.
get_set_bits_count_using_modulo_operator(→ int)	Count the number of set bits in a 32 bit integer

Module Contents

bit_manipulation.count_number_of_one_bits.benchmark() → None

Benchmark code for comparing 3 functions, with different length int values. Brian Kernighan’s algorithm is consistently faster than using modulo_operator, and the lookup table method is often the fastest for repeated calls.

bit_manipulation.count_number_of_one_bits.get_set_bits_count_using_brian_kernighans_algorithm(number: int) → int

Count the number of set bits in a 32 bit integer >>> get_set_bits_count_using_brian_kernighans_algorithm(25) 3 >>> get_set_bits_count_using_brian_kernighans_algorithm(37) 3 >>> get_set_bits_count_using_brian_kernighans_algorithm(21) 3 >>> get_set_bits_count_using_brian_kernighans_algorithm(58) 4 >>> get_set_bits_count_using_brian_kernighans_algorithm(0) 0 >>> get_set_bits_count_using_brian_kernighans_algorithm(256) 1 >>> get_set_bits_count_using_brian_kernighans_algorithm(-1) Traceback (most recent call last):

…

ValueError: the value of input must not be negative >>> get_set_bits_count_using_brian_kernighans_algorithm(1023) 10

bit_manipulation.count_number_of_one_bits.get_set_bits_count_using_lookup_table(number: int) → int

Count the number of set bits in a 32-bit integer using a precomputed lookup table.

I see similar approach in GeeksforGeeks, but the implementation is different. Link to Code: https://www.geeksforgeeks.org/dsa/count-set-bits-integer-using-lookup-table/

>>> get_set_bits_count_using_lookup_table(25)
3
>>> get_set_bits_count_using_lookup_table(37)
3
>>> get_set_bits_count_using_lookup_table(21)
3
>>> get_set_bits_count_using_lookup_table(58)
4
>>> get_set_bits_count_using_lookup_table(0)
0
>>> get_set_bits_count_using_lookup_table(256)
1
>>> get_set_bits_count_using_lookup_table(-1)
Traceback (most recent call last):
    ...
ValueError: the value of input must not be negative

bit_manipulation.count_number_of_one_bits.get_set_bits_count_using_modulo_operator(number: int) → int

Count the number of set bits in a 32 bit integer >>> get_set_bits_count_using_modulo_operator(25) 3 >>> get_set_bits_count_using_modulo_operator(37) 3 >>> get_set_bits_count_using_modulo_operator(21) 3 >>> get_set_bits_count_using_modulo_operator(58) 4 >>> get_set_bits_count_using_modulo_operator(0) 0 >>> get_set_bits_count_using_modulo_operator(256) 1 >>> get_set_bits_count_using_modulo_operator(-1) Traceback (most recent call last):

…

ValueError: the value of input must not be negative >>> get_set_bits_count_using_modulo_operator(1024) 1