> Interview Breeze

Number of set bits in an integer

Problem

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.

Solution

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:

Reverse a singly linked list

Given a singly linked list, write a function that returns a linked list with all the nodes in reverse order.

Read More >>
Max Stack

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 >>
Target Subsequence

Given a sequence of positive integers A and an integer T, return whether there is a *continuous sequence* of A that sums up to exactly T.

Read More >>

Python Console