Wednesday, November 9, 2011

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 mth bit is the most right bit of 1. When it minus 1, the mth bit becomes 0, and all 0 bits behind the mth 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. 

17 comments:

  1. Very Usefull Post! Love your blog! I have converted your algorithm in Java and it works like charm!. In my free time i will post your few contents with algorithm in Java(under your authority as mentioned above) in my blog http://www.yro-tech.blogspot.com

    ReplyDelete
    Replies
    1. Cool, please go ahead to post the Java version:)

      Delete
    2. Hi Harry,

      Your writing shines like gold! There is no room for gibberish here clearly. You nailed it in Number of 1 in a Binary!

      I will have the mp3 files my customer buys on a WordPress page and a cart will direct them to that page . If I want the mp3 files to be downloaded by the customer is there any reason to protect them except to keep them from being indexed by a search engine? Do I need to have a key or do a get operation other than have server-side encryption in S3?

      Very useful article, if I run into challenges along the way, I will share them here.

      Grazie,
      Kevin

      Delete
  2. In C#, you can do
    Convert.ToString(n, 2).ToCharArray().Where(@char => @char == '1').Count();
    but I bet they would not accept such trick

    ReplyDelete
  3. Easy log(n) solution which avoids bit operations:

    int count =0;
    while(n>0){
    if(n%2==1) count++;
    n/= 2;
    }
    return count;

    ReplyDelete
  4. I have seen better solutions with out the use of any for or while loops. I feel these answers are more correct because it lowers the amount of operations needed to complete the task.

    ReplyDelete
  5. "Hamming weight" is the answer. Solves the problem for a 32-bit integer in 18 arithmetic operations (and, add, shift)

    ReplyDelete
  6. simply we can write it as

    while(n)
    {
    n=n&(n-1);
    count++
    }
    return count;

    ReplyDelete
  7. Sain Bainuu,

    Your writing shines like gold! There is no room for gibberish here clearly. You nailed it in No. 20 - Number of 1 in a Binary

    I will have the mp3 files my customer buys on a wordpress page and a cart will direct them to that page.
    AWS Training USA
    If I want the mp3 files to be downloaded by the customer is there any reason to protect them except to keep them from being indexed by a search engine? Do I need to have a key or do a get operation other than have server-side encryption in S3?

    Very useful article, if I run into challenges along the way, I will share them here.

    Grazie,
    Irene Hynes

    ReplyDelete
  8. Salama Aleikum,

    This is indeed great! But I think perhaps you are generally referring Left Rotation of String which is getting unsustainable.

    As far as all my research has led me to conclude, AWS only has one service that supports websocket protocol for pushing data straight to browsers. SNS solely supports mobile. IoT supports websocket over MQTT, albeit awkwardly, requiring you to treat ephemeral browser sessions like devices. AWS Training USA . Some libraries to abstract this awkward fit have popped up.

    Very useful post !everyone should learn and use it during their learning path.

    MuchasGracias,
    Preethi.

    ReplyDelete
  9. Greetings Mate,


    11/10!! Your blog is such a complete read. I like your approach with No. 20 - Number of 1 in a Binary. Clearly, you wrote it to make learning a cake walk for me.

    When you save a role in the AWS Management Console with a Display Name and a Color, if the color is set to black it doesn't render any lozenge around the role selector, which causes some alignment issues -- the text for Display Name is slightly closer to the collapse arrow. Sometimes it pushes the collapse arrow to the text baseline instead of vertically centered. AWS Training






    I am so grateful for your blog. Really looking forward to read more.


    Obrigado,
    Ajeeth

    ReplyDelete
  10. I appreciate your efforts because it conveys the message of what you are trying to say. It's a great skill to make even the person who doesn't know about the subject could able to understand the subject . Your blogs are understandable and also elaborately described. I hope to read more and more interesting articles from your blog. All the best.
    rpa training in bangalore
    rpa training in chennai
    rpa training in pune
    best rpa training in bangalore

    ReplyDelete
  11. Wow it is really wonderful and awesome thus it is very much useful for me to understand many concepts and helped me a lot. it is really explainable very well and i got more information from your blog.
    microsoft azure training in bangalore
    rpa training in velachery| rpa training in tambaram |rpa training in sholinganallur | rpa training in annanagar| rpa training in kalyannagar

    ReplyDelete
  12. For Python training in Bangalore, Visit:- Python training in Bangalore

    ReplyDelete
  13. Visit for AWS training in Bangalore:- AWS training in Bangalore

    ReplyDelete
  14. I came on the Internet i saw great testimony about DR Voke on how he was able to cure someone from HERPES, and any disease this person said great things about this man, and advice we contact him for any problem that DR Voke can be of help, well i decided to give him a try, he requested for my information which i sent to him, and he told me he was going to prepare for me a healing portion, which he wanted me to take for days, and after which i should go back to the hospital for check up, well after taking all the treatment sent to me by DR Voke i went back to the Hospital for check up, and now i have been confirmed HERPES Negative, friends you can reach Dr voke on any treatment for any Disease, reach him on _________________________________[doctorvoke@yahoo.com]

    ReplyDelete