Как сравнить два числа, чтобы увидеть, какое больше

Question

Сравнение двух чисел x, y; если x> y, я возвращаю 1, иначе возвращает 0. Я пытаюсь сделать это, используя только побитовые операторы, такие как >> << ~! & | ^ +. </p>

Пока я получил это:

int greaterThan(int x,int y) {
return ((~(x-y))>>31);
}

Так что, если xy отрицательный, самый значимый бит будет равен 1. Поэтому я отрицаю его, чтобы получить 0 и сдвинуть его так, чтобы он возвращал 0. Если xy положительный, самый значимый бит будет 0. Отрицательный чтобы получить 1 и сдвинуть его, чтобы вернуть 1. Это не похоже на работу. Я делаю это неправильно или что-то упустил?

Answer 1

Ваш метод не работает по нескольким причинам:

• Если предположить, что x и y являются знаковыми значениями, вычитание может быть переполнено.Это не только приводит к неопределенному поведению в соответствии со стандартом C, но и в типичных реализациях, где переполнение перекрывает, это даст неправильные результаты.Например, если x равно INT_MIN, а y равно 1, x-y даст INT_MAX, для которого не установлен старший бит.

• Если x и y являются значениями без знака, то x=UINT_MAX и y=0 - это пример, где вы получаете неправильный ответ.Чтобы этот тест сработал, вам нужно наложить условие на значения x и y (например, для которого не задан старший бит).

То, что сводится к тому, что для выполнения сравнения путем тестирования "старшего бита", вам нужно на один бит больше, чем количество бит в сравниваемых значениях.В языке ассемблера на архитектурах с разумным CISC-флагом флаг переноса предоставляет этот дополнительный бит, и специальные инструкции условного перехода (а также инструкции переноса / заимствования) могут считывать значение флага переноса.Однако C не предоставляет доступа к такому флагу переноса.Одним из альтернативных подходов может быть использование целочисленного типа большего размера (например, long long), чтобы вы могли получить дополнительный бит в своем результате.Хорошие компиляторы переведут это в чтение флага переноса, вместо того, чтобы фактически выполнять большие арифметические операции.

Answer 2

C Standard (1999), глава 6.5.7 Операции побитового сдвига, параграф 5:

Результатом E1 >> E2 является E1-сдвинутая вправо позиция бита E2. Если E1 имеет тип без знака или если E1 имеет тип со знаком и неотрицательное значение, значение результата является целым часть отношения E1 / 2E2. Если E1 имеет тип со знаком и отрицательное значение, результирующее значение определяется реализацией.

Т.е., результат для сдвига вправо на отрицательных числах определяется реализацией. Одна из возможностей заключается в том, что «знаковый бит» копируется в биты справа, что, по-видимому, и делает GCC (поскольку в результате все биты установлены, -1).

Answer 3

@ Дэн, не могли бы вы уточнить свой вопрос в первом посте, то есть, что именно вы можете использовать, а что нет (в ваших комментариях вы упомянули, что вы не можете использовать if / else и т. Д. ).

В любом случае, если вы хотите избавиться от неожиданного -1, вам следует рассмотреть приведение значения к unsigned int перед переключением. Это не сделает ваше решение полностью правильным, хотя. Попробуйте подумать о проверке знакового бита чисел (например, если первый бит x равен 0, а первый бит y равен 1, тогда вы можете быть уверены, что x> y).