Why an expression instead of a constant, in a C for-loop's conditional?
CFor LoopCoding StyleExpressionConstantfoldingC Problem Overview
In many programming competitions I have seen people write this type of for
-loop
for(i = 0; i < (1 << 7); i++)
Unless I am missing something, that's the same as
for(i = 0; i < 128; i++)
Why use the (1 << 7)
version?
Isn't calculating the condition every time an unnecessary overhead?
C Solutions
Solution 1 - C
Yes, they are equivalent in behavior.
>Then why do people use the (1 << 7) version?
I guess, they use it to document it is a power of 2.
>Calculating the condition every time must be an overhead! I am unable to find the reason behind this!
Not really, any normal compiler will replace 1 << 7
by 128
and so both loops will have the same performances.
>(C11, 6.6p2) "A constant expression can be evaluated during translation rather than runtime, and accordingly may be used in any place that a constant may be."
Solution 2 - C
Let's translate each one of these options into plain English:
for(i = 0; i < (1 << 7); i++) // For every possible combination of 7 bits
for(i = 0; i < 128; i++) // For every number between 0 and 127
Runtime behavior should be identical in both cases.
In fact, assuming a decent compiler, even the assembly code should be identical.
So the first option is essentially used just in order to "make a statement".
You could just as well use the second option and add a comment above.
Solution 3 - C
1 << 7
is a constant expression, the compiler treats it like 128
, there's no overhead in run time.
Without the loop body, it's hard to say why the author uses it. Possibly it's a loop that iterates something associated with 7 bits, but that's just my guess.
Solution 4 - C
>Then why do people use the (1 << 7) version?
It is a form of documentation, it is not a magic number but 2^7
(two to the seventh power) which is meaningful to whomever wrote the code. A modern optimizing compiler should generate the exact same code for both examples and so there is no cost to using this form and there is a benefit of adding context.
Using godbolt we can verify this is indeed the case, at least for several versions of gcc
, clang
and icc
. Using a simple example with side effects to ensure that the code is not totally optimized away:
#include <stdio.h>
void forLoopShift()
{
for(int i = 0; i < (1 << 7); i++)
{
printf("%d ", i ) ;
}
}
void forLoopNoShift()
{
for(int i = 0; i < 128; i++)
{
printf("%d ", i ) ;
}
}
For the relevant part of the code we can see they both generate the following see it live:
cmpl $128, %ebx
What we have is an integer constant expression as defined in the draft C11 standard section 6.6
Constant expressions which says:
>An integer constant expression117) shall have integer type and shall only have operands that are integer constants, enumeration constants, character constants, sizeof expressions whose results are integer constants,[...]
and:
>Constant expressions shall not contain assignment, increment, decrement, function-call, or comma operators, except when they are contained within a subexpression that is not evaluated.115)
and we can see that a constant expression is allowed to be evaluated during translation:
>A constant expression can be evaluated during translation rather than runtime, and accordingly may be used in any place that a constant may be.
Solution 5 - C
> for(i = 0; i < (1 << 7); i++)
and
> for(i = 0; i < 128; i++)
gives same performance but developer can take huge advantage in case for(i = 0; i < (1 << 7); i++) is used in a loop as
for(int k = 0; k < 8; k++)
{
for(int i = 0; i < (1 << k); i++)
{
//your code
}
}
Now it is in the inner loop upper limit i.e. (1 << k) changes with power of 2 runtime. But it is applicable if your algorithm requires this logic.
Solution 6 - C
The compiler outputs the same code for both cases. you probably want to use different forms depending on the context.
- You can use
NUM_STEPS
orNUM_ELEMENTS_IN_NETWORK_PACKET
when it's a constant part or a design choice in your algorithm that you want to make clear. - Or you can write
128
, to make clear it's128
, a constant. - Or write
1 << 7
if you're at a competition and the test said something like "run it 2^7 times".
Or, you can be showing off that you know bit operations!
In my humble opinion, programming is like writing a letter for two people, the compiler and the person that will have to read it. What you're meaning should be clear for both.
Solution 7 - C
It's evaluated by the preprocessor since both operands are constant.
But if you're going to use the number instead of the bit shift shouldn't it be 0x0100?