Liza has a programming course at her institute where they study pure C, essentially it’s their first semester. By the third month of their study, they have to handle homework like this:
you need to write a function int isLess(int a, int b) using exclusively the operators ! ~ & ^ | + << >> and constants ranging from 0 to 255 inclusively without using large constants like 0xffffffff, without conditional structures and loops (if, do, while, for, switch, etc.), without macros, without calling any functions, no &&, ||, -, ?, no other data types besides int.
There’s an obvious answer y + (~x + 1) >> 31) & 1, which means subtracting y from x and then observing the sign. But for a pair of numbers -2147483648 [0x80000000] and 2147483647 [0x7fffffff] the algorithm fails—it returns zero, whereas the tests expect one. This is because it exceeds the 32 bits of int while calculating the difference.
Naturally, I asked both ChatGPT and Google Bard. No help from them; zero. They don’t understand the issue from the previous paragraph. And if they do understand, they suggest a dumb solution which is obviously non-working to the naked eye.
After an hour of tinkering, we finally found the right solution together. Liza did a great job, largely figuring things out herself, plus using Google search. The solution turned out to be very complex, but it works. It involved about 15 bitwise operations in the end. Once the functions have been combined and transformed into a single expression with parenthesis—as the task requirements specify—it’s impossible to understand what’s happening. I wonder if architecture universities cover programming.
Solution: ((~(((a ^ b) >> 31) ^ 1) ^ 1) & ((a + (~b + 1)) >> 31) & 1) | (((a ^ b) >> 31) & 1) & ((a >> 31) & 1);
The most interesting part is that when I ask Wolfram Alpha to simplify the expression, it simplifies it into something that fails the tests. It seems that Wolfram Alpha does not know about the 32-bit limitation either.
Hi, I'm Rauf Aliev. 