Learn Computer Science programming - C# and C++ Algorithms

 
Number of set bits inside an integer.

Given an integer, can you determine how many bits are set?
Code
 
Using the AND bit shifting, you can shift the integer you are trying to measure the number of bits. For example, take the number 00000101. The rightmost bit is 1. Add 1 to your count, then shift the integer to become 00000010. The rightmost is 0. Shift right again and the integer becomes 00000001. Add another 1 to your count and you get 2 count. Now the integer becomes 0000000. You're done!

Pseudo-Code
  Start with a count = 0
  While the integer is NOT zero
  If the integer AND 1 equals 1, increment count
  Shift the integer 1 bit to the right
  Return count

 Int NumOfOnesInByte (unsigned int number)
  {
  Int numOnes = 0;
  While (number){
  If (number & 1)
  numOnes++;
  number = number >> 1;
  }
  return numOnes;
  }
 
The above code running time is O(n), representing the worst case possible if all were ones. A better solution would be to subtract 1.

Example:

Subtracting 1 from 0111 0000 = 0110 1111 (reverses all the low bit numbers). The equation of 0111 000 - (0111 0000 -1) = 0110 0000 which would be equal to 0111 0000 & 0110 0000 = 0110 0000. Number = Number & (Number -1). The running time is O(m) here m is the number or 1s in the byte. This more efficient.

Int NumOfOnesInByte (unsigned int number)
{
Int numOnes = 0;
While (number){
If (number & 1)
numOnes++;
number = number & (number -1);
}
return numOnes;
}

Negative numbers

If the value passed is an integer, the last leftmost bit that gets inserted is 1 rather than zero. This can be dealt with by insuring reading an unsigned integer only.