Do these two bit-counting algorithms have the same time complexity?

Question

Below is an algorithm I picked up somewhere (forgot where exactly, possibly from this answer) to calculate the amount of bits set in an integer, i.e. its Hamming weight.

function hamming_weight($i)
{
    $i = $i - (($i >> 1) & 0x55555555);
    $i = ($i & 0x33333333) + (($i >> 2) & 0x33333333);
    return ((($i + ($i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

(I happened to have it handy in PHP, but this could really be any language.)
If I'm not terribly mistaken, this runs in O(1) - there's no branches after all.

Now here's a bit-counting function I wrote myself, which apart from readability I deem inferior:

function hamming_weight_2($i)
{
    $weight = 0;
    for ($k = 1, $s = 0; $k < 0xFFFFFFFF; $k *= 2, $s++)
    {
        $weight += (($i & $k) >> $s);
    }
    return $weight;
}

However, in what way is it inferior? At first I thought "well there's a loop, so this should run in linear time", but then I realized the loop doesn't depend on the size of the input at all. No matter the size of $i, the number of iterations stays the same.

What I'm thus wondering is this:

• Can these two alogrithms really be said to both run in O(1)?
• If so, is there a measure that distinguishes the two? It seems the first one ought to be better in some way.

Answer 1

In this case, looking at the question in terms of big O complexity doesn't make sense because there are a fixed number of bits in your variable. Instead you should count the individual operations:

Algorithm 1:

• Bitwise Ands: 4
• Bitshifts: 4
• Additions/Subtracts: 3
• Multiplications: 1

Algorithm 2:

• Bitwise Ands: 32
• Bitshifts: 32
• Additions/Subtracts: 64
• Multiplications: 32

Even allowing for replacing those multiplications with additional bitshifts, significantly more work is being done in the second algorithm.

Answer 2

Can these two algorithms really be said to both run in O(1)?

Absolutely, yes. Any algorithm that runs in under a fixed amount of time independently of the size of its input can be said to be O(1).

If so, is there a measure that distinguishes the two? It seems the first one ought to be better in some way?

What distinguishes algorithms with identical asymptotic complexity is a constant factor. This applies to algorithms of any asymptotic complexity, not only O(1) algorithms.

You can figure out the constant by adding up the elementary operations required to perform the computations according to these algorithms. Count operations performed outside a loop, and add the count of operations inside the loop multiplied by the number of times that loop will be executed in the worst case (i.e. 32).

While the two algorithms have identical asymptotic complexity, the first algorithm is said to have a much smaller constant factor, and is, therefore, faster than the second one.

Answer 3

f (n) = O (g (n)) means that f (n) is less than or equal to c * g (n) for all n ≥ N for some N > 0 and for some c > 0. The c component can be important. If one algorithm runs in n nanoseconds and another runs in n hours, they both have the same time in Big-O notation but one is just slightly (a few thousand billion times) faster. Not something to be concerned about, obviously. Scarcely any difference.

PS. It is rarely important to count the number of bits in a single word. For counting the bits in an array of words, both algorithms are sub-optimal.

Answer 4

Well, it depends. Note that neither of them are actually algorithms, they're implementations. That's different, since in implementation you always have a constant number of bits. Yes, always - bigints are also limited by a constant, because array size is limited by a constant. Clearly it's useless to think that way though.

So let's look at it differently. First, consider the conceptual algorithms instead of the implementations. Integers are now n bits long, and the code you showed is generalized to their n-bit forms. The first one would have O(log n) steps vs O(n) for the second. But how long do those steps take? It depends on your abstract machine. It is a stackoverflow tradition to pretend that the only abstract machine in "existence" (in the platonic sense) is the RAM machine, or maybe the Turing machine. But there are more. PRAM for example, in which you are not necessarily limited to a constant number of parallel processing elements.

n-bit addition takes O(log n) time on a PRAM machine with sufficient processors (so, at least n), bitwise operations obviously only take O(1) on a PRAM machine with at least n processors, so that gives you O(log(n)²) for the first algorithm but O(n log n) for the second.

But you can go even further, and assume all operations on n bits take constant time. I'm sure someone will comment that you can't do that, but you can actually assume whatever you want (look up hypercomputation in particular). The usual assumption that operations on O(log n) bits take constant time is pretty weird too if you think about it. Anyway if "n-bit operations are O(1)" is what you're working with, that's O(log n) for the first algorithm and O(n) for the second.