Queer! right-shifting more than a type's width

[Nick Patavalis]

Ok, what is this supposed to print:

#include <stdio.h>
#include <stdint.h>

int
main (void)
{
uint32_t r, s;

s = 33;
r = (uint32_t)1 << s;
printf("r = %u\n", r);

return 0;
}

I have been programming in C for several years (and doing a lot of
low-level stuff that require bit manipulations) but this I didn't
expect!!!!

It turns out that the number printed is "2"!!!

How on earth is the "<<" operator defined? It is certainly not defined
as a shift, neither as a "multiplication". I'm totally confused!

/npat

[Ben Pfaff]

Nick Patavalis <np**@efault.net> writes:

uint32_t r, s;

s = 33;
r = (uint32_t)1 << s;

Behavior of << and >> is undefined when the right operand is
greater than or equal to the width of the left operand. See
C99 6.5.7#3.
--
Ben Pfaff
email: bl*@cs.stanford.edu
web: http://benpfaff.org

[Gordon Burditt]

>Ok, what is this supposed to print:

There is nothing that this is *NOT* supposed to print.
Invoking undefined behavior allows any behavior at all.

#include <stdio.h>
#include <stdint.h>

int
main (void)
{
uint32_t r, s;

s = 33;
r = (uint32_t)1 << s;
Shifting by more than the width of the type invokes the
wrath of undefined behavior.
printf("r = %u\n", r);

return 0;
}

I have been programming in C for several years (and doing a lot of
low-level stuff that require bit manipulations) but this I didn't
expect!!!!

It turns out that the number printed is "2"!!!
If you've ever looked at the definitions of shift instructions in
assembly language (i386 in particular, but it's not the only one
like this), you might notice that some of those involving a variable
shift count (usually in a register) only pay attention to a limited
number of bits in that register. After all, there's not much point
in actually shifting an integer 1073741824 times, and it's likely
to lock out interrupts for way too long.

If a << b is implemented as a << (b % 32) where a is a
32-bit integer, you get the observed behavior.
How on earth is the "<<" operator defined? It is certainly not defined
as a shift, neither as a "multiplication". I'm totally confused!

It is not defined at all when you hand it numbers out of range.

Gordon L. Burditt

[Nick Patavalis]

On 2004-08-09, Gordon Burditt <go***********@burditt.org> wrote:

If you've ever looked at the definitions of shift instructions in
assembly language (i386 in particular, but it's not the only one
like this), you might notice that some of those involving a variable
shift count (usually in a register) only pay attention to a limited
number of bits in that register. After all, there's not much point
in actually shifting an integer 1073741824 times, and it's likely
to lock out interrupts for way too long.

If I remember correctly, it is not the same for ARMs (which I have
been dealing with recently). In this architecture shifting more than
the width of the register will give you zero. I'm not sure though, and
I don't have th ARM-ARM at nearby.

But of course you 're right: It is an undefined behavior in any
case. What makes things more "peculiar" is that two very similar
programs might behave very differently even when compiled for the same
architecture. When I first observed this, the program was doing
something like this:

#define cond(fc) if ( (1UL << (fc)) & (mask) )
#define cond_enable(fc) do { mask |= 1UL << (fc); } while (0)
#define cond_disable(fc) do { mask &= ~(1UL << (fc)); } while (0)

.... several conditions were defined ....

#define NEVER 32
#define C1 1
#define C2 2
#define C3 NEVER
#define C4 4

.... and springled inside the code stuff like this ....

cond(C1) { printf("This only if C1 is enabled\n"); }
cond(C3) { printf("This never\n"); }

It worked fine, until someone decided to use variables for the
condition-bits, instead of constants:

int c5 = 5;
int c6 = 6;
int c7 = 7;
...
c6 = NEVER
...
cond(c6) { printf("This never\n"); }

I think you 're getting the picture.

Anyway thanks for your reply (all of you).
/npat

[Daniel Haude]

On Mon, 9 Aug 2004 07:11:50 +0000 (UTC),
Nick Patavalis <np**@efault.net> wrote
in Msg. <sl*****************@gray.efault.net>

But of course you 're right: It is an undefined behavior in any
case. What makes things more "peculiar" is that two very similar
programs might behave very differently even when compiled for the same
architecture.

Exactly that's what undefined behavior is all about, which is why it is to
be avoided like the plague. You need not even compare "very similar"
progams; one and the same program might behave differently when run
repeatedly.

--Daniel

--
"With me is nothing wrong! And with you?" (from r.a.m.p)

