6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What makes you believe that "arithmetic minus requires more steps with only bitwise operators"? As I understand it, that's probably not true on most modern processors. You might want to test that assumption (e.g., by benchmarking different implementations). $\endgroup$ – D.W. Dec 22 '16 at 17:25
  • $\begingroup$ @D.W. You might be right. In my comment I meant in that situation I was dealing with a processor with a very minimal instruction set and was restricted to use only bitwise operators where subtraction operator was not available in my operator list, I had to implement minus first. That led me to believe that it might be some extra steps needed to be taken. I didn't realize that there might be different bitwise operator sets available for different processors, and didn't stress my specification in the question. $\endgroup$ – Known Zeta Dec 23 '16 at 22:59
5
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You can break it down into a tree so that you only need a number of ORs equal to log2(bits) by doing it in steps as shown in my answer. $\endgroup$ – Extrarius Dec 20 '16 at 22:07
  • 3
    $\begingroup$ Changing the two shifts in my answer to a single circular shift of the same amount would result in exactly $\log_2 n$ ORs $\endgroup$ – Extrarius Dec 20 '16 at 22:14
  • $\begingroup$ Yes, I see it now, very good idea. Sorry, I was struggling with the formatting after my initial comment, so I have read your answer afterwards. $\endgroup$ – Evil Dec 20 '16 at 22:17
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Duplicate the line with the 'or' and change the constants to successive powers of 2. Eg: C = C or (C >> 2) or (C << 2) then 4, 8, etc. You can also replace the two shifts on each line with a single circular shift: C = C or (C rol 1); C = C or (C rol 2); etc $\endgroup$ – Extrarius Dec 20 '16 at 21:47
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @Evil, you are right, it might be cheating. And I really like your 6-operation solution -- that is beautiful! Far nicer than my example. I encourage you to add it to your answer, as an addendum, or as a second answer (even if it is cheating). $\endgroup$ – D.W. Dec 21 '16 at 6:56
2
$\begingroup$

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.

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