Left shift

[Christian Christmann]

Hi,

in the header of my class I've a constant

static const int a = ( 1 << 32 ) - 1;

When compiling the code, g++ issues the warning
"warning: left shift count >= width of type"

Why? And how can I get rid of that?

Thank you.
Chris

 

[Noah Roberts]

Hi,

in the header of my class I've a constant

static const int a = ( 1 << 32 ) - 1;

When compiling the code, g++ issues the warning
"warning: left shift count >= width of type"

Why?

Because your implementation's representation of int is apparently < 33
bits.

And how can I get rid of that?

You could try:

static_cast<int>((1L << 32) - 1);

This will work if int is 32 bits.

 

[Frederick Gotham]

Christian Christmann posted:

Hi,

in the header of my class I've a constant

static const int a = ( 1 << 32 ) - 1;

When compiling the code, g++ issues the warning
"warning: left shift count >= width of type"

Why? And how can I get rid of that?

You're either trying to do one of two things:

(1) Set a to 4294967295

(2) Set all bits to zero except the sign bit, then subtract 1. This will have
a different effect on different systems.

 

[Marcus Kwok]

Hi,

in the header of my class I've a constant

static const int a = ( 1 << 32 ) - 1;

When compiling the code, g++ issues the warning
"warning: left shift count >= width of type"

Why? And how can I get rid of that?

You can only shift by (n-1), where n is the number of bits in the type.
For example, suppose an int is 8 bits. Then

1 << 0 == 00000001
1 << 1 == 00000010
1 << 2 == 00000100
1 << 3 == 00001000
1 << 4 == 00010000
1 << 5 == 00100000
1 << 6 == 01000000
1 << 7 == 10000000

At this point, since an int is 8 bits, we can see why we can only shift
a maximum of 7. When it gets to (1 << 8), what should it do? Shift the
1 completely out of the number? Or leave it where it is? I'm not sure
but this is probably one of {undefined, unspecified,
implementation-defined}.

In your case, an int must be 32 bits or smaller, but you are trying to
shift it by 32 places.

 

[Howard]

Because your implementation's representation of int is apparently < 33
bits.


You could try:

static_cast<int>((1L << 32) - 1);

This will work if int is 32 bits.

Or, since you're just setting those 32 bits to 1s, you could use:

static const int a = 0xffffffff;

-Howard

 

[Thomas Tutone]

Hi,

in the header of my class I've a constant

static const int a = ( 1 << 32 ) - 1;

When compiling the code, g++ issues the warning
"warning: left shift count >= width of type"

Seems like a relatively lucid warning to me.

Why?

Because on your system, the number of bits in an int is less than or
equal to 32. And that means that, on your system, (1 << 32) is equal
to 0. Think about it - if you shift a 1 from the first bit to the 33rd
bit, but there are only 32 bits, what are you left with? So "a" in
your example is equal to -1, which I'm guessing is not what you
intended.

And how can I get rid of that?

Uhhm, shift fewer than 32 times and use an unsigned int? What is it
you're trying to do?

Best regards,

Tom

 

[Jack Klein]

Because your implementation's representation of int is apparently < 33
bits.


You could try:

static_cast<int>((1L << 32) - 1);

This will work if int is 32 bits.

Only if long has more than 32 bits.

 

[Michiel.Salters]

Seems like a relatively lucid warning to me.


Because on your system, the number of bits in an int is less than or
equal to 32. And that means that, on your system, (1 << 32) is equal
to 0.

No. Why would it? The most trivial example why it won't is because the
actual CPU has 32 bits and a built-in instruction for << that takes
just 5
bits. On such systems, A<<N == A<<(N%32) because all higher bits
are simply ignored. On such systems 1<<32 == 1. Or the CPU may just
decide to abort the program because it's buggy.

HTH,
Michiel Salters

 

[Victor Bazarov]

No. Why would it? The most trivial example why it won't is because the
actual CPU has 32 bits and a built-in instruction for << that takes
just 5
bits. On such systems, A<<N == A<<(N%32) because all higher bits
are simply ignored. On such systems 1<<32 == 1. Or the CPU may just
decide to abort the program because it's buggy.

