5

I have a piece of code from an assignment I am uncertain about. I feel confident that I know the answer, but I just want to double-check with the community incase there's something I forgot. The title is basically secure coding and the question is just to explain the results.

int main() {
   unsigned int i = 1;
   unsigned int c = 1;
   while (i > 0) {
     i = i*2;
     c++;
   }
   printf("%d\n", c);
   return 0;
}

My reasoning is this:

At first glance you could imagine the code would run forever, considering it's initialized to a positive value and ever increasing. This of course is wrong because eventually the value will grow so large it will cause an integer overflow. This in turn is not entirely true either, because eventally it will force the variable 'i' to be signed by making the last bit to 1 and therefore regarded as a negative number, therefore terminating the loop. So it is not writing to unallocated memory and therefore cause integer overflow, but rather violating the data type and therefore causing the loop to terminate.

I am quite sure this is the reason, but I just want to double check. Any opinions?

4

7 回答 7

5

No, unsigned int will never compare against zero as a signed number. The only chance for the loop to end is for the variable to become exactly zero.

The latter will surely happen once since you multiply by 2 (an even number) in each iteration and this causes a zero bit to be inserted from right (least meaningful bit), so after some number of iterations all non-zero bits will be "shifted out of the number" and it will become zero.

于 2011-03-02T15:24:04.280 回答
2

There is no overflow when dealing with unsigned values. All calculations are done modulo (UINT_MAX + 1).

So, what happens is that the value by repeatedly multiplying by 2 you eventually wrap-around to zero ... and your loop stops

Suppose, for simplicity sake, that unsigned is 4 bits wide.

1 * 2 = 2 ==> 0b0010
2 * 2 = 4 ==> 0b0100
4 * 2 = 8 ==> 0b1000
8 * 2 = 0 ==> 0b0000
于 2011-03-02T15:31:28.183 回答
1

unsigned values do not overflow; they are, in fact, guaranteed and defined to wrap-around.

于 2011-03-02T15:39:16.290 回答
1

In case of signed integer, the left most bit sets the sign, so the range of values that this type element can have are -2147483648 to 2147483647. To get negative value from positive value you do bit inverse to all bits and vice-versa.

In case of unsigned integer, the left most bit is use to store extra values. So i range of values that this type element can have are 0 to 4294967295.

In binary form, when i=1; and you only do i = i*2; then values, that you can have as values are:

1 // 1 in base 10
10 // 2 in base 10
100 // 4 in base 10
1000
10000
100000
1000000
10000000
100000000
1000000000
10000000000
100000000000
1000000000000
10000000000000
100000000000000
1000000000000000
10000000000000000
100000000000000000
1000000000000000000
10000000000000000000
100000000000000000000
1000000000000000000000
10000000000000000000000
100000000000000000000000
1000000000000000000000000
10000000000000000000000000
100000000000000000000000000
1000000000000000000000000000
10000000000000000000000000000
100000000000000000000000000000
1000000000000000000000000000000 // 1073741824 in base 10
10000000000000000000000000000000 // 2147483648 in base 10

Now, if you have a loop like: while (i > 0) { and i acts as described before, then it will be in a infinite loop, as it will never be 0. Overflows will occur, but thy will not brake program - it will still be running.

In case variable i is signed (default), then you would get output c=32 as integer 10000000000000000000000000000000 evaluates to -2147483648 and that is < 0. In this case however you do not know the output.

As it is schoolwork, then naturally teachers have picked a problem, where you can not conclude anything from running the code provided. I assume, that this is because, thy want you to know how underlaying types are stored and what is difference between signed and unsigned types.

Just as an extra fact, Java does not have unsigned primitives or immutable number classes. Not having them can be painful, in some cases. It is diffidently a useful keyword.

于 2011-03-02T15:59:52.263 回答
0

i is unsigned throughout. At some point it will overflow (or wrap around if that makes it clearer) and become exactly 0, it cannot ever be negative.

于 2011-03-02T15:23:49.847 回答
0

you are right about the overflow, but an unsigned int is unsigned for a reason (there is no sign bit hence unsigned, an unsigned int starts at 0) therefore it will overflow to 0, if it was unsigned it would have overflown to a negative number (- 2**31 on a 32 bit machine for example)

于 2011-03-02T15:26:04.087 回答
0

As i is an unsigned integer (0 - 255), i will equal 0 after 8 iterations due to binary round off.

于 2011-03-02T15:30:22.810 回答