HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
returncomparisonbitwiseonlyusingandoperators

Problem

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.

Solution

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$).

Context

StackExchange Computer Science Q#67693, answer score: 5

Revisions (0)

No revisions yet.