Complexity= O(n)

int numOfOnes(int n){

int count=0;

while(n!=0){

if((n & 1) == 1)

count++;

n=n>>>1;

}

return count;

}

Method 2:

The method works as follows:

The operation:

n=n&(n-1)

resets the last set bit of n.

So the number of time the above operation can be done before n is equal to 0 are the number of set bits in n originally.

Complexity= O(m) where m is the number of set bits in n.

int numOfOnes2(int n){

int count=0;

while(n!=0){

n=n&(n-1);

count++;

}

return count;

}

Also note that if count above is 1, then number n is a power of 2.

## No comments:

Post a Comment