Битовая бомба: тайный код на чистом С | 06 ноября 2023 года, 10:47

У Лизы в институте курс программирования на чистом С, по сути первый семестр. На третьем месяце обучения им приходится делать вот такие домашки:

нужно написать функцию int isLess(int a, int b) исключительно на операторах ! ~ & ^ | + <> и константах 0-255 включительно без использования больших констант типа 0xffffffff, без использования условных конструкций и циклов (if, do, while, for, switch, и т.д.), без макросов, без вызовов любых функций, никаких &&, ||, -, ? никаких других типов данных кроме int.

Есть очевидный ответ y + (~x + 1) >> 31) & 1, то есть вычитается y из x и дальше смотрим на знак. но для пары чисел -2147483648 [0x80000000] и 2147483647[0x7fffffff] алгоритм сбоит – он возвращает ноль, а тесты ожидают единицу. Это потому, что идет выход за 32 бита int при вычислении разницы.

Разумеется, я спросил и у ChatGPT, и у Google Bard. От них помощи ноль. Они не понимают проблемы из предыдущего параграфа. А если и понимают, предлагают тупое решение, которое видно невооруженным глазом, что не работает.

Мы в итоге после часа ковыряния нашли правильное решение в четыре руки. Лиза молодец, практически весь путь сама прошла, плюс гугл поиск. Решение вышло очень сложное, но работает. Там около 15 bitwise операций в итоге. После свертки функций и превращения в одно выражение со скобками — а так требуется по условию задачи — понять что там вообще происходит невозможно. Интересно в архитектурных университетах программирование проходят.

ответ: ((~(((a ^ b) >> 31) ^ 1) ^ 1) & ((a + (~b + 1)) >> 31) & 1) | (((a ^ b) >> 31) & 1) & ((a >> 31) & 1);

Самое интересное, что wolframalpha при запросе simplify и выражение, упрощает его так, что оно начинает не проходить тесты. То есть, wolframalpha конечно тоже не знает про ограничение в 32 бита.