Write a function that takes an unsigned integer X and returns an integer representing the number of bits set to 1 in X. For example, if X was equal to 5, your function would return 2 since the binary representation of 5, which is
101, contains 2 bits set to 1.
There are a number of ways to approach solving this problem, but one of the most straight forward ways is to continually unset the right most bit set to 1 until your integer is equal to 0, and keep a count of the number of times you have done that. There are two equally valid ways to unset the right most bit with bitwise operations: m = m & (m - 1) or m -= m & -m. With the knowledge of how to unset the right most bit, we can write a function to solve our problem.
def count_set_bits(m): count = 0 while(m): m -= m & -m count += 1 return count
You may also want to read:
Given a singly linked list, write a function that returns a linked list with all the nodes in reverse order.Read More >>
Design a data structure that is similar to a stack. It will only contain unique integers (no integer will ever repeat), and should have a pop, push, peek, and max function that have O(1) time complexity.Read More >>