Number of ones to the left of every zero in binary representation

Question

I am seeking the computationally fastest way to determine the total number of ones to the left of every zero in the binary representation of a number. That is: for every zero, count the number of ones that are to the left of it, and then total the counts.

For example:

75 => {1, 0, 0, 1, 0, 1, 1}

{1}
{1}
{1, 1}

Total = 4

I wish to do this programmatically but my attempts are slow and feel inefficient. Is there some clever method I might use?

Answer 1

Go through the number from left to right, keeping track of how many ones you have seen yet. When you see a zero, add the number of ones-so-far to an accumulator.

Answer 2

I think the following is about as fast as you can get in C, without using look-up tables:

int CountOnes (unsigned int n)
  {
  int nZeroes = 0 ;
  int summedOnes = 0 ;
  while (n)
    {
    if (n & 1) summedOnes += nZeroes ;
    else nZeroes++ ;
    n >>= 1 ;
    }
  return summedOnes ;
  }