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.

Improve this question
$\endgroup$
5
  • $\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, 2016 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, 2016 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, 2016 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, 2016 at 19:36
  • $\begingroup$ A XOR B is 0 if and only if A=B. What more do you need? $\endgroup$
    – Raphael ♦
    Sep 28, 2016 at 6:04

3 Answers 3

Reset to default
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.

Improve this answer
$\endgroup$
0
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.

Improve this answer
$\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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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