**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