The result of 1 << 32

[mrby]

All,

Here is one question that I can not understand.

int main()
{
int i = 32;
printf("%p %p\n", 1<<i, 1<<32);
}

The result is:
0x1 0x0

("int" type on my machine is 32-bit)

Why 1<<i and 1<<32 get different result? I had thought
both of them would get 0x0.

 

[Jordan Abel]

All,

Here is one question that I can not understand.

int main()
{
int i = 32;
printf("%p %p\n", 1<<i, 1<<32);
}

The result is:
0x1 0x0

("int" type on my machine is 32-bit)

Why 1<<i and 1<<32 get different result? I had thought
both of them would get 0x0.

A theory: the 1<<32 is calculated at compile time [and the compiler
itself is smart enough to do this] while the 1<<i value is
calculated at runtime - now, if your processor's LSH instruction
only accepts a 5-bit immediate operand.

According to the standard, shifting by a number greater than or
equal to the field width is undefined.

A.6.2 Undefined Behavior

* An expression is shifted by a negative number or by an amount
greater than or equal to the width in bits of the expression
being shifted (§3.3.7).

 

[mrby]

You explanation makes sense! I do appreciate it.

 

[Netocrat]

All,

Here is one question that I can not understand.

int main()
{
int i = 32;
printf("%p %p\n", 1<<i, 1<<32);
}

The result is:
0x1 0x0

("int" type on my machine is 32-bit)

Why 1<<i and 1<<32 get different result? I had thought
both of them would get 0x0.

A theory: the 1<<32 is calculated at compile time [and the compiler
itself is smart enough to do this] while the 1<<i value is

So you're assuming wrap-around, which is reasonable but not the only
possibility. As you quoted from the standard, this is undefined behaviour
- all bets are off and any result's possible.

To add to that, the printf format specifier used is that of a pointer. It
should be %d.

[...]

 

[Jordan Abel]

All,

Here is one question that I can not understand.

int main()
{
int i = 32;
printf("%p %p\n", 1<<i, 1<<32);
}

The result is:
0x1 0x0

("int" type on my machine is 32-bit)

Why 1<<i and 1<<32 get different result? I had thought
both of them would get 0x0.

A theory: the 1<<32 is calculated at compile time [and the
compiler itself is smart enough to do this] while the 1<<i value
is

So you're assuming wrap-around, which is reasonable but not the
only possibility. As you quoted from the standard, this is
undefined behaviour - all bets are off and any result's possible.

I was giving a possible reason why this might have happened.
"Because it's undefined" isn't an answer. Things do happen for a
reason - there's a reason the value was 1 instead of 42 or
0xdeadbeef or crashing or starting up a game of nethack. The
standard gives a lot of latitude, but compiler authors tend not to
be as capricious as they could be. It's also a possible reason why
this was allowed to be undefined, rather than mandating one
particular behavior or another.

To add to that, the printf format specifier used is that of a
pointer. It should be %d.

oops, didn't notice that part

[...]

 

[Mark McIntyre]

I was giving a possible reason why this might have happened.
"Because it's undefined" isn't an answer.

Its a good idea to explain whats going on. However I find it better to
do it the other way round:

"This is undefined behaviour, which means your compiler isn't actually
required to handle it sensibly. Typically however compiler writers
will implement wrap-around or..."

This ensures your audience learn /first/ that its UB and naughty,
/then/ about how it might be handled. This avoids the risk that they
leave after para 1, and think that /all/ compilers implement
wraparound.

 

[Richard Tobin]

"This is undefined behaviour, which means your compiler isn't actually
required to handle it sensibly. Typically however compiler writers
will implement wrap-around or..."

This ensures your audience learn /first/ that its UB and naughty,
/then/ about how it might be handled. This avoids the risk that they
leave after para 1, and think that /all/ compilers implement
wraparound.

I'd like to emphasize Jordan's other point, which you snipped:

