patternMinor
Comparison using only bitwise operators (and return -1 or 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.
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$).
$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.