Whatever conclusions you're trying to make from whatever knowledge you
possess about the hardware are nonconsequential; the Standard says that
the behaviour of the program in which the right operand of the shift
operator is negative or greater than or equal to the length in bits of
the promoted left operand is *undefined*. It can be 0, it can be 1, or
(and you know the drill, repeat after me) it can make demons fly out of
your nose.

V

 

[Steve Pope]

Thomas Tutone wrote:

No. Why would it? The most trivial example why it won't is because the
actual CPU has 32 bits and a built-in instruction for << that takes
just 5 bits. On such systems, A<<N == A<<(N%32) because all higher bits
are simply ignored. On such systems 1<<32 == 1. Or the CPU may just
decide to abort the program because it's buggy.

Also I don't think there's any rule requiring the compiler
to reduce this constant expression in exactly the same manner
that the target machine would. In the above, no left shift
instruction is ever generated in the code.

Steve

 

[Earl Purple]

Whatever conclusions you're trying to make from whatever knowledge you
possess about the hardware are nonconsequential; the Standard says that
the behaviour of the program in which the right operand of the shift
operator is negative or greater than or equal to the length in bits of
the promoted left operand is *undefined*. It can be 0, it can be 1, or
(and you know the drill, repeat after me) it can make demons fly out of
your nose.

Is the behaviour also undefined if you shifted by 1 bit 32 times? Are
the two equivalent?

In that case ((1 << 16) << 16) would be fully defined as long as
sizeof(int) > 16.

I assume, by the way, that it is perfectly defined behaviour to
right-shift bits off the end because that I do regularly, eg
right-shift 0x1234 >> 8 should give me 0x12. (If you're not allowed to
do that there is something horribly wrong with the standard).

 

[Victor Bazarov]

Is the behaviour also undefined if you shifted by 1 bit 32 times? Are
the two equivalent?

No, they are not equivalent. Shifting by 1 bit is well-defined. No
matter how many times you do it.

In that case ((1 << 16) << 16) would be fully defined as long as
sizeof(int) > 16.
Correct.

I assume, by the way, that it is perfectly defined behaviour to
right-shift bits off the end because that I do regularly, eg
right-shift 0x1234 >> 8 should give me 0x12. (If you're not allowed to
do that there is something horribly wrong with the standard).

It's well-defined. Get a copy of the Standard to check.

V

 

[Bo Persson]

Is the behaviour also undefined if you shifted by 1 bit 32 times?
Are
the two equivalent?

In that case ((1 << 16) << 16) would be fully defined as long as
sizeof(int) > 16.

The restriction in the standard is there because of the underlying
hardware.

We expect the compiler to be able to use the shift instructions of the
CPU. The problem is that some hardware will actually perform the long
shift (with a zero result), while others will do it modulo register
size. Others might refuse altogether.

With the popular x86 family, the behaviour has changed between
generations, which makes it hard for the compiler to compensate.

So, the C++ standard says that a shift works as expected as long as
the shift count is smaller than the integer type. If it is larger we
don't know, that's up to the underlying hardware.


Bo Persson

 

[Ron Natalie]

At this point, since an int is 8 bits, we can see why we can only shift
a maximum of 7. When it gets to (1 << 8), what should it do? Shift the
1 completely out of the number? Or leave it where it is? I'm not sure
but this is probably one of {undefined, unspecified,
implementation-defined}.

Undefined behavior. On the Intel i860, there is only enough bits
in the shift instruction to encode 31 places. If you do 32, it
only stuffs the low order bits and you get NOTHING. Believe me
the @&$@ X11 Server code relied on that yielding a zero not the
original operand. Had to fix it in a dozen places.

 

[Jerry Coffin]

[ ... ]

Undefined behavior. On the Intel i860, there is only enough bits
in the shift instruction to encode 31 places. If you do 32, it
only stuffs the low order bits and you get NOTHING. Believe me
the @&$@ X11 Server code relied on that yielding a zero not the
original operand. Had to fix it in a dozen places.

