Solution: There is an elegant solution with a complexity of O(k) where k is the number of "1". The code is as follow:
int cout_numof1(int n)
{
int cnt = 0;
while(n)
{
n = n & (n-1);
cnt++;
}
return cnt;
}
This is a blog for interview questions. The questions are primarily from certain web forums, BBS or books. The owner of this blog doesn't claim any copyright of those questions. The blog is established primarily to help the blog owner prepare job interviews.
Monday, March 12, 2012
Calculate the Number of "1" in the Binary Form of a Positive Integer
Problem: Given a positive integer, count the number of "1" in its binary form. For example, the binary form of "7" is "111", so the number of "1" is 3.
Solution: There is an elegant solution with a complexity of O(k) where k is the number of "1". The code is as follow:
Solution: There is an elegant solution with a complexity of O(k) where k is the number of "1". The code is as follow:
This function is called population count (popcnt) and it even has its own instruction in many instruction sets. Your implementation is usually suboptimal, even if there is no popcnt instruction in your instruction set.
ReplyDeletehttp://en.wikipedia.org/wiki/Hamming_weight