Search code examples
cbit-manipulationtwos-complement

How to simulate two's complement arithmetics upon 5-bit representation?


Suppose one have to sum (or to subtract, etc.) two signed numbers as coded below:

short short_sum (int i1, int i2) {
    assert (SHRT_MIN <= i1 && i1 <= SHRT_MAX);
    assert (SHRT_MIN <= i2 && i2 <= SHRT_MAX);
    return (short)(i1 + i2);
    }

I need to simulate the same effect, but replacing int and short by, respectively, signed bytes and (theoretical) 5-bit signed integers. Something like what follows:

signed char tiny_sum (signed char c1, signed char c2) {
    assert (-16 <= c1 && c1 <= 15);
    assert (-16 <= c2 && c2 <= 15);
    return (signed char)(((c1 + c2) << (CHAR_BIT - 5)) >> ((CHAR_BIT - 5)));
    }

Although the code above has done the trick, it has some flaws: right-shifting a negative number is implementation-defined and, worse, left-shifting such a number, or a positive whose left-shifting "overflows", is undefined. So the code is neither portable nor truly predictable.

So this is my question: how can I achieve the desired effect with a fast, portable and well-defined bit manipulation?

Thanks in advance.


Solution

  • Using https://graphics.stanford.edu/~seander/bithacks.html#VariableSignExtend do:

    #include <stdio.h>
    
    // start with good typedefs...
    typedef signed char int5_t;
    typedef unsigned char uint5_t;
    #define INT5_MAX 15
    #define INT5_MIN -16
    #define UINT5_MAX 31
    
    int5_t int5_add(int5_t a, int5_t b) {
        // converting signed to unsigned is defined
        // `% 32` is just the same as `& 0x1f`.
        const unsigned c = ((unsigned)a + (unsigned)b) % 32;
        // Just copying from the link...
        const unsigned m = 1U << (5 - 1);
        // Just two operations.
        return (c ^ m) - m;
    }
    
    void test(int a, int b, int c) {
        int d = int5_add(a, b);
        printf("%3hhd + %3hhd = %3hhd shouldbe %3hhd - %s\n", a, b, d, c, d == c ? "OK" : "ERROR");
    }
    int main() {
        test(-16, -1, 15);
        test(-16, 0,  -16);
        test(-16, 1,  -15);
        test(15,  1,  -16);
        test(15,  0,  15);
        test(15,  -1, 14);
        return -1;
    }
    

    and, worse, left-shifting such a number, or a positive whose left-shifting "overflows", is undefined

    "Undefined" in the standard, but see your compiler documentation. On gcc we "know" that integers implementation:

    GCC supports only two’s complement integer types, and all bit patterns are ordinary values.

    [...]

    • The results of some bitwise operations on signed integers (C90 6.3, C99 and C11 6.5).

    Bitwise operators act on the representation of the value including both the sign and value bits, where the sign bit is considered immediately above the highest-value value bit. Signed ‘>>’ acts on negative numbers by sign extension.

    As an extension to the C language, GCC does not use the latitude given in C99 and C11 only to treat certain aspects of signed ‘<<’ as undefined. However, -fsanitize=shift (and -fsanitize=undefined) will diagnose such cases. They are also diagnosed where constant expressions are required.