Comparison using only bitwise operators (and return -1 or 0)

Question

I have to use only bitwise operators to compare two numbers (represented in two's complement), and return $-1$ (represented by all $1$'s) if the numbers aren't equal or return $0$ (represented by all $0$'s) otherwise.

Say $a$ and $b$ are $W$ bits long ($W$ is not necessarily $2^n$). I find it easy to find out if both numbers are equal using $\mathsf{XOR}$: just do it like $a\ \mathsf{XOR} \ b$ and I will obtain $0$ (all $0$'s) if the two are the same. However I stuck at trying to get $-1$ when the two numbers differ, since the result of $\mathsf{XOR}$ just says which position of the two numbers differ and I have no idea how I should turn a non-zero number into $-1$.

How can I convert a non-zero number into $-1$ in two's complement representation (all bits set to $1$), while keeping it $0$ when it's not non-zero, which is a step further for the simple $\mathsf{XOR}$ comparison?

Edit: In the situation this question was originated from, subtraction was not a native operator which could be directly used. The 5-operation solution from @Evil and the answer from @D.W. should also be perfectly right when an extended collection of operators, like the subtraction, were implemented.

Answer 1

The first step is to take $c = a \text{ XOR } b$, this will return $0$ if the numbers were equal or some bits set to $1$ otherwise. Now to calculate the result the $c$ variable should be ORed with its circular shifts, to propagate $1$ on the whole variable.

$c = c \text{ OR } (c \text{ ROL } 1)$
$c = c \text{ OR } (c \text{ ROL } 2)$
$c = c \text{ OR } (c \text{ ROL } 4)$
$\dots$
$c = c \text{ OR } (c \text{ ROL }(W / 2))$.

Using consecutive powers of two gives exactly $\log_2 n$ ROLs needed (credit for Extrarius, it works when you store the partial results back to $c$).

Answer 2

Since -1 in two's complement is all bits set, you need to figure out how to 'copy' any 1 bit into every location in the value. You can use "or" to take all the 1 bits from two sources, and you can use shifting to change the position of the 1 bits in a variable. For example, if you have 2-bit variables:

C = A xor B
C = C or (C >> 1) or (C << 1)

If, for example, C starts out as 0b10, then two "or" lines would be

C = 0b10 or 0b01 or 0b00 = 0b11 = -1

If, instead, C begins as 0b01, then you get:

C = 0b01 or 0b00 or 0b10 = 0b11 = -1

For larger variables, duplicated the OR line and change the constants to successive powers of two up to half the bit-width of your variables. For ex, for 16-bit variables:

C = A xor B
C = C or (C >> 1) or (C << 1)
C = C or (C >> 2) or (C << 2)
C = C or (C >> 4) or (C << 4)
C = C or (C >> 8) or (C << 8)

You can also replace the two shifts on each line with circular shifts of the same amount.

Answer 3

Here is a trick that is faster than the previous schemes on some architectures (namely, processors that don't natively support a rotate-left instruction). I'll present a scheme that works for 32-bit words; you can easily adjust it to any word size.

C = A xor B
C = C or (C >> 16)
C = C or (C >> 8)
C = C or (C >> 4)
C = C or (C >> 2)
C = C or (C >> 1)
D = C & 1
M = -D

Notice that there is any bit set in A xor B, then C will certainly have its low bit set, and thus D will be 1. In this case M will get set to the twos-complement negation of 1, i.e., to -1, which has the all-ones bit pattern. (The clever part here is the use of negation to spread a single bit to all of the bit positions, in a single instruction.)

So, if A is different from B, then M will get set to all-ones. On the other hand, if A is equal to B, then M will get set to all-zeros. This achieves your desired functionality.

My solution needs 13 operations (1 xor, 5 or's, 5 right-shifts, 1 and, and 1 negation). In comparison, Extrarius's solution needs 21 operations, so it is likely to be slower. On an architecture that supports circular left shifts, Evil's solution is faster, as it needs only 11 operations. However, if you're implementing in C, you'll need to be careful to make sure to use the right coding idioms so the compiler will generate rotate-left instructions rather than doing something slower. If you're on another platform that doesn't have a native instruction for rotate-left, then my solution above will be faster than Evil's solution.

Answer 4

This answer, like the previous one is not meant for the efficiency, please read @D.W. answer for that, and always check the output produced by the compiler (to find out if it understood and optimized the code) and check yourself if there is an improvement.
The idea is to check whether two numbers are equal under the strict requirement to use only bitwise operations.
The simplest version is to propagate all bits, which works no matter which one was set simply by ORing the number with all its ROLs: $$c = c \text{ OR } (c \text{ ROL } 1) \text{ OR } (c \text{ ROL } 2) \dots \text{ OR } (c \text{ ROL }(W - 1))$$ This is one line solution, it takes more terms than the previous one, but no intermediate assignments are used. ROLs are used to simply ignore the position of bit set. It also enables parallelism...

Another idea, with subtraction using only 5 operations $$\color{red}{-}(\color{blue}{((a - b) \text{ OR } (b - a))}\color{purple}{ >> (W - 1)})$$ It works in the following way: $\color{blue}{\text{two differences}}$ are calculated, if $a = b$ then both are zero and the sign bit is zero, otherwise one of the differences is negative and the second is positive, which ORed gives the sign bit set to one. The $\color{purple}{\text{sign bit is shifted to the last place}}$ yielding 1 as the result. $\color{red}{\text{The minus}}$ converts $1$ to $-1$, which gives all bits set to one in two's complement encoding.