Bit-fields and integral promotion/UACs

[Christian Kandeler]

Hi,

consider the following program:

#include <stdio.h>

int main(void)
{
struct test {
unsigned int x : 1;
} test;

test.x = 1;

printf("%lu\n", (unsigned long) (test.x << 31));

return 0;
}

On a platform with 64-bit longs and 32-bit ints, this prints
18446744071562067968, i.e. a number that has the upper 33 bits set to 1.
This stunned me at first, but I think I have now figured out what happens:

(1) Because the bit-field is only one bit wide, all its values fit into a
signed int, so test.x is converted to one.
(2) Therefore, the result of the shift operation is a signed int too.
(3) Since the resulting value is negative on this platform, ULONG_MAX + 1 is
added to it, yielding the value mentioned above.

Is this correct?
If it is, the (unwanted) sign extension is the result of (1), which converts
the unsigned bit-field to a signed int. This could then easily be avoided
by casting the bit-field to an unsigned int before the shift. However, the
resulting program

#include <stdio.h>

int main(void)
{
struct test {
unsigned int x : 1;
} test;

test.x = 1;

printf("%lu\n", (unsigned long) ((unsigned int) test.x << 31));
return 0;
}

still prints the same value with gcc 3.3.3. All other compilers I have tried
(including gcc 4), print 2147483648, as I had originally expected. Is my
assumption correct that gcc 3 is wrong here? Or am I overlooking something
and the behavior is actually implementation-defined?


Thanks,
Christian

 

[Alex Fraser]

#include <stdio.h>

int main(void)
{
struct test {
unsigned int x : 1;
} test;

test.x = 1;

printf("%lu\n", (unsigned long) (test.x << 31));

return 0;
}

On a platform with 64-bit longs and 32-bit ints, this prints
18446744071562067968, i.e. a number that has the upper 33 bits set to 1.
This stunned me at first, but I think I have now figured out what
happens:

(1) Because the bit-field is only one bit wide, all its values fit into a
signed int, so test.x is converted to one.

Yes (I would say "the value of test.x is converted"); this is integer
promotion.

(2) Therefore, the result of the shift operation is a signed int too.

Yes, because the type of the result of a shift is always the same as the
(promoted) left-hand operand.

(3) Since the resulting value is negative on this platform, ULONG_MAX + 1
is added to it, yielding the value mentioned above.

The shift invokes undefined behaviour, because the left-hand operand has
signed type and the result cannot be represented in that type.

[snip]

This could then easily be avoided by casting the bit-field to an unsigned
int before the shift. However, the resulting program

[snip: previous code with cast added]

still prints the same value with gcc 3.3.3. All other compilers I have
tried (including gcc 4), print 2147483648, as I had originally expected.
Is my assumption correct that gcc 3 is wrong here?

By my understanding, yes.

Alex

 

[CBFalconer]

.... snip ...

This could then easily be avoided by casting the bit-field to an
unsigned int before the shift. However, the resulting program

[snip: previous code with cast added]

still prints the same value with gcc 3.3.3. All other compilers
I have tried (including gcc 4), print 2147483648, as I had
originally expected. Is my assumption correct that gcc 3 is
wrong here?

By my understanding, yes.

Since you snipped the (faulty) code with added cast, it is hard to
criticize. Anyway I have added that (tautened) code back below:

#include <stdio.h>
int main(void) {
struct test {
unsigned int x : 1;
} test;

test.x = 1;
printf("%lu\n", (unsigned long) ((unsigned int) test.x << 31));
return 0;
}

Try:
printf("%lu\n", ((unsigned long) test.x) << 31);

The first task is to get the value 1 into unsigned long form.
After that the shift can function without overflow. In part this
is the fault of the standards attitude towards value preservation,
when unsigned preservation would be more appropriate.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>

 

[Chris Torek]

On a platform with 64-bit longs and 32-bit ints, this prints
18446744071562067968, i.e. a number that has the upper 33 bits set to 1.
This stunned me at first, but I think I have now figured out what happens:

(1) Because the bit-field is only one bit wide, all its values fit into a
signed int, so test.x is converted to one.
(2) Therefore, the result of the shift operation is a signed int too.
(3) Since the resulting value is negative on this platform, ULONG_MAX + 1 is
added to it, yielding the value mentioned above.

Is this correct?

Yes.

ANSI/ISO C has the "wrong" rules (according to me anyway ) for
handling mixes of signed and unsigned. The "right" rule is very
simple: "if any operand is unsigned, the result is unsigned."
This rule is simple and easy to understand, but sometimes gives
"surprising" results.

The ISO rule is: "If any operand is unsigned, it is widened, but
the resulting type depends on the possible ranges of values of the
original unsigned type and the wider type." This rule is complicated
and hard to understand, and *still* sometimes gives surprising
results. (Moreover, the results depend on the relative values of
the various *_MAXes, for non-bitfield types. In particular,
implementations with a USHRT_MAX of 65535 and an INT_MAX of 32767
behave differently from those with a USHRT_MAX of 65535 and an
INT_MAX of 2147483647, when doing arithmetic with "unsigned short".)

