Вы обнаруживаете переполнение в добавлении x + yComplement, а не в общем вычитании
-INT_MIN само переполняется в 2-х дополнениях; INT_MIN == -INT_MIN. Это аномалия дополнения 2 1 .
Вы должны получить быстрое положительное обнаружение переполнения для любого отрицательного числа (кроме 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, чтобы оставить старшие биты на месте (но тогда вам придется сдвинуть влево ваш ! результат).
Это просто ограничение лаборатории, вы не можете использовать unsigned или любую константу больше 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
Но в любом случае, вот вывод as86 x86 от gcc и clang в проводнике компилятора Godbolt.