Re: [Dev-C++] OT signed/unsigned

[Per W. <pw...@ia...>]

Of course there are more things that can be said about the subject.

There are several things to think about, but the things that comes to
mind is mainly:
- Numeric range for signed integers.
- Sign extension when changing between integers of different size.
- Bit-manipulation and shift operations.

One example where it is vital to keep track of signed/unsigned is when
using bit-fields.

typedef struct {
    unsigned int active : 1;
    unsigned int mode : 4;
    unsigned int reset : 1;
    unsigned int action : 2;
} bitfields_t;

In this case, several small bit-fields share the space in a larger integer
but the source code will not need to contain any bit manipulation.

However, if the bit field had been declared without the unsigned keyword,
the field 'active' would only have had room for -1 and 0. Since signed
values are stored in something called two-complement format, the negative
range will always be one step larger than the positive range.

For size:
1-bit -1 .. 0 <=3D=3D=3D seems illogical: can't even store the value 1!
2-bit -2 .. 1
8-bit -128 .. 127
16-bit -32768 .. 32767
=2E..

Lets try:

    bitfields_t t;
    printf("sizeof(t) =3D %u\n",sizeof(t));
    t.active =3D 1;
    printf("t.active =3D %d\n",t.active);
    printf("t.active =3D %u\n",t.active);

For a 32-bit machine, the output will normally be:
    sizeof(t) =3D 4
    t.active =3D 1
    t.active =3D 1

Now change the fields declarations from 'unsigned int' to just 'int'. The
output will then be:
    sizeof(t) =3D 4
    t.active =3D -1  <=3D=3D=3D assign of 1 resulted in -1 because of overf=
low.
    t.active =3D 4294967295  <=3D=3D=3D sign extension makes large unsigned=
 values

The signed value can only store the value -1 and 0, and since the sign bit
is set, t.active is -1.
When printing a signed value, t.active is automatically increased
in size from 1 bit up to the size of an int variable. When the
value is signed, there will be a sign extension when the storage
size is increased.

Sign extension means that the sign bit - the most significant bit in the
integer - will be copied into all new bits added for the larger integer
format.

This sign extension is very, very important to think about. For unsigned
numbers, going to a larger integer size just adds a lot of zero-bits to
the left of the original value, while for signed integers, it is the most
significant bit that gets duplicated.

For signed integers, there will be sign-extension:
1 decimal (0x01 hex) will become 0x0001, 0x00000001, etc when
sign-extending.

-1 decimal (0xff hex) will become 0xffff, 0xffffffff, etc when
sign-extended.

For a unsigned integer, the extra bits will just be set to zero:
255 decimal (0xff hex) will become 0x00ff, 0x000000ff, etc when extending
to a larger numeric type.

Bit rotations and shifts.
=3D=3D=3D=3D=3D
Note that shift operations do result in "strange" behaviour because of
sign extension of signed numbers.

Let's assume the 8-bit rotate-left code:
    a =3D (a << 1) | ((a & 0x80? ? 1 : 0);

Let's assume the 8-bit rotate-right coe:
    a =3D (a >> 1) | ((a & 1) ? 0x80 : 0);

The value is shifted left or right, and the bit that gets shifted out is
copied to the other end of the integer. The above code looks nice, but
let's try it:

    signed char a;
    unsigned char b;
    unsigned i;

    // Rotating 8-bit number left:=B7
    printf("Rotating 8-bit signed and unsigned integer left\n");=B7
    for (i =3D 1,a =3D 8,b =3D 8; i <=3D 8; i++) {=B7
        a =3D (a << 1) | ((a & 0x80) ? 1 : 0);=B7
        b =3D (b << 1) | ((b & 0x80) ? 1 : 0);=B7
        printf("step %u: %10u %10d %02x      "
               "%10u %10d %02x\n",i,a,a,a & 0xff,b,b,b);=B7
    }=B7
=B7
    // Rotating 8-bit number right:=B7
    printf("Rotating 8-bit signed and unsigned integer right\n");=B7
    for (i =3D 1,a =3D 8,b =3D 8; i <=3D 8; i++) {=B7
        a =3D (a >> 1) | ((a & 1) ? 0x80 : 0);=B7
        b =3D (b >> 1) | ((b & 1) ? 0x80 : 0);=B7
        printf("step %u: %10u %10d %02x      "
               "%10u %10d %02x\n",i,a,a,a & 0xff,b,b,b);=B7
    }=B7

Will result in:

Rotating 8-bit signed and unsigned integer left
step 1:         16         16 10              16         16 10
step 2:         32         32 20              32         32 20
step 3:         64         64 40              64         64 40
step 4: 4294967168       -128 80             128        128 80
step 5:          1          1 01               1          1 01
step 6:          2          2 02               2          2 02
step 7:          4          4 04               4          4 04
step 8:          8          8 08               8          8 08

Rotating 8-bit signed and unsigned integer right
step 1:          4          4 04               4          4 04
step 2:          2          2 02               2          2 02
step 3:          1          1 01               1          1 01
step 4: 4294967168       -128 80             128        128 80
step 5: 4294967232        -64 c0              64         64 40
step 6: 4294967264        -32 e0              32         32 20
step 7: 4294967280        -16 f0              16         16 10
step 8: 4294967288         -8 f8               8          8 08

The left three colums is rotation of a signed value - printed as unsigned,
signed and hex.

The right three columns is rotation of a unsigned value - printed as
unsigned, signed and hex.

Note that left-rotation works as expected for both signed and unsigned
values. The large value for the fourth iteration is just sign-extension of
-128 up to full 32-bit size.

However, look at the right-rotation of signed values. While the original
value - and all left-rotated values - contained one single bit set, the
right-rotated signed value suddenly started to contain quite a lot of
bits.

When shifting signed or unsigned values left, the least significant bit
will always be a zero.

When shifting a unsigned value right, the most significant bit will always
be a zero.

However, when shifting a signed value right, the most significant bit will
be a copy of the previously most significant bit, i.e. the sign bit will
be duplicated.

When shifting -128 (0x80) right, the result will not be 64 (0x40), but
instead the negative sign bit will be duplicated, resulting in -64 (0xc0).
The duplication of the sign bit is required to allow a right-shift of a
negative value to correspond with a division by two, but shows why the
rotate-right code must be slightly extended to work with signed values.

To get a correct right-rotation, the duplicated sign-bit must be
eliminated:
    a =3D ((a >> 1) & 0x7f) | ((a & 1) ? 0x80 : 0);=B7

which will give us the printout:
Rotating 8-bit signed and unsigned integer right
step 1:          4          4 04               4          4 04
step 2:          2          2 02               2          2 02
step 3:          1          1 01               1          1 01
step 4: 4294967168       -128 80             128        128 80
step 5:         64         64 40              64         64 40
step 6:         32         32 20              32         32 20
step 7:         16         16 10              16         16 10
step 8:          8          8 08               8          8 08

/Per W

On Thu, 8 Jun 2006, Lord Sauron wrote:

> No nuggets of knowledge?  I'm sure there's something more on the
> subject.  I don't know, though I can't imagine it being that simple.
>