Emulating signed integers using unsigned integers in C – Integer

The Problem:

In Jens Gustedt’s book "Modern C", he presents a method to emulate signed integers using unsigned integers. Specifically, he provides code for comparing two unsigned integers, reinterpreting them as signed integers. However, users have pointed out that the code appears to miss a case where one integer is negative and the other is positive. For instance, if we represent -1 as the unsigned integer UINT_MAX and 1 as 1, the code incorrectly determines that -1 is not less than 1. This raises the question of whether there is a mistake in the code or a misunderstanding of the emulation process.

The Solutions:

Solution 1: Using Simple logic

Revisiting the original code, it becomes apparent that the issue arises in handling the case where one number is negative and the other is positive. The corrected code would look as follows:

bool is_signed_less_correct(unsigned a, unsigned b) {
    // Determine the signedness of both numbers.
    bool is_negative_a = is_negative(a);
    bool is_negative_b = is_negative(b);

    // If the signedness is different, the comparison is trivial.
    if (is_negative_a != is_negative_b) {
        // If one is negative and the other is positive, the negative one is smaller.
        return is_negative_a;
    }
    else {
        // If both are negative or both are positive, use unsigned comparison.
        return a < b;
    }
}

This code explicitly handles the case where one number is negative and the other is positive, ensuring that a negative number is always considered smaller.

Solution 2: Using Subtraction to Offset Values

bool is_signed_less(unsigned a, unsigned b) {
unsigned const int_min = UINT_MAX / 2 + 1; /* 0x80000000 on 32-bit platforms */
return (a – int_min) < (b – int_min);
}

In this solution, we determine if a is less than b by subtracting the minimum signed integer value, int_min, from both a and b before performing the unsigned comparison. This ensures that the values are mapped to a range where the subtraction results correctly reflect their signed interpretations.

1. Offset Calculation: The constant int_min is calculated as half of UINT_MAX plus 1. This value is the negative of the minimum signed integer value, which provides the offset for mapping the signed integer range to the unsigned integer range.

2. Subtracting the Offset: Both a and b are subtracted by int_min. This subtraction shifts the signed integer values to the unsigned integer range, where they can be directly compared.

3. Unsigned Comparison: The resulting values are compared using unsigned comparison operators. If (a – int_min) is less than (b – int_min), it implies that a is less than b in the signed integer interpretation.

4. Handling Special Cases: This solution correctly handles the case where a and b have opposite signs by ensuring that the subtraction shifts the values to the appropriate positions in the unsigned integer range. This eliminates the potential for incorrect comparisons due to sign differences.

Solution 3: Handling Negative Numbers in Comparison

To correctly compare signed integers using unsigned integers, we need to account for all possible scenarios. In the original code, there was a missing case where one number is negative (represented by a large unsigned integer) and the other is positive (represented by a small unsigned integer). This could lead to incorrect comparisons, especially when comparing values near the maximum and minimum ranges.

To address this issue, the improved solution introduces two temporary boolean variables, `negativeA` and `negativeB`, which store the signs of the input values. These variables are computed only once, avoiding redundant calculations.

The comparison logic is then updated as follows:

bool is_signed_less(unsigned a, unsigned b) {
    bool negativeA = is_negative(a);
    bool negativeB = is_negative(b);
    return (
        (
            negativeA != negativeB ?
            negativeA :
            a < b
        )
    );
}

This updated code first checks if the signs of `a` and `b` differ. If they do, it checks if `a` is negative (represented by a large unsigned integer). If `a` is negative, it returns `true`, indicating that `a` is less than `b`. Otherwise, it returns `false`, indicating that `a` is greater than or equal to `b`.

If the signs of `a` and `b` are the same, the code simply compares them using the less-than operator, `a < b`. This is because both `a` and `b` are either positive or negative, and their relative order is the same regardless of their representation as unsigned integers.

With this modification, the function `is_signed_less` correctly handles signed integer comparisons even in cases where one number is negative and the other is positive. This ensures accurate comparisons for all possible combinations of signed integers represented as unsigned integers.

Solution 4: Correct comparison of unsigned integers as signed

The original code for `is_signed_less` function is incorrect when comparing unsigned integers as signed integers. It fails to handle the case when the signs of the two numbers are different. To fix this issue, the code should be modified as follows:

“`
bool is_signed_less(unsigned a, unsigned b) {
if (is_negative(b) != is_negative(a)) {
return b < a; // If signs are different, reverse the comparison } else { return a < b; // If signs are the same, use normal comparison } } ```

In this corrected version, when the signs of `a` and `b` are different, the comparison is reversed using `b < a`. This ensures that negative numbers are always considered less than positive numbers, regardless of their actual values.

Solution 5: Simpler and Correct Comparison of Signed Unsigned Integers

Jens Gustedt’s approach to emulating signed integers using unsigned integers in C has a flaw in his comparison function is_signed_less. To address this, here’s a simpler and correct version of the function:

bool is_signed_less(unsigned a, unsigned b) {
   const unsigned sign_bit = ~(UINT_MAX >> 1);
   return (a ^ sign_bit) < (b ^ sign_bit); 
}

To understand how this function works, let’s break it down:

• Sign Bit: The constant sign_bit represents the sign bit position in the unsigned integer representation, which is the most significant bit (MSB).
• XOR with Sign Bit: The expressions (a ^ sign_bit) and (b ^ sign_bit) essentially flip the sign bit of a and b while preserving the rest of the bits.
• Unsigned Comparison: The comparison (a ^ sign_bit) < (b ^ sign_bit) is now an unsigned comparison, but it effectively compares the signed values of a and b.

This revised function correctly handles the scenario where is_negative(a) and is_negative(b) have different values, ensuring that the comparison result is accurate.

Video Explanation: