Counting the number of 1 bits (the population count) is the foundation of bitsets, hashing, and error-correcting codes.
The naive way loops over all 32 or 64 bit positions. Brian Kernighan's trick is smarter: the expression n & (n - 1) clears the lowest set bit of n, so the number of loop iterations equals the number of set bits.
Implement count_set_bits(n) to return how many 1 bits are in the binary representation of a non-negative integer n.
Example: 7 is 0b111, so the answer is 3.
def count_set_bits(n):
"""Return the number of 1 bits in the binary representation of n.
Use Brian Kernighan's trick: n & (n - 1) clears the lowest set bit,
so each loop iteration removes exactly one set bit.
"""
# TODO: loop while n is nonzero, clear the lowest bit with n &= n - 1,
# and increment a counter each time.
pass
The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.
Counting the number of 1 bits (the population count) is the foundation of bitsets, hashing, and error-correcting codes.
The naive way loops over all 32 or 64 bit positions. Brian Kernighan's trick is smarter: the expression n & (n - 1) clears the lowest set bit of n, so the number of loop iterations equals the number of set bits.
Implement count_set_bits(n) to return how many 1 bits are in the binary representation of a non-negative integer n.
Example: 7 is 0b111, so the answer is 3.
Press Run Tests or ⌘↩ to check your solution.