No. 20 - Number of 1 in a Binary

Problem: Please implement a function to get the number of 1s in an integer. For example, the integer 9 is 1001 in binary, so it returns 2 since there are two bits of 1s.

Analysis: It looks like a simple question about binary numbers, and we have many solutions for it. Unfortunately, the most intuitive solution for many candidates is incorrect. We should be careful.

Solution 1: Check the most right bit, possibly with endless loop

When candidates are interviewed with this problem, many of them find a solution in short time: check whether the most right bit is 0 or 1, and then right shit the integer one bit and check the most right bit again. It continues in a loop until the integer becomes 0. How to check whether the most right bit of an integer is 0 or 1? It is simple since we have AND operation. There is only one bit of 1, which is the most right bit, in the binary format of integer 1. When we have AND operation on an integer and 1, we can check whether the most right bit is 0 or 1. When the result of AND operation is 1, it indicates the right most bit is 1; otherwise it is 0. We can implement a function base on this solution quickly:

int NumberOf1(int n)
{
    int count = 0;
    while(n)
    {
        if(n & 1)
            count ++;

        n = n >> 1;
    }

    return count;
}

Interviewers may ask a question when they are told this solution: What is the result when the input integer is a negative number such as 0x80000000? When we right shift the negative number 0x80000000 a bit, it become 0xC0000000 rather than 0x40000000, which is the result to move the first bit of 1 to the second bit. The integer 0x8000000 is negative before shift, so we should guarantee it is also negative after shift. Therefore, when a negative integer is right shifted, the first bit is set as 1 after the right shift operation. If we continue to shift to right side, a negative integer will be 0xFFFFFFFF eventually and it is trapped in an endless loop.

Solution 2: Check the most right bit, with left shift operation on 1

We should not right shift the input integer to avoid endless loop. Instead of shifting the input integer n to right, we may shift the number 1 to left. We may check firstly the least important bit of n, and then shift the number 1 to left, and continue to check the second least important bit of n. Now we can rewrite our code based on this solution:

int NumberOf1(int n)

{

    int count = 0;

    unsigned int flag = 1;

    while(flag)

    {

        if(n & flag)

            count ++;

        flag = flag << 1;

    }

    return count;

}

In the code above, it loops 32 times on 32-bit numbers.

Solution 3: Creative solution

Let us analyze that what happens when a number minus 1. There is at least one bit 1 in a non-zero number. We firstly assume the right most bit is 1. It becomes 0 if the number minus 1 and other bits keep unchanged. This result is identical to the not operation on the most right bit of a number, which also turns the right most bit from 1 into 0.

Secondly we assume the right most bit is 0. Since there is at least one bit 1 in a non-zero number, we suppose the m^th bit is the most right bit of 1. When it minus 1, the m^th bit becomes 0, and all 0 bits behind the m^th bit become 1. For instance, the second bit of binary number 1100 is the most right bit of 1. When it minus 1, the second bit becomes 0, and the third and fourth bits become 1, so the result is 1011.

In both situations above, the most right of bit 1 becomes 0 when it minus 1. When there are some 0 bits at right side, all of them become 1. The result of bit and operation on the original number and minus result is identical to result to modify the most right 1 into 0. Take the binary number 1100 as an example again. Its result is 1011 when it minus 1. The result of and operation on 1100 and 1011 is 1000. If we change the most right of 1 bit in number 1100, it also becomes 1000.

The analysis can be summarized as: If we first minus a number with 1, and have and operation on the original number and the minus result, the most right of 1 bit becomes 0. We continue these operations until the number becomes 0. We can develop the following code accordingly:

int NumberOf1(int n)

{

    int count = 0;

    while (n)

    {

        ++ count;

        n = (n - 1) & n;

    }

    return count;

}

The number of times in the while loops equals to the number of 1 in the binary format of input n.

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.
 

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.