Brute force method to count number of 1's in given number is to iterate through each bit and check if it is 1, then increment counter. But it will take 32 checks (assuming 32 bit number).
Can we do better? Is there any way by which we don't need to check all bits? What if we iterate as many times as numbers of 1's. To achieve it, we have to remove 1 from number at each iteration, then only at last when no one is remaining in number, we can stop.
Can we do better? Is there any way by which we don't need to check all bits? What if we iterate as many times as numbers of 1's. To achieve it, we have to remove 1 from number at each iteration, then only at last when no one is remaining in number, we can stop.
Manipulation of bits in number is only solution to reduce iteration. By doing x-1, we can eliminate last 1 from given number but it will introduce tailing 1's in number. But those should be not an issue for us. Because we have AND weapon to get rid of all tail 1's.
Following is implementation of above algorithm in c language.
Please write comments if you find anything wrong or you want to add something more related to this topic.
No comments:
Post a Comment
Write your comment here.