LINUX.ORG.RU

Красивые способы корректного сравнения знаковых и беззнаковых целых

 , ,


5

7

Стандарты языка С предписывают компиляторам пользовать «быстрое» сравнение, вместо корректного.

То есть в следующем коде согласно всех стандартов языка С переменная res должна получить значение 0 а не 1, что крайне непрактично.

unsigned int a = 1;
int b = -1;
int res = (b < a);

Недавно я узнал что существует заметно больше способов корректного сравнения чем я изначально предполагал. Поэтому мне интересен чужой опыт.

Естественно речь о ситуациях где отказаться ни от знаковых, ни от беззнаковых никак нельзя.

Мой основной способ решения этой проблемы через расширение разрядности, так как я в первую очередь имею дело с unsigned char, но смесь size_t c ssize_t или что-то подобное также нередко доставляет неудобства.

Опишите кто и как выкручивается в сложившейся ситуации.

[UPDATE] ассемблерные листинги к классическим алгоритмам сравнения

For example x86 gcc 7.1 will for C++ source:

bool compare(int x, unsigned int y) {
    return (x < y); // "wrong" (will emit warning)
}

bool compare2(int x, unsigned int y) {
    return (x < 0 || static_cast<unsigned int>(x) < y);
}

bool compare3(int x, unsigned int y) {
    return static_cast<long long>(x) < static_cast<long long>(y);
}

Produce this assembly (godbolt live demo):

compare(int, unsigned int):
        cmp     edi, esi
        setb    al
        ret

compare2(int, unsigned int):
        mov     edx, edi
        shr     edx, 31
        cmp     edi, esi
        setb    al
        or      eax, edx
        ret

compare3(int, unsigned int):
        movsx   rdi, edi
        mov     esi, esi
        cmp     rdi, rsi
        setl    al
        ret

Взято вот здесь:

https://stackoverflow.com/a/44070807/73747

★★★★★

Последнее исправление: cvv (всего исправлений: 10)

В чём конкретно проблема я не понимаю

LINUX-ORG-RU ★★★★★
()

Я поиграю в угадайку.

Автор столкнулся на практике с тем, что

unsigned int ui = 1;
int si = -1;
printf("%d\n", ui > si);

напечатает 0.

Его не устраивает, что -1 оказывается больше, чем 1, и теперь он ищет выход из сложившейся ситуации.

Угадал?

i-rinat ★★★★★
()
Ответ на: комментарий от EXL

Они генерят в это случае предупреждение?

GCC и Clang генерят, если включишь -Wsign-compare. Эта опция входит в -Wextra, но не входит в -Wall.

i-rinat ★★★★★
()
Ответ на: комментарий от EXL

Есть, кстати, одна очень подлая ошибка, на которую предупреждений я ещё не видел. Если делаешь операции типа u64 = u32 * u32, не скастовав один из u32 в u64 перед умножением, получаешь сюрприз с переполнением и неожиданным результатом.

i-rinat ★★★★★
()
Последнее исправление: i-rinat (всего исправлений: 1)
Ответ на: комментарий от i-rinat

Скажем, я узнал что существует заметно больше способов решения этой проблемы чем я предполагал. Поэтому мне интересен чужой опыт.

Естественно речь о ситуациях где отказаться ни от знаковых, ни от беззнаковых никак нельзя.

Мой основной способ решения этой проблемы через расширение разрядности.

cvv ★★★★★
() автор топика
Последнее исправление: cvv (всего исправлений: 1)
Ответ на: комментарий от i-rinat

А статический анализатор clang’а ловит подобную штуку?

но не входит в -Wall.

Ох уж эти -Wextra, -Wall, -Weverything, -pedantic, -Walmost-all, -Walmost-everything.

EXL ★★★★★
()
Ответ на: комментарий от EXL

А статический анализатор clang’а ловит подобную штуку?

Вряд ли. Не видел такой проверки там, по крайней мере.

Пробовал плагином к clang’у ловить, но там очень много фолзов. Собственно, кроме найденных вручную багов больше ничего не всплыло, одни фолзы. Если кто-то придумает, как эти фолзы фильтровать, можно и чекер к scan-build прикрутить.

i-rinat ★★★★★
()
Ответ на: комментарий от grem

Не читай - сразу отвечай. Я думал опять про сравнение float.

RazrFalcon ★★★★★
()
Ответ на: комментарий от cvv

Мой основной способ решения этой проблемы через расширение разрядности.

