Saturday, January 17, 2015

Number of ones in the binary representation of a number


Write a function that takes in an integer and returns the number of ones set in the binary representation.
This problem looks very easy. The way we do it is to compare the number  with 1 and left shift the number until it reaches zero.
Yeah...
But what about negative number? It is always less than zero.

The trick is, every negative number XOR with -1 will gives its positive counterpart less one (LO). For example, -123 ^ -1 = 122, -1 ^ -1 = 0. Since -1 has 32 ones, so the number of ones in any negative number is the number of zeros in LO. For example, the number of ones in -123 is the number of zeros in 122. So we only need to convert the negative number into its LO, then we can use the old method for positive integers.


public static int countOnes(int n) {
  if (n == 0)
   return 0;
  if (n == -1)
   return 32;
  int count = 0;
  boolean isNegative = false;
  if (n < 0) {
   isNegative = true;
   n = (-n) - 1;
  }
  while (n > 0) {
   if ((n & 1) == 1)
    count++;
   n = n >> 1;
  }
  return isNegative? 32 - count : count;
 }

No comments:

Post a Comment