Explaining the plausible implementations often (as in this case)
explains why the behaviour is undefined. Understanding that is better
than just knowing that it's undefined.

-- Richard

 

[Walter Roberson]

A theory: the 1<<32 is calculated at compile time [and the compiler
itself is smart enough to do this] while the 1<<i value is
calculated at runtime - now, if your processor's LSH instruction
only accepts a 5-bit immediate operand.

According to the standard, shifting by a number greater than or
equal to the field width is undefined.

I don't have my reference material here, but I seem to recall that
constant calculations are supposed to be done "as if" they were
done at run-time. Possibly that only applied to calculations in
preprocessor expressions.

If my recollection is correct, then even though the shift behaviour
is undefined, would it not be required to be consistant?

 

[Flash Gordon]

A theory: the 1<<32 is calculated at compile time [and the compiler
itself is smart enough to do this] while the 1<<i value is
calculated at runtime - now, if your processor's LSH instruction
only accepts a 5-bit immediate operand.

According to the standard, shifting by a number greater than or
equal to the field width is undefined.

I don't have my reference material here, but I seem to recall that
constant calculations are supposed to be done "as if" they were
done at run-time. Possibly that only applied to calculations in
preprocessor expressions.

If my recollection is correct, then even though the shift behaviour
is undefined, would it not be required to be consistant?

No, the result of undefined behaviour is not required to be consistent.
If undefined behaviour had to be consistent then that would effectively
mean having to detect buffer overruns, otherwise how could it provide
consistent behaviour on the undefined behaviour caused by writing beyond
the end of a buffer?

 

[Jordan Abel]

I don't have my reference material here, but I seem to recall that
constant calculations are supposed to be done "as if" they were
done at run-time. Possibly that only applied to calculations in
preprocessor expressions.

It does not apply to undefined behavior.

If my recollection is correct, then even though the shift
behaviour is undefined, would it not be required to be consistant?

There are no rules which apply to undefined behavior. Were this
unspecified or implementation-defined, that would be true.

 

[Christian Bau]

A theory: the 1<<32 is calculated at compile time [and the compiler
itself is smart enough to do this] while the 1<<i value is
calculated at runtime - now, if your processor's LSH instruction
only accepts a 5-bit immediate operand.

According to the standard, shifting by a number greater than or
equal to the field width is undefined.

I don't have my reference material here, but I seem to recall that
constant calculations are supposed to be done "as if" they were
done at run-time. Possibly that only applied to calculations in
preprocessor expressions.

If my recollection is correct, then even though the shift behaviour
is undefined, would it not be required to be consistant?

"Undefined behavior" includes permission to be inconsistent. If the
hardware produces a random number as a result of trying to calculate 1
<< 32, then the compiler can do the same thing at compile-time.

In many implementations, it would be possible to define the behavior of
x << y for arbitrary values of y. If the implementation defines the
behavior, then it would implement it both at compile time and at runtime
consistently with that definition.

If the hardware behaves consistently, but the implementation doesn't
actually _define_ that behavior, then all bets are off. However, this
could be the source of an incredibly hard to find bug. For example, in x
<< y a compiler might figure out that y always has the same value at a
high enough optimisation level. So in the example

int i = 32;
int result = 1 << i;

a compiler might do a shift at runtime when it is not optimising, and do
a shift at compile time when it is optimising. Good luck finding the bug
if that happens.

 

[Mark McIntyre]

Explaining the plausible implementations often (as in this case)
explains why the behaviour is undefined. Understanding that is better
than just knowing that it's undefined.

.... and if you actually read what I say, you'll see that I am still
advocating supplying both bits of information, as you suggest.

My point was that if you stress first that its UB, then explain likely
implementation-specific solutions, you ensure that newbies leave
knowing they can't rely on it.

I've noticed that undergrad level newbies will read para 1 then doze
off or start to play with their mobe, and so miss the rest of the
Lesson...

 

[Richard Tobin]

