Prove given equality check function works for all subset of integers

Question

I wrote a function to check equality between integers a and b using bitwise shift operators. Return value of 1 means both are Equal and 0 means unequal inputs.

int foo(int a, int b)
{
        return ((a>>= b<<= a) ? 1 : 0);
}

How can I prove theoretically that function foo() works for all values in subset of integer range including negative values. If it fails for certain values, can I theoretically find out for what set of values will foo() works correctly.

Answer 1

I don't think this is the right place for such questions, and maybe Stackoverflow or programming puzzles and code golf may be better suited. However, I'll try to answer the question nevertheless.

I do not think your code has anything to do with equality of two numbers.

Your code can be separated into three lines as:

b = b << a;

a = a >> b;

return a != 0 ? 1 : 0

Well, first of all, if the right side of such a shift operator is negative, the behavior is undefined in C99 and C11. So for negative values, you can't be sure what will happen. The behavior is also undefined if the right operand is greater than or equal to the width of the promoted left operand. See quote below from C11 standard, section 6.5.7:

If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

And, the behavior will indeed be undefined for most values, either for the first part, or for the second. For the very few cases where both are defined, you are essentially calculating:

$$\frac{a}{2^{b \cdot 2^a}}$$

and I have no idea how that would help in checking for equality. Basically, even if $a$ equals $b$, the above under integer division would be 0, and will give the wrong output.

In short, the behavior is undefined, and to get theoretical answers, you need to at least define the behavior theoretically and completely.