Смоделировать инструкцию jg (datalab's isGreater)
Я делаю datalab CSAPP, функцию isGreater.
Вот описание
isGreater - if x > y then return 1, else return 0
Example: isGreater(4,5) = 0, isGreater(5,4) = 1
Legal ops: ! ~ & ^ | + << >>
Max ops: 24
Rating: 3
x и y оба являются типом int.
Поэтому я считаю, чтобы смоделировать инструкцию jg для ее реализации. Вот мой код
int isGreater(int x, int y)
{
int yComplement = ~y + 1;
int minusResult = x + yComplement; // 0xffffffff
int SF = (minusResult >> 31) & 0x1; // 1
int ZF = !minusResult; // 0
int xSign = (x >> 31) & 0x1; // 0
int ySign = (yComplement >> 31) & 0x1; // 1
int OF = !(xSign ^ ySign) & (xSign ^ SF); // 0
return !(OF ^ SF) & !ZF;
}
Инструкция jg нуждается в SF == OF и ZF == 0.
Но он не может передать особый случай, то есть x = 0x7fffffff(INT_MAX), y = 0x80000000(INT_MIN).
Я делаю это так:
x + yComplement = 0xffffffff, поэтому SF = 1, ZF = 0, поскольку xSign!= ySign, OF имеет значение 0.
Итак, что не так с моим кодом, моя операция установки OF неверна?
2 ответа
Вы обнаруживаете переполнение в дополнении 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 оставить старшие биты на месте (но тогда вам придется сдвинуть ! результат).
Это просто ограничение лаборатории, вы не можете использовать unsigned или любую константу больше 0xff(255)
Итак, у вас нет доступа к логическому смещению вправо. Тем не менее, вам нужно не более одного &1, Можно работать с числами, где все, что вас волнует, это младший бит, а остальные - мусор.
Вы в конечном итоге делаете & !ZF что либо &0 или & 1 . Thus, any high garbage in OF` стирается.
Вы также можете отложить >> 31 пока после XORing вместе два числа.
Это забавная проблема, которую я хочу оптимизировать самостоятельно:
// 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
Но в любом случае, вот вывод x86 asm от gcc и clang в проводнике компилятора Godbolt.
Предполагая, что два дополнения, INT_MINабсолютное значение не может быть представлено как int, Так, yComplement == y (т.е. все еще отрицательный), и ySign является 1 вместо желаемого 0,
Вы могли бы вместо этого рассчитать знак y вот так (меняется как можно меньше в вашем коде):
int ySign = !((y >> 31) & 0x1);
Для более подробного анализа и более оптимальной альтернативы проверьте ответ Питера Кордеса.