Weird number和Signed overflow

本文主要参考，以32位带符号整数为例。 twos-complement

先看如下的程序：

#include

#include

 

int main(void)

{

    int a = INT_MAX;

    int b = a + 1;

    int c = a + 7;

 

    printf("%d %d %d\n", a, a + 1, a + 2);

    printf("%d %d %d %d\n", b, b + b, 2 * b, -b);

    printf("%d %d %d\n", c, c - a, b - a);

   

    if(c < a)

        printf("c < a is true\n");

    if(c - a > 0)

        printf("c - a > 0 is true\n");

 

 

    return 0;

}

在VC 6.0的输出如下：

2147483647 -2147483648 -2147483647

-2147483648 0 0 -2147483648

-2147483642 7 1

c < a is true

c - a > 0 is true

 

32位符号整数最大的整数为2,147,483,647（INT_MAX），在表示下，INT_MAX加一变成了-2147483648。-2147483648是一个非常特殊的数，称之为weird number，weird number有如下特性（1）不等于0 （2）等于0的一半 （3）既是正数也是负数

 

另外特别注意上面的c-a 和b-a依然是正数（注意是负数减去正数结果是正数，从另一方面来说正数减去负数可能是负数）。这个特性在现实中广泛应用，假定一个计数器，一路增加，未溢出之前值为prev（正数），溢出之后值为cur（负数）。我们依然可以使用

   if(cur - prev > 0) 

来判定cur发生在prev之后，这无疑是非常方便的。

 twos complement优于ones complement的地方：dominance of twos complement was not due to ease of use, but rather due to the fact that it allows a single hardware adder to perform both signed and unsigned computations. 另一个理由My recollection of those days is that the greater motivation was to get away from systems with two different representations of zero. There were ancient Fortran codes run on CDC mainframes that had to test results for both postive and negative zero.

C标准中整数的表示

The first edition of K & R explicitly states the signed-integer overflow is undefined. This has carried through to the present. After all, there *are* machines that handle it in different ways. There's (nearly extinct) one's complement and two's complement, but there's also saturating arithmetic that many DSPs use, where (for 16-bit type), 32767+1 = 32767.

 

C11中并未规定整数用two’s complement来表示，而是有三种可能，具体采用哪种implementation-defined。

在6.2.6.2 Integer types中：

2 For signed integer types, the bits of the object representation shall be divided into three groups: value bits, padding bits, and the sign bit. There need not be any padding bits;

signed char shall not have any padding bits. There shall be exactly one sign bit.

Each bit that is a value bit shall have the same value as the same bit in the object

representation of the corresponding unsigned type (if there are M value bits in the signed

type and N in the unsigned type, then M <= N). If the sign bit is zero, it shall not affect the resulting value. If the sign bit is one, the value shall be modified in one of the

following ways:

— the corresponding value with sign bit 0 is negated (sign and magnitude);

— the sign bit has the value -(2^M) (two’s complement);

— the sign bit has the value -(2^M -1) (ones’ complement).

Which of these applies is implementation-defined, as is whether the value with sign bit 1

and all value bits zero (for the first two), or with sign bit and all value bits 1 (for ones’

complement), is a trap representation or a normal value. In the case of sign and

magnitude and ones’ complement, if this representation is a normal value it is called a

negative zero.

 

现实中的问题及解决

在现实中所有运行Linux的都是采用two’s complement，但是这并意味着不会带来问题。

1 long long_cmp_opt(const int a, const int b)

     2 {

     3   if (a > 0) {

     4     do_something();

     5     if (b < 0) {

     6       do_something_else();

     7       if ((a - b) > 0)

     8         do_another_thing();

     9     }

    10   }

    11 }

第7行编译器可能优化，认为a-b肯定大于0而忽略这条语句，但是在two’s complement下这条语句可能小于0，从而导致编译器优化错误。GCC的O2及更高级别的优化就会直接忽略这条语句，而O1会正确生成该语句。

 

另一个例子："signed counters can't overflow" can be pretty useful, since it can allows the compiler to figure out loop sizes

    for (i = x; i < x + 16; i++)

    {

        /* code that does not modify either x or i */

    }

The compiler wants to know it's safe to assume this loop goes around 16 times. That isn't true if "x + 16" could overflow.

 

 

解决方法一：采用无符号整数来计数

  The C standard defines unsigned integers to use modular arithmetic, so that wrapping the counter is fully defined (Section 6.2.5 Paragraph 9). here is the corresponding version for unsigned long types:

    if (ULONG_MAX / 2 < a - b)

This version relies on the fact that, bit for bit, twos-complement addition and subtraction are identical to their unsigned counterparts. Now, the bitwise representation of the constant ULONG_MAX / 2 is a zero bit followed by all one-bits, which is the largest value that does not have the most-significant bit set. Therefore, if the result of computing a - b is greater than this constant, we know that this result has its uppermost bit set.

 

解决方法二：Why not just use -fwrapv in the kernel?

`-fwrapv'

This option instructs the compiler to assume that signed arithmetic overflow of addition, subtraction and multiplication wraps around using twos-complement representation. This flag enables some optimizations and disables others. This option is enabled by default for the Java front-end, as required by the Java language specification.

 

The kernel currently uses -fno-strict-overflow because -fwrapv was buggy in some versions of gcc. Unfortunately -fno-strict-overflow is also buggy in some other versions of gcc. Depending on the version of gcc I compile with, I have to patch the makefile to use one or the other.