## 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.

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

2. Very much useful article. Kindly keep blogging

Java Training in Chennai

Java Online Training India

3. 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

4. Great Article Cloud Computing Projects

Networking Projects

Final Year Projects for CSE

JavaScript Training in Chennai

JavaScript Training in Chennai

The Angular Training covers a wide range of topics including Components, Angular Directives, Angular Services, Pipes, security fundamentals, Routing, and Angular programmability. The new Angular TRaining will lay the foundation you need to specialise in Single Page Application developer. Angular Training

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

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

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

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.

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

6. simply we can write it as

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

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

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.

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.

Ajeeth

10. Hmm, it seems like your site ate my first comment (it was extremely long) so I guess I’ll just sum it up what I had written and say, I’m thoroughly enjoying your blog. I as well as an aspiring blog writer, but I’m still new to the whole thing. Do you have any recommendations for newbie blog writers? I’d appreciate it.
Advanced AWS Jobs Interview questions and answers |Best Top 110 AWS Interview Question and Answers – india

11. Hmm, it seems like your site ate my first comment (it was extremely long) so I guess I’ll just sum it up what I had written and say, I’m thoroughly enjoying your blog. I as well as an aspiring blog writer, but I’m still new to the whole thing. Do you have any recommendations for newbie blog writers? I’d appreciate it.
Advanced AWS Training in Bangalore | Best Amazon Web Services Training Institute in Bangalore
Advanced AWS Training Institute in Pune | Best Amazon Web Services Training Institute in Pune
Advanced AWS Online Training Institute in india | Best Online AWS Certification Course in india
AWS training in bangalore | Best aws training in bangalore

12. 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

13. 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

14. Thanks for splitting your comprehension with us. It’s really useful to me & I hope it helps the people who in need of this vital information.
Best Devops training in sholinganallur
Devops training in velachery
Devops training in annanagar
Devops training in tambaram

15. Thanks you for sharing this unique useful information content with us. Really awesome work. keep on blogging
Best Devops online Training
Online DevOps Certification Course - Gangboard

16. This is a nice article here with some useful tips for those who are not used-to comment that frequently. Thanks for this helpful information I agree with all points you have given to us. I will follow all of them.
python Course in Pune
python Course institute in Chennai
python Training institute in Bangalore

17. Thank you for taking the time to provide us with your valuable information. We strive to provide our candidates with excellent care and we take your comments to heart.As always, we appreciate your confidence and trust in us
python Course in Pune
python Course institute in Chennai
python Training institute in Bangalore

18. I am looking for and I love to post a comment Python training in punethat "The content of your post is awesome" Great work!

19. For Python training in Bangalore, Visit:- Python training in Bangalore

20. Visit for AWS training in Bangalore:- AWS training in Bangalore

21. Wow it is really wonderful and awesome thus it is veWow, it is really wonderful and awesome thus it is very much useful for me to understand many concepts and helped me a lot.

oracle dba training in bangalore

oracle dba courses in bangalore

oracle dba classes in bangalore

oracle dba training institute in bangalore

oracle dba course syllabus

best oracle dba training

oracle dba training centers

22. This is the exact information I am been searching for, Thanks for sharing the required infos with the clear update and required points. To appreciate this I like to share some useful information.

perl training institutes in bangalore

perl training in bangalore

best perl training institutes in bangalore

perl training course content

perl training interview questions

perl training & placement in bangalore

perl training center in bangalore

23. It is very good and useful for students and developer.Learned a lot of new things from your post Good creation,thanks for give a good information at sap crm.

mysql dba training in bangalore

mysql dba courses in bangalore

mysql dba classes in bangalore

mysql dba training institute in bangalore

mysql dba course syllabus

best mysql dba training

mysql dba training centers

24. I just loved your article on the beginners guide to starting a blog.If somebody take this blog article seriously in their life, he/she can earn his living by doing blogging.thank you for thizs article. pega online training , best pega online training ,
top pega online training

25. Enjoyed reading this article throughout.Nice post! Digital Marketing is the trendy course right now and is going to be in
a great demand in near future as jobs for this domain will be sky rocketted.To be on par with the current trend we have to
gain complete knowledge about the subject. For the complete course online
360Digitmg Digital Marketing Course

26. 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]

27. Thanks for Sharing This Article.It is very so much valuable content. I hope these Commenting lists will help to my website
devops online training
best devops online training
top devops online training

28. Its really an Excellent post. I just stumbled upon your blog and wanted to say that I have really enjoyed reading your blog. Thanks for sharing....
pega Training in Bangalore

29. Thanks for posting the best information and the blog is very helpful.digital marketing institute in hyderabad