Because we are stuck with the horrible, near-impossible-to-reason-about,
implementation-dependent "value preserving" rules (am I laying it
on a little thick? ), your only recourses are intermediate
temporary variables or casts.

... This could then easily be avoided by casting the bit-field to
an unsigned int before the shift. However, the resulting program

#include <stdio.h>

int main(void)
{
struct test {
unsigned int x : 1;
} test;

test.x = 1;

printf("%lu\n", (unsigned long) ((unsigned int) test.x << 31));
return 0;
}

still prints the same value with gcc 3.3.3. All other compilers I have tried
(including gcc 4), print 2147483648, as I had originally expected. Is my
assumption correct that gcc 3 is wrong here?

Gcc 3.3.3 is wrong here.

(Note that shifting an "unsigned int" 31 bits is itself at least
a little risky, since there are 16-bit "int" implementations.)

 

[Christian Kandeler]

The shift invokes undefined behaviour, because the left-hand operand has
signed type and the result cannot be represented in that type.

Don't you mean "cannot _necessarily_ be represented"? Surely if int is 32
bits, then 1 << 31 is okay? Or, more generally, 1 << sizeof int * CHAR_BIT
- 1 is? If not, I'd be interested to know why.


Christian

 

[Keith Thompson]

Don't you mean "cannot _necessarily_ be represented"? Surely if int is 32
bits, then 1 << 31 is okay? Or, more generally, 1 << sizeof int * CHAR_BIT
- 1 is? If not, I'd be interested to know why.

If int is 32 bits, the INT_MAX is 2147483647.

1 << 31 is 2147483648.

 

[Joe Wright]

Alex Fraser wrote:




Don't you mean "cannot _necessarily_ be represented"? Surely if int is 32
bits, then 1 << 31 is okay? Or, more generally, 1 << sizeof int * CHAR_BIT
- 1 is? If not, I'd be interested to know why.


Christian

It's the old off-by-one problem.
1 << 31 yields..
1000 0000 0000 0000 0000 0000 0000 0000 Min int = -2147483648
...and MAX_INT is..
0111 1111 1111 1111 1111 1111 1111 1111 Max int = 2147483647

 

[Alex Fraser]

Alex Fraser wrote: [snip]

By my understanding, yes.

Since you snipped the (faulty) code with added cast, it is hard to
criticize. Anyway I have added that (tautened) code back below:

#include <stdio.h>
int main(void) {
struct test {
unsigned int x : 1;
} test;

test.x = 1;
printf("%lu\n", (unsigned long) ((unsigned int) test.x << 31));
return 0;
}

The OP stated 32-bit ints, so the value of "(unsinged int) text.x << 31" can
be represented in the result type, unsigned int.

Alex

 

[CBFalconer]

Alex Fraser wrote: [snip]

Is my assumption correct that gcc 3 is wrong here?

By my understanding, yes.

Since you snipped the (faulty) code with added cast, it is hard to
criticize. Anyway I have added that (tautened) code back below:

#include <stdio.h>
int main(void) {
struct test {
unsigned int x : 1;
} test;

test.x = 1;
printf("%lu\n", (unsigned long) ((unsigned int) test.x << 31));
return 0;
}

The OP stated 32-bit ints, so the value of "(unsinged int) text.x
<< 31" can be represented in the result type, unsigned int.

No it can't by that code. And why did you remove the corrected
code that didn't care how many bits were in an int? Together with
an explanation of why it was needed.

--
"The power of the Executive to cast a man into prison without
formulating any charge known to the law, and particularly to
deny him the judgement of his peers, is in the highest degree
odious and is the foundation of all totalitarian government
whether Nazi or Communist." -- W. Churchill, Nov 21, 1943

 

[Christian Kandeler]

Surely if int is 32 bits, then 1 << 31 is okay? [ ... ]

It's the old off-by-one problem.
1 << 31 yields..
1000 0000 0000 0000 0000 0000 0000 0000 Min int = -2147483648

I knew that the shift yielded a negative value. However, another look at the
standard showed that this is not guaranteed at all:

[E1 << E2]
If E1 has a signed type and nonnegative value, and E1 × 2^E2 is
representable in the result type, then that is the resulting value;
otherwise, the behavior is undefined.

This is the part that I was not aware of; I naively assumed that since we
don't exceed a width of 32 bits, the operation had to be valid.


Christian

 

[Alex Fraser]

No it can't by that code.
Pardon?

And why did you remove the corrected code that didn't care how many bits
were in an int?

Because it is irrelevant to the behaviour of the code above when the number
of bits in an int is known, which is the reason for this thread.

Alex