Ну ок, допустим что одно из чисел uint64_t и другое это int64_t, надо узнать, больше ли одно другого.

bool test(uint64_t a, int64_t b)
{
  return a > b; // wrong
}
Допустим, никакого __int128 или аналога нет, чтоб в него скастовать и сравнивать. Как это решать? Можно написать отдельное сравнение, которое сначала проверяет что int64_t меньше нуля. Если меньше, значит такой int64_t точно меньше uint64_t:
bool test(uint64_t a, int64_t b)
{
  if (b < 0)
  {
    return true;
  }
  return a > b;
}
А какие еще могут быть варианты?

SZT ★★★★★
()

Перестань сравнивать бананы с гайками, и всё сразу наладится. Про сравнение int < 0 тут выше уже сказали; затем делай перевод в uint tmp=…;

zendrz ★★
()
Ответ на: комментарий от zendrz

никаких tmp тут не надо, компилятор и так скастует в unsigned тип при сравнении.

Можно так сделать

bool test(uint64_t a, int64_t b)
{
  if (b < 0)
  {
    return true;
  }
  return a > (uint64_t)b;
}
чтоб компилятор варнинг не писал лишний.

SZT ★★★★★
()
Последнее исправление: SZT (всего исправлений: 1)
Ответ на: комментарий от SZT

Ок, это уже частности. Безусловно, явный каст необходим, как и проверка перед ним.

zendrz ★★
()
Ответ на: комментарий от SZT

Я обычно пишу static_cast<int64_t>(a) < b потому что uint64_t в моём коде обычно означает, что оно не может быть отрицательно, а не то что оно может быть больше, чем влезет в int64_t.

q0tw4 ★★★★
()

Естественно речь о ситуациях где отказаться ни от знаковых, ни от беззнаковых никак нельзя

Похоже на лечение симптома вместо болезни. В моей практике такой необходимости не было ни разу, было бы интересно если вы опишете кейс. В моём понимании допустимо сравнивать только одинаковые величины, а у одинаковых величин по определению совпадают области значений (которые могут быть дополнительно сужены, но это здесь не имеет значение), следовательно для них используются одинаковые типы, следовательно нет такой проблемы как сравнение знаковых с беззнаковыми. Следовательно нужно начать с того чтобы использовать правильные типы, или понять почему вы сравниваете разные величины и как этого избежать.

А так-то для оригинальной задачи вы решения сами привели. Замечу только что последний вариант некорректен по меньшей мере без static_assert(sizeof(long long) > sizeof(int));

slovazap ★★★★★
()
Ответ на: комментарий от cvv

Мой основной способ решения этой проблемы через расширение разрядности.

Компиляторы FPC и Delphi тоже так решают проблему, выдавая заодно предупреждение.

byko3y ★★★★
()
Ответ на: комментарий от byko3y

Это неплохо. D решает через двойное условие.

Меня удивляет что С-компиляторы ограничиваются только ворнингом в лучшем случае.

cvv ★★★★★
() автор топика
Ответ на: комментарий от slovazap

Я не ищу решение. Я ищу альтернативный опыт.

cvv ★★★★★
() автор топика

я честно говоря не понимаю, как можно «сравнивать» быстро не так, как это делает процессор.

как я понимаю, int приводится в unsigned перед сравнением, а это (0xffffffff < 0x1)

example_cat
()
Ответ на: комментарий от cvv

раз уж стали делиться как в других языках.

В Rust вообще не скомпилируется:

pub fn compare (x: i32, y: u32) -> bool {
    return x < y;
}
error[E0308]: mismatched types
 --> <source>:2:16
  |
2 |     return x < y;
  |                ^ expected i32, found u32

Нужно явно писать compare, compare2 или compare3, типа такого

pub fn compare (x: i32, y: u32) -> bool {
    return (x as u32) < y;
}

pub fn compare2 (x: i32, y: u32) -> bool {
    return x < 0 || (x as u32) < y;
}

pub fn compare3 (x: i32, y: u32) -> bool {
    return (x as i64) < (y as i64);
}
fsb4000 ★★★★★
()
Последнее исправление: fsb4000 (всего исправлений: 1)
Ответ на: комментарий от cvv

Меня удивляет что С-компиляторы ограничиваются только ворнингом в лучшем случае.

