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.


migrated from cstheory.stackexchange.com Dec 23 '12 at 4:06

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\begingroup$ You try all values in your range and see if it works. $\endgroup$ – adrianN Dec 19 '12 at 14:56
  • $\begingroup$ @adrianN Well, what if the integer is 64 bit? It would take ages to check all values. And even then, you would only be able to check that it returns true for equal values. Checking it does not give false positives will take quadratic time. $\endgroup$ – Paresh Dec 23 '12 at 6:44

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.