... and if you actually read what I say

I did read it, but I still wanted to draw attention to a specific
reason for talking about the implementation.

-- Richard

 

[Mark McIntyre]

I did read it, but I still wanted to draw attention to a specific
reason for talking about the implementation.

okay, we're on the same wavelenth.

 

[Old Wolf]

It does not apply to undefined behavior.


There are no rules which apply to undefined behavior. Were this
unspecified or implementation-defined, that would be true.

It is not true for unspecified behaviour either. The code

foo( f(), g() );

could call f and g in different orders depending on what day
of the week it is.

 

[tedu]

No, the result of undefined behaviour is not required to be consistent.
If undefined behaviour had to be consistent then that would effectively
mean having to detect buffer overruns, otherwise how could it provide
consistent behaviour on the undefined behaviour caused by writing beyond
the end of a buffer?

Are there real examples where it's not consistent? Buffer overruns
generally are, provided the data written is the same in all cases. I'm
curious to learn of any times when one time the daemons come out the
left nostril, and the next time the right, so to speak.

 

[Flash Gordon]

Are there real examples where it's not consistent? Buffer overruns
generally are, provided the data written is the same in all cases. I'm
curious to learn of any times when one time the daemons come out the
left nostril, and the next time the right, so to speak.

I've come across numerous instances where changing the optimisation
level, or a compiler switch, or a line of code somewhere aparantly
completely unrelated has changed the visible effect of undefined
behaviour. I've come across code with undefined behaviour that will
crash 1 run in 10. I've come across instances where the program would
apparantly work when run inside a debugger but not if run standalone.

The thing is that with a lot of applications in the real world things
*don't* happen exactly the same every run.

 

[Chris Torek]

Are there real examples where it's not consistent? Buffer overruns
generally are, provided the data written is the same in all cases.

I assume you mean "generally are consistent". This is true on
some systems and not on others. In particular, systems in which
C programs are run in a "virtual address space" that is initialized
the same way on each run tend to act consistently (which is very
nice for debugging). Those that do not, tend not to.

The same applies to, e.g., use of uninitialized local variables:

#include <stdio.h>

int main(void) {
int i;
printf("uninitialized i = %d\n", i);
return 0;
}

This program tends to produce consistent output (though not always
0) on Unix-like systems, including Linux, but not on old microcomputers
(where the contents of RAM and/or registers on each program launch
tend to depend on what was run before). (But even on Linux, you
may be able to arrange different output from one run to the next,
even without recompiling, by fiddling with dynamic linker options.)

 

[Michael Wojcik]

Are there real examples where it's not consistent?

Sure. I see them all the time. Take a look at documented buffer-
overflow exploits, and you'll see how much effort attackers must go
to in order to assure sufficient consistency of behavior for their
attacks to have a decent chance of succeeding.

Buffer overruns
generally are, provided the data written is the same in all cases.

They most certainly are not. It might be true that over the set of
all extant C programs for which buffer overruns are possible, when
executed with exactly the same inputs (from all sources), where such
inputs lead to a buffer overrun, that in a majority of cases the
behavior is the same.

Even that's a bit dubious, though, and it's a far cry from
"generally".

The behavior on buffer overrun is highly susceptible to environmental
effects and program state in many implementations.

 

[Michael Wojcik]

I assume you mean "generally are consistent". This is true on
some systems and not on others. In particular, systems in which
C programs are run in a "virtual address space" that is initialized
the same way on each run tend to act consistently (which is very
nice for debugging). Those that do not, tend not to.

Even that is excessively optimistic, in my experience. Non-trivial
programs rarely have buffer overruns with identical state from one
execution to another, and so rarely have perfectly consistent
behavior.

In the case of a buffer overrun on a virtual-memory system, for
example, in many (most?) implementations the behavior depends
strongly on whether a page is mapped after the end of the buffer, and
what its permissions are. And that can certainly change from one
execution to another.