По историческим причинам. Сейчас идет тенденция к устранению undefined behaviour из языка, хоть и пространства для этого не так много. Изначально язык был сделан так, что кол-во ошибок компиляции и выполнения сведено до абсолютного минимума, и программист должен сам волноваться о том, правильно ли его програма работает или нет.

byko3y ★★★★
()
Ответ на: комментарий от byko3y

да нет никакого UB. просто хипстеры плетут что-то про «стандарт предписывает» и дальше бред сивой кобылы. тем временем, компилятор просто действует согласно правилам приведения типов. и они не менялись лет так цать. но ведь читать книжки по сишечке не надо, надо смело писать фигню, получать фигню и обвинять компилятор и даже стандарты.

Iron_Bug ★★★★★
()
Ответ на: комментарий от Iron_Bug

да нет никакого UB. просто хипстеры плетут что-то про «стандарт предписывает» и дальше бред сивой кобылы. тем временем, компилятор просто действует согласно правилам приведения типов. и они не менялись лет так цать. но ведь читать книжки по сишечке не надо, надо смело писать фигню, получать фигню и обвинять компилятор и даже стандарты.

Зато на такой код компилятор ваще не ругается:

[del@thinkpad int]$ cat test.c 
int foo(int a, unsigned b) {
  return a < (int)b;
}
[del@thinkpad int]$ gcc -c -std=c11 -Wall -Wextra test.c 
[del@thinkpad int]$ 

Хотя тут каст unsigned к signed, а это UB =)

DELIRIUM ☆☆☆☆☆
()
Ответ на: комментарий от DELIRIUM

это НЕ UB. поведение всех компиляторов в таком случае строго задекларировано в стандарте. кто не читал, тот ССЗБ. почему компилятор должен сообщать юзеру, что он идиот?

в некоторых компиляторах уже дошли до маразма: требуют явно декларировать обычное проваливание через кейсы в свитче. вот я радикально против такой фигни.

Iron_Bug ★★★★★
()
Последнее исправление: Iron_Bug (всего исправлений: 1)
Ответ на: комментарий от Iron_Bug

Да ну? Переполнение знакового целого не UB? Ну-ну.

DELIRIUM ☆☆☆☆☆
()
Ответ на: комментарий от DELIRIUM

каст unsigned к signed, а это UB

Нет, это implementation-defined.

6.3.1.3 Signed and unsigned integers

1 When a value with integer type is converted to another integer type other than _Bool, if the value can be represented by the new type, it is unchanged.

2 Otherwise, if the new type is unsigned, the value is converted by repeatedly adding or subtracting one more than the maximum value that can be represented in the new type until the value is in the range of the new type.

3 Otherwise, the new type is signed and the value cannot be represented in it; either the result is implementation-defined or an implementation-defined signal is raised.

Нужно смотреть в документацию к компилятору. У GCC по этому impl-defined пункту написано в мануале:

For conversion to a type of width N, the value is reduced modulo 2^N to be within range of the type; no signal is raised.

Так что всё норм.

i-rinat ★★★★★
()
Ответ на: комментарий от i-rinat

Хм, ок. Буду иметь в виду. В любом случае, ревью в нормальном проекте это не пройдёт =)

DELIRIUM ☆☆☆☆☆
()
Ответ на: комментарий от DELIRIUM

а это UB

Нет.

If the destination type is signed, the value is unchanged if it can be represented in the destination type; otherwise, the value is implementation-defined.

А с С++20 и С2X уже будет строго определено, а не реализацией

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p1236r1.html

https://i.imgur.com/yXxaDcf.png

fsb4000 ★★★★★
()
Ответ на: комментарий от Iron_Bug

поведение всех компиляторов в таком случае строго задекларировано в стандарте.

Лол, нет. Там написано: implementation-defined.

кто не читал, тот ССЗБ. почему компилятор должен сообщать юзеру, что он идиот?

Смелое заявление для человека, который явно текст стандарта не открывал.

i-rinat ★★★★★
()
Ответ на: комментарий от i-rinat

не, ну так не надо приводить типы с потерей данных. это уже даже не только от компилятора будет зависеть, а от представления данных в машине.

Iron_Bug ★★★★★
()
Ответ на: комментарий от cvv

Так задумано изначально K & R.

Керниган не участвовал в разработке дизайна языка.

i-rinat ★★★★★
()
Ответ на: комментарий от Iron_Bug

почему компилятор должен сообщать юзеру, что он идиот?

плох тот компилятор, который не мечтает доминировать над юзером

Egor_
()
Ответ на: комментарий от Iron_Bug

