Вы обнаруживаете переполнение в сложении x + yComplement, а не в общем вычитании

-INT_MIN само переполняется в дополнении до 2; INT_MIN == -INT_MIN. Это аномалия дополнения до 2¹.

Вы должны получить быстрое обнаружение переполнения для любого отрицательного числа (кроме INT_MIN) минус INT_MIN. Результирующее дополнение будет иметь знаковое переполнение. например -10 + INT_MIN переполняется.

http://teaching.idallen.com/dat2343/10f/notes/040_overflow.txt есть таблица входных/выходных знаков для сложения и вычитания. Случаи переполнения - это когда входные знаки противоположны, но знак результата соответствует y.

      SUBTRACTION SIGN BITS  (for num1 - num2 = sum)
    num1sign num2sign sumsign
   ---------------------------
        0 0 0
        0 0 1
        0 1 0
 *OVER* 0 1 1 (subtracting a negative is the same as adding a positive)
 *OVER* 1 0 0 (subtracting a positive is the same as adding a negative)
        1 0 1
        1 1 0
        1 1 1

Вы можете использовать это напрямую с исходными x и y и использовать только yComplement как часть получения minusResult. Настройте свою логику, чтобы она соответствовала этой таблице истинности.

Или вы можете использовать int ySign = (~y) >> 31; и оставить остальную часть кода без изменений. (Используйте tmp для удержания ~y, чтобы выполнить операцию только один раз, для этого и yComplement). Обратное дополнение до единицы (~) не страдает от аномалии дополнения до 2.

Сноска 1: знак/величина и дополнение до единицы имеют два избыточных способа представления 0 вместо значения без обратного.

Забавный факт: если вы создаете целочисленную функцию абсолютного значения, вы должны учитывать результат unsigned, чтобы избежать этой проблемы. int не может представлять абсолютное значение INT_MIN.

Повышение эффективности:

Если вы используете unsigned int, вам не нужно & 1 после сдвига, потому что логические сдвиги не расширяются по знаку. (И в качестве бонуса это позволит избежать неопределенного поведения переполнения со знаком C в +: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html).

Затем (если вы использовали uint32_t или sizeof(unsigned) * CHAR_BIT вместо 31) у вас была бы безопасная и переносимая реализация сравнения дополнений до 2. (семантика знакового сдвига для отрицательных чисел определяется реализацией в C.) Я думаю, что вы используете C как своего рода псевдокод для битовых операций и не заинтересованы в написании переносимой реализации, и это нормально. То, как вы это делаете, будет работать на обычных компиляторах на обычных процессорах.

Или вы можете использовать & 0x80000000, чтобы оставить старшие биты на месте (но тогда вам придется сдвинуть влево результат !).

Это просто ограничение лаборатории, вы не можете использовать без знака или любую константу больше 0xff(255)

Итак, у вас нет доступа к логическому сдвигу вправо. Тем не менее, вам нужно не более одного &1. Можно работать с числами, где все, что вам нужно, это младший бит, а остальные содержат мусор.

В конце концов вы делаете & !ZF, что означает либо &0, либо &1. Thus, any high garbage in OF`.

Вы также можете отложить >> 31 до тех пор, пока два числа не будут объединены XOR.

Это забавная проблема, которую я хочу оптимизировать сам:

// untested, 13 operations
int isGreater_optimized(int x, int y)
{
    int not_y = ~y;
    
    int minus_y = not_y + 1;
    int sum = x + minus_y;

    int x_vs_y = x ^ y;       // high bit = 1 if they were opposite signs: OF is possible
    int x_vs_sum = x ^ sum;   // high bit = 1 if they were opposite signs: OF is possible

    int OF = (x_vs_y & x_vs_sum) >> 31;   // high bits hold garbage
    int SF = sum >> 31;

    int non_zero = !!sum;              // 0 or 1
    return (~(OF ^ SF)) & non_zero;      // high garbage is nuked by `& 1`
}

Обратите внимание на использование ~ вместо ! для инвертирования значения с большим количеством мусора.

Похоже, что в вычислении OF отдельно от SF все еще есть некоторая избыточность, но на самом деле двойное XOR над суммой не компенсируется. x ^ sum является входом для &, и после этого мы выполняем XOR с суммой.

Однако мы можем отложить сдвиги даже позже, и я нашел еще несколько оптимизаций, избегая дополнительной инверсии. Это 11 операций

// replace 31 with  sizeof(int) * CHAR_BIT  if you want.  #include <limit.h>
// or use int32_t

int isGreater_optimized2(int x, int y)
{
    int not_y = ~y;

    int minus_y = not_y + 1;
    int sum = x + minus_y;
    int SF = sum;             // value in the high bit, rest are garbage

    int x_vs_y = x ^ y;       // high bit = 1 if they were opposite signs: OF is possible
    int x_vs_sum = x ^ sum;   // high bit = 1 if they were opposite signs: OF is possible
    int OF = x_vs_y & x_vs_sum;   // low bits hold garbage

    int less = (OF ^ SF);
    int ZF   = !sum;               // 0 or 1
    int le   = (less >> 31) & ZF;  // clears high garbage
    return  !le;                   // jg == jnle
}

Я задавался вопросом, смогут ли какие-нибудь компиляторы просмотреть это руководство, сравнить и оптимизировать его в cmp edi, esi/ setg al, но не тут-то было :/ Я думаю, это не тот шаблон, который они ищут, потому что код, который мог бы быть написан как x > y, имеет тенденцию к быть написано так :P

But anyway, here's the x86 asm output from gcc and clang on Проводник компилятора Godbolt.

Предполагая дополнение до двух, абсолютное значение INT_MIN не может быть представлено как int. Итак, yComplement == y (т.е. все еще отрицательное), а ySign это 1 вместо желаемого 0.

Вместо этого вы можете вычислить знак y следующим образом (изменив как можно меньше в вашем коде):

int ySign = !((y >> 31) & 0x1);

Для более подробного анализа и более оптимальной альтернативы см. ответ Питера Кордеса.