0

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?

Mr.Wizard
  • 802
  • I may be missing something here but doesn't this problem simplify to the number of ones to the first zero. If not edit your question to include a counter example. In case I have misunderstood the question. Otherwise just start at the beginning moving along till you find the the first zero digit (or get to the end) then keep going to the end counting the number of ones as you go. This would be a simple loop with one iteration for each digit. – Warren Hill Aug 24 '13 at 10:35
  • @Warren The answers below describe how to perform the operation I was seeking; perhaps they do better to clarify my intent that I could rephrasing. The problem is really a very simple one but I couldn't think last night. – Mr.Wizard Aug 24 '13 at 17:22

2 Answers2

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.

hmakholm left over Monica
  • 286,031
1

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 ;
  }
TonyK
  • 64,559