[Joe Wright]

Nick Patavalis wrote:

Ok, what is this supposed to print:

#include <stdio.h>
#include <stdint.h>

int
main (void)
{
uint32_t r, s;

s = 33;
r = (uint32_t)1 << s;
printf("r = %u\n", r);

return 0;
}

I have been programming in C for several years (and doing a lot of
low-level stuff that require bit manipulations) but this I didn't
expect!!!!

It turns out that the number printed is "2"!!!

How on earth is the "<<" operator defined? It is certainly not defined
as a shift, neither as a "multiplication". I'm totally confused!

How many years is several? Can you imagine any association between
Shift and Rotate? Clearly (not?) 'r = (uint32_t)1 << 31' is the
widest shift you can expect to work in C.

00000000 00000000 00000000 00000001

...becomes..

10000000 00000000 00000000 00000000

Wider is Undefined Behaviour. Having said that, if shifting 32
wraps, yielding the original pattern..

00000000 00000000 00000000 00000001

...and shifting 33 yields..

00000000 00000000 00000000 00000010

...I, for one, would not be totally confused.
--
Joe Wright mailto:jo********@comcast.net
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---

[Nick Patavalis]

On 2004-08-10, Joe Wright <jo********@comcast.net> wrote:

How many years is several? Can you imagine any association between
Shift and Rotate?

I can, but what we're witnessing is definitely *not* a rotate.
Clearly (not?) 'r = (uint32_t)1 << 31' is the
widest shift you can expect to work in C.

I understand that this is how left-shift is *defined*. But it could
easily be defined having shifts larger than the type-width result to
zero. Come to think of it, this is what happens with
constants. Actually your example is *wrong*:

r = (uint32_t)1 << 31

yields:

00000000 00000000 00000000 00000001

while, all of the following:

r = (uint32_t)1 << 32
r = (uint32_t)1 << 33
r = (uint32_t)1 << 34

yield

00000000 00000000 00000000 00000000

The 'problem' appears *only* when the code is written like this:

s = 32;
r = (uint32_t)1 << s;

And what really happens, is that the compiler simply emits the
architecture's left-shift instruction (*not* the rotate instruction),
regardless of the value of "k". The problem is that for *some* 32bit
architectures the left-shift instruction only considers bits bit 4:0
of the register-operand, and *this* explains the behavior
observed. For other architectures the shifter ORs the remaining
operand-register bits together, and if the OR's result is non-zero, it
zeroes the shift's result (guaranteeing this way a more "consistent"
behavior).

The compiler is allowed to *simply* emit the architectural shift
instruction, because the standard explicitly makes shifts more than
the type-width undefined.

In the examples above (with the literals), the compiler has to emit no
shift instructions whatsoever; it simply performs the shift
*internally*. And it this case it does it using the "consistent" way.

/npat

[Keith Thompson]

Nick Patavalis <np**@efault.net> writes:

On 2004-08-10, Joe Wright <jo********@comcast.net> wrote:

How many years is several? Can you imagine any association between
Shift and Rotate?

I can, but what we're witnessing is definitely *not* a rotate.

Clearly (not?) 'r = (uint32_t)1 << 31' is the
widest shift you can expect to work in C.

I understand that this is how left-shift is *defined*. But it could
easily be defined having shifts larger than the type-width result to
zero. Come to think of it, this is what happens with
constants. Actually your example is *wrong*:

r = (uint32_t)1 << 31

yields:

00000000 00000000 00000000 00000001

Are you showing the high-order bit at the far right? The
result of (uint32_t)1 << 31 is 0x80000000 or

10000000 00000000 00000000 00000000

in normal binary (high bit first) notation.

[...] The compiler is allowed to *simply* emit the architectural shift
instruction, because the standard explicitly makes shifts more than
the type-width undefined.

More than or equal to.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Nick Patavalis]

On 2004-08-10, Keith Thompson <ks***@mib.org> wrote:

Nick Patavalis <np**@efault.net> writes:

r = (uint32_t)1 << 31

yields:

00000000 00000000 00000000 00000001
Are you showing the high-order bit at the far right?

No intel has not deranged my mind *that* much :) this is just a typo.
The result of (uint32_t)1 << 31 is 0x80000000 or

10000000 00000000 00000000 00000000

in normal binary (high bit first) notation.

Obviously!
[...]

The compiler is allowed to *simply* emit the architectural shift
instruction, because the standard explicitly makes shifts more than
the type-width undefined.

More than or equal to.

Once more I stand corrected.

Thanks for your corrections.
/npat