The x86 allows you to encode more if you want to, but recent iterations
of the processor mask it to 5 bits before doing the shift.

 

[Steve Pope]

(e-mail address removed) says...

The x86 allows you to encode more if you want to, but recent iterations
of the processor mask it to 5 bits before doing the shift.

And I still say for in the code fragment posted, no left shift
instruction will ever be emitted by the compiler, so such details are
quite possibly irrelevant.

Steve

 

[Jerry Coffin]

And I still say for in the code fragment posted, no left shift
instruction will ever be emitted by the compiler, so such details are
quite possibly irrelevant.

This seems almost self-contradictory. If you could be certain the
compiler wouldn't emit a left-shift instruction, then such details would
be definitely irrelevant. The only way they may be relevant is if the
compiler might emit the instruction -- which I'd say is correct for at
least a few compilers.

 

[Steve Pope]

(e-mail address removed) says...

This seems almost self-contradictory. If you could be certain
the compiler wouldn't emit a left-shift instruction, then such
details would be definitely irrelevant. The only way they may
be relevant is if the compiler might emit the instruction --
which I'd say is correct for at least a few compilers.

That is why I said "possibly irrelevant". "Intuitively, constant
expressions are simple expressions that can be evaluated by the
compiler before the program is linked [9.1] and starts to run."
(Stroustrap, C.5) To me it's unintuitive (but not incorrect) that
the compiler would not reduce the expression.

And actually, if the constant expression reduces to zero and is
assigned to a pointer, it's probably incorrect for the compiler
not to reduce it; but maybe those more expert than I might have
an opinion on this.

Steve

 

[Steve Pope]

Following up to myself:

(e-mail address removed) says...

And I still say for in the code fragment posted, no left shift
instruction will ever be emitted by the compiler [..]

This seems almost self-contradictory. If you could be certain
the compiler wouldn't emit a left-shift instruction, then such
details would be definitely irrelevant. The only way they may
be relevant is if the compiler might emit the instruction --
which I'd say is correct for at least a few compilers.

That is why I said "possibly irrelevant". "Intuitively, constant
expressions are simple expressions that can be evaluated by the
compiler before the program is linked [9.1] and starts to run."
(Stroustrap, C.5) To me it's unintuitive (but not incorrect) that
the compiler would not reduce the expression.

And actually, if the constant expression reduces to zero and is
assigned to a pointer, it's probably incorrect for the compiler
not to reduce it; but maybe those more expert than I might have
an opinion on this.

In fact, the following compiles (gcc):

int foo() {
int *pi;
pi = 1 << 100;
}

It seems to me that any approach that did not perform the
left shift until runtime would not be a correct implementation.

(Although there are some screwy possibilties, such as only
reducing the constant expression at compile time when it's
being assigned to a pointer; or reducing if it reduces to zero,
and issuing code for it otherwise; but I think these possibilities
are very highly remote.)

Steve

 

[Bo Persson]

(e-mail address removed) says...

This seems almost self-contradictory. If you could be certain
the compiler wouldn't emit a left-shift instruction, then such
details would be definitely irrelevant. The only way they may
be relevant is if the compiler might emit the instruction --
which I'd say is correct for at least a few compilers.

That is why I said "possibly irrelevant". "Intuitively, constant
expressions are simple expressions that can be evaluated by the
compiler before the program is linked [9.1] and starts to run."
(Stroustrap, C.5) To me it's unintuitive (but not incorrect) that
the compiler would not reduce the expression.

And actually, if the constant expression reduces to zero and is
assigned to a pointer, it's probably incorrect for the compiler
not to reduce it; but maybe those more expert than I might have
an opinion on this.

Do you mean that compile time constant expressions should be evaluated
differently than non-constant expressions? Shouldn't we expect the
same result?


To be more technical, the standard doesn't talk about compilers at
all - we could very well have an interpreter, or some other kind of
translator. And *if* a compiler does a compile time evaluation, is it
not supposed to use the hardware instructions itself, internally?


Bo Persson