analyzing this algorithm (big-o)

Question

Problem

What is this algorithm doing? What does 0x01 represent? What does it mean that m = m >> 1 within the inner while loop? What is this algorithm big-O of?

while(n>0)
{
     m = n;
     while(m)
     {
          if(m & 0x01)
          {
                c++;
          }
          m = m >> 1;
     }
}

Attempt

1. By looking @ the algorithm, I understand that m is right-shifted one place.
   (E.g., if m = 1010, m >> 1 = 0101. Is that correct?)

2. Because there is a nested while loop, and because each while iterates n time, my guess is that this algorithm is O(n^2). Is that correct?

Answer 1

What is this algorithm doing? For a value of n, the number of bits that are on in n is added to c.

0x01 represents the value 1. It is being used as a bit mask to check whether the lowest bit of m is on. If it is, then it increments c. This is the bit-counting part. Then, m is right-shifted once to move the next bit down into the position of LSB (least significant bit). The while(m) will stop once m is equal to 0; that is, when m has no more bits on.

And the algorithmic complexity depends on what you're doing with n. If you're decrementing it, then your algorithm is O(n) since the inner section (the while(m)) is constant (since there is a maximum number of bits in an integer, and that is probably 32).

The complexity is probably O(n * 32), but since constants are taken out of Big-Oh notation, you end up with O(n).

Answer 2

The inner loop is counting the number of "1" bits in m. Its cost is O(log m) because every iteration it's halving the value of m, until it reaches 0.

(If you consider m to be an integer of fixed size, say, 32 bits, then you could say the inner loop is O(1) because it always makes at most 32 operations which is a constant number)

The outer loop, as some have pointed out, never finishes because n never changes. (unless n is 0).

So overall this code is O(infinity), it never finishes.

Answer 3

Well... for one thing, this function will actually never exit. The while( n > 0 ) at the start will remain constantly true, because 'n' is never modified within the loop. So that'll be a problem if you try to run it.

But to answer your questions:

The m & 0x01 will basically check to see if 'm' is an odd number. It does this by doing a bitwise operation between m and 0x01. The value 0x01 is a hexidecimal representation of the value 1. Doing an & operation between them will cause each bit to be compared against one another (in binary), and set to 1 if and only if both matching bits have a value of one. For more information one that, do some research on binary and hexidecimal representations, and the bitwise operators.

The >> is another bitwise operator which shifts all the bits in a value by one spot. In the decimal world, that's equivalent to dividing by 2. So that line is causing the value of m to be divided by two each time it gets to that line of code. There is a mirror operator of << for shifting the bits in the opposite direction, and equates to multiplying by 2 instead.

Hope this helps!