Monday 18 January 2016

Calculate the number of 1’s in the binary representation of a number

Number of 1’s in the binary representation of a number

Complexity of the algorithm is O(Number of 1's).
bitcount(n):
count = 0
while n > 0:
            count = count + 1
            n = n & (n-1)
return count


In worst case (when the number is 2^n - 1, all 1's in binary) it will check every bit.

public class BitCount {
     public static void main(String[] args) {

           int number = 15;
           int count = 0;
           while(number>0) {
                number = number & (number-1);
                count++;
           }
           System.out.println("Number of 1s are: "+count);
     }
}

Output:
Number of 1s are: 4

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...