-1

I had an interview question about implementing XOR in terms of ADD/SUB and branches:

Implement Xor operation between two numbers using the following commands only:

  1. Add
  2. Sub
  3. Branch if equal
  4. Branch if not equal
  5. And

You can use registers r3 and r4 as extra space. Assume that register r1 stores the first number and r2 stores the second number

Community
  • 1
  • 1
HYAG
  • 25
  • 1
  • 3
  • 4
    That looks like a homework assignment. What is your question? – C.Evenhuis Dec 12 '18 at 10:00
  • 1
    And what have you tried so far? – Mike Dec 12 '18 at 10:19
  • It is an Intreview Question , i am trying to know how to get each bit by using add and sub – HYAG Dec 12 '18 at 10:23
  • 1
    This seems pointless, except for silly toy architectures like MARIE or LMC which are barely programmable and have ADD but not bitwise ops. All real CPUs have an XOR instruction, and there doesn't seem like any clear use-case for folding an XOR into an ADD or SUB when optimizing, because it's not at all simple. XOR is add-without-carry, but I don't think there's any efficient way to remove the carry propagation and just get XOR. So probably you need some kind of silly bit-at-a-time loop. I'm somewhat interested in seeing an answer to this, though. – Peter Cordes Dec 12 '18 at 10:42
  • without "carry" branching this sounds even more ridiculous than I thought at first... not sure what the ZF branching is good for in this case, except having hardcoded constants for 2^64 possibilities (if input registers are 32 bit). This is making me curious, I don't see how add+sub+jz/jnz can be connected to somewhat reasonable solution... (after spending 5min thinking about it, having "no clue" is usually bad sign in my case, like that the solution will be either utterly convoluted, or does not exist ... in this case it probably should exist (because it was I.question), but eluding me) – Ped7g Dec 12 '18 at 10:51
  • for example let's keep this to two bits... 00^00 = 00, 01^00 = 01, 01^01 = 00 ... but 01+01 = 10 ... you can do x+x to get all "possible carry" (although 11+11 = 100, not sure how that helps, would need to think more about, it's obvious in per-bit situation, but not so much in composition of multiple bits), but then you need to subtract that only where y did induce real carry and my brain gets stuck right there... would need at least `and`, but then the solution is trivial. Is there `and` from `add+sub+jz+jnz`? Don't see that either. – Ped7g Dec 12 '18 at 11:07
  • @PeterCordes what does this have to do with optimization, it is a question to understand if the interview candidate, and/or student doing homework understands how these operations work and bit manipulation. I might steal this one for interview candidates as well as we need folks that have the knack to do logical operations, and understand how things work deep down. – old_timer Dec 12 '18 at 12:02
  • 2
    `a + b = ((a & b) << 1) + (a ^ b)`, hence `a + b - ((a & b)+(a & b)) = a ^ b` – EOF Dec 12 '18 at 12:13
  • nice! From Ped7g's comment and the addition of the and. It does become trivial anding the numbers gives you the bit positions that have a carry problem. you can and the two numbers then subtract that result from each, no more carry problem. then you get an add without carry, an xor. but doing that with only two scratch registers doesnt work. EOFs solution does work with two scratch registers. the question stating xor as an add without carry which is not how it is defined it is an exclusive or, but that comment helps with the solution. – old_timer Dec 12 '18 at 12:20
  • @old_timer funnily enough, would there be `jc/jnc` jumps allowed, with enough scratch registers, I'm pretty sure it should be possible to solve it with add/sub only (with few loops going through separate bits, subtracting of 2\*\*n would detect trailing zeroes, so it's actually even possible to traverse it from bottom starting at 2\*\*0 I guess? The hurdle of 2 scratch may be too much, but I'm not going to dive into details, as Q was edited in different direction, `and` makes it lot less convoluted than anything carry based would ever be. – Ped7g Dec 12 '18 at 17:26
  • Can you please re-write your question to more closely represent the actual interview question? – old_timer Dec 13 '18 at 04:50

2 Answers2

7

Since a + b can be expanded to (a ^ b) + ((a & b) << 1), if +, -, &-operators are available, the following holds:

a ^ b == a + b - (a & b) - (a & b).

In fact, gcc 8.2.1 optimizes the following c-function

unsigned foo(unsigned a, unsigned b)
{
   return a + b - (a & b) - (a & b);
}

to the following x86-64 assembly with -O3:

foo:
    movl    %edi, %eax
    xorl    %esi, %eax
    ret

Consequently, neither of the branch-instructions are required, nor more than three registers (following is pseudo-assembly):

$r1 = a          //first argument
$r2 = b          //second argument
$r3 = $r1 & $r2  //one temp register is enough
$r1 = $r1 + $r2
$r1 = $r1 - $r3
$r1 = $r1 - $r3  //$r1 is the return value
EOF
  • 6,273
  • 2
  • 26
  • 50
  • 1
    This question is requesting it *without* AND. Can we still implement this in a non-looping way with beq / bne? I don't see how. – Peter Cordes Dec 12 '18 at 12:26
  • ُEDIT : You can use AND operation. – old_timer Dec 12 '18 at 12:31
  • this solution also allows for the preservation of r1 and r2 with two scratch registers. – old_timer Dec 12 '18 at 12:35
  • 3
    @PeterCordes The question was edited to allow `&`. Anyway, since subrtact-and-branch-if-not-zero is Turing-complete, it is certainly possible to implement `xor` with `add, sub, beq, bne`, but it might be difficult with only four registers. – EOF Dec 12 '18 at 12:35
  • 1
    I was thinking of something along the lines of shifting bits to the top (using `add same,same`) where ADD and XOR are equivalent for inputs with only the top bit (maybe) set. Then beq against zero and set a zero or 1 bit, and shift that into position with a loop. To do that for bits other than the LSB, we'd have to clear lower bits. But we can build up versions of the inputs with high bits cleared, and subtract from the original inputs... Maybe something like `O(k^2)` time where k is the number of bits; much better than `O(2^k)`. – Peter Cordes Dec 12 '18 at 13:03
  • Another thought: sub/jne is Turing complete, but maybe only with numbers encoded 1 bit per memory location or something. We don't know for sure that a one-instruction-set computer can usefully take advantage of multiple bits packed into a word / register for boolean ops. – Peter Cordes Dec 13 '18 at 03:30
5

With SUB you can get NOT

~a = ~0 - a

or if two's complement is used

~a = -a - 1

From AND and NOT you get NAND which is functional complete, thus you can do any logic functions easily. There are various ways to get XOR from those. One of them is

XOR from NAND

t = a NAND b
a ^ b = (a NAND t) NAND (b NAND t)

Alternatively

Another way

a ^ b = (b NAND ~a) NAND (a NAND ~b)

which can be translated to something like this

r3 = ~0 - r1  # ~a
r4 = r2 & r3  # b & ~a
r4 = ~r4      # b NAND ~a
r2 = ~0 - r2  # ~b
r2 = r2 & r1  # a & ~b
r2 = ~r2      # a NAND ~b
r1 = r2 & r4
r1 = ~r1      # a ^ b

but it won't be as efficient as utilizing the adder's property directly

You can find many other ways from exclusive or's equivalences

a ^ b = (a | b) & ~(a & b) = ~(~a & ~b) & ~(a & b)
a ^ b = ~(a & b) & (a | b) = ~(a & b) & ~(~a & ~b)

See Is XOR a combination of AND and NOT operators?

Related: XOR from only OR and AND

phuclv
  • 37,963
  • 15
  • 156
  • 475