CODEWITHSUNDEEP
c++
bodacydo
bodacydo

Reputation: 79509

Bitwise AND and order of operations in C/C++

I'm currently dissecting through the ol' Doom engine source code, and came across an interesting line:

counter = (++counter)&(MAX_VALUE-1);

It looks like a way to increment a counter without going over a certain number, but I have a tricky time doing bitwise operations in my head, so I whipped up a quick console project to try this out, and lo and behold, it works beautifully.

I deduce the above way is more efficient than an if() statement, especially if the code is executed rapidly, for example, within a loop, where performance within a real-time game is crucial.

I'm trying to figure out the order of operations the compiler uses to execute this line. If the increment '++' operator is placed after the 'counter', it will always remain zero. It only works if the increment is used as a prefix ("++counter"), but even still, if I write it out with pen and paper, I get the arbitrary result of the bitwise AND operation, not a counter that increments.

It seems the bitwise operation is calculated, and then the increment is performed, but I'm stumped figuring out why, any ideas?

Upvotes: 0

Views: 625

Answers (2)

alain
alain

Reputation: 12057

The formula

counter = (++counter)&(MAX_VALUE-1);

has undefined behaviour, see CoryKramer's answer.

The formula

counter = (counter + 1)&(MAX_VALUE - 1);

works only for MAX_VALUEs that are equal to a power of 2. Only then the value MAX_VALUE - 1 has this form in binary:

000...000111...111

When such a value is used in a AND operation, it "truncates" the higher bits of the other value, and has the effect of wrapping around when the other value reaches MAX_VALUE.

I think the normal modulo operation is just as fast on modern hardware, and does not have the restriction mentionend above:

counter = (counter + 1)%MAX_VALUE;

Upvotes: 0

Cory Kramer
Cory Kramer

Reputation: 118001

While the parentheses have higher precedence than operator ++ or bitwise AND (operator &), there are no defined sequence points in your right-hand side. So your code exhibits undefined behavior.

If you remove the operator++ what this is intending to do is

(counter + 1)&(MAX_VALUE-1);

If you consider MAX_VALUE to be 32 then MAX_VALUE-1 in binary is

11111

So if you have a larger value than that and use & any bits left of bit 5 (from the right) will be cleared

0000011111   // assume this is MAX_VALUE - 1 
1100110110   // assume this is counter + 1
__________
0000010110

The result would be true if any of the bits less than or equal to MAX_VALUE - 1 were 1.

Upvotes: 1

Related Questions