2
$\begingroup$

Is there a possibility to compute the result of an integer equality comparison by only using arithmetic or bitwise operations? Negative values use the two-complement representation.

I am looking for a generic algorithm, which results in two possible values for equality and inequality but not using comparison operations.

$\endgroup$
  • $\begingroup$ Something like this. However, it shall also yield a fixed value if A and B are not equal. This should only work for integer comparisons. $\endgroup$ – Max Sep 27 '16 at 18:56
  • $\begingroup$ Bitwise operations are possible. However, using the comparison operation must be avoided. No, is not language or architecture dependent. I'm looking for a generic algorithm to compute whether two values A and B are equal or not without using actual comparison operators. The result of the algorithm should be two different values indicating equality or inequality. $\endgroup$ – Max Sep 27 '16 at 19:13
  • $\begingroup$ It is absolutely language dependent. If you aren't using a language, how else can you program? $\endgroup$ – gardenhead Sep 27 '16 at 19:28
  • $\begingroup$ I updated the question. It is not language dependent since the algorithm should use arithmetic/bitwise operations which are generally language independent. $\endgroup$ – Max Sep 27 '16 at 19:36
  • $\begingroup$ A XOR B is 0 if and only if A=B. What more do you need? $\endgroup$ – Raphael Sep 28 '16 at 6:04
5
$\begingroup$

Let $W$ be the number of bits, $A, B$ integers to compare.

$Result = (NOT((A - B) \text{ OR } (B - A))) >> (W - 1)$.

Here NOT negates bits. $A - B$ and $B - A$ is zero iff numbers are equal otherwise they are of different signs which ORed together will give a negative number.
The result is $1$ if numbers are equal and $0$ otherwise.

$\endgroup$
1
$\begingroup$

Iff they're unequal their xor will have at least one bit set. You can test the resulting word for zero in various ways, for instance by or'ing all the bits together, or known bit hacks. Specifically, (Z-1)&(~Z & 1<<(wordsize-1)) to check if Z is zero, by seeing if subtracting 1 carries all the way to the high bit.

$\endgroup$
0
$\begingroup$

Since all arithmetic operations return an integer, and the result of an equality comparison must be a boolean, this is clearly impossible.

Edit for updated question:

This should do the trick in C:

int cmp(int a, int b) {
  return !!(a-b)

This function returns 0 if the argument are equal, and 1 otherwise.

If $a = b$, then $a-b=0$. The first bang (the logical not operator) will transform the 0 into a 1, and the second will transform it back into a 0.

If $a \neq b$, then $a - b \neq 0$. The first bang will then transform the result into 0, and the second to 1.

$\endgroup$

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.