это НЕ UB. поведение всех компиляторов в таком случае строго задекларировано в стандарте. кто не читал, тот ССЗБ. почему компилятор должен сообщать юзеру, что он идиот?

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

byko3y ★★★★
()
Ответ на: комментарий от byko3y

ЯП не обязан обслуживать идиотов. предполагается, что человек, который пишет код, понимает, что он делает. я вообще не понимаю таких претензий. я считаю, что те, кто не способен осилить простейшую логику, не должны приближаться к компьютеру. им не поможет ни компилятор с идиотскими ворнингами, ни даже специально приставленный человек с палкой. идиотизм неизлечим. просто не надо тащить всякое в профессию.

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

и нет ничего более бесячего, чем «предупреждения» компилятора о таких вещах. ты можешь их использовать вполне сознательно и это НЕ ошибка, это один из вариантов сознательного использования возможностей языка. и когда компилятор вдруг начинает вынуждать тебя писать какие-то идиотские комментарии в switch или принудительно включать подавления ненужных в принципе ворнингов - это просто пик маразма. ненависть возникает просто такая, что хочется поубивать уродов, из-за которых компилятор превращается в непонятно что.

Iron_Bug ★★★★★
()
Последнее исправление: Iron_Bug (всего исправлений: 4)
Ответ на: комментарий от DELIRIUM

ты не поверишь, но ДА. именно так. признай, что если разработчик понимает, что он пишет, то это ему не нужно. за 20+ лет программирования (а если посчитать не профессиональное программирование, то все 30) я никогда не нуждалась в подобном странном софте. и до сих пор не нуждаюсь.

ты же не проверяешь периодически, обосрался ты или нет. это детей надо проверять. а взрослых не надо. вот примерно такая аналогия.

Iron_Bug ★★★★★
()
Последнее исправление: Iron_Bug (всего исправлений: 2)
Ответ на: комментарий от Iron_Bug

никогда не нуждалась в подобном странном софте. и до сих пор не нуждаюсь.

Выше от тебя было заявление о том, что преобразование unsigned int в int определено стандартом. Это явная ошибка. Как минимум, одно заблуждение, потенциально приводящее к дефекту кода, уже есть. Сколько ещё таких сюрпризов оставлено тобой в написанном коде?

Удивительно, как за столько лет работы до тебя ещё не дошло, что люди совершают ошибки. Все. Хотя, если намеренно выбирать такую работу, где никто не может тебе на ошибки указать, можно и протянуть двадцать лет в полной уверенности своей непогрешимости.

i-rinat ★★★★★
()
Ответ на: комментарий от i-rinat

так я же не привожу типы с потерей данных. я не псих. или если это делается, то я уверена, какие именно там данные и почему это безопасно.

я с ассемблера программировать начинала. не надо меня пугать страшилками про типы данных и ужасы прямых указателей. и да, я против замусоривания компиляторов ненужной фигнёй. надо повышать уровень образования, а не заниматься маразмом.

Iron_Bug ★★★★★
()
Последнее исправление: Iron_Bug (всего исправлений: 3)
Ответ на: комментарий от Iron_Bug

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

Дай угадаю. Ревью изменений кода вы не производите, потому что твой код всегда идеален?

i-rinat ★★★★★
()
Ответ на: комментарий от i-rinat

так это пример школярского косяка. я такие косяки уже лет 20 назад не делала. даже учась в школе уже не делала. сишечка - очень простой ЯП. я вообще не понимаю проблем тех, кто не смог осилить столь простые правила. и не надо под них портить компиляторы. пусть они валят на пистоны, жабы, куда угодно. там всё в песочницах, анально огорожено, тормозно и «безопасно». сишечка - не про такую «безопасность». она про свободу выбора и про ответственность за эту свободу.

Iron_Bug ★★★★★
()
Последнее исправление: Iron_Bug (всего исправлений: 1)
Ответ на: комментарий от i-rinat

при чём тут ревью? я не только код писала, я много чего проверяла. я постоянно собираю, правлю и патчу кучу чужого кода. по работе и просто потому что я собираю весь софт из сорцов. и я вижу косяки просто при просмотре кода. мне не нужны костыли. я дебажу чужой софт, правлю кучу косяков с выделением памяти. я не понимаю, почему люди не могут осилить простые правила.

Iron_Bug ★★★★★
()
Последнее исправление: Iron_Bug (всего исправлений: 2)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.