CODEWITHSUNDEEP
bitwise-operatorsxorbitwise-and
John Zane
John Zane

Reputation: 888

XOR from only OR and AND

How do you do the XOR bitwise operation if you only have available the AND and the OR operations?

Upvotes: 14

Views: 74950

Answers (11)

Paul R
Paul R

Reputation: 212929

If you have arithmetic operators such as + and - in addition to bitwise AND (&) and OR (|) then you can do bitwise XOR like this:

int bitwise_XOR(int a, int b)
{
    return (a + b) - (a & b) - (a & b);
}

The reason this works is that we are doing a full add, which is equivalent to XOR when the sum for any given bit position is <= 1, and then we're correcting for the case where a carry is generated (1 + 1) by subtracting 2 * (a & b).

Note that this works even when the intermediate terms overflow, assuming we have "normally behaved" integers (2's complement, modulo 2 wraparound for overflow, etc).

Upvotes: 5

Max Kleiner
Max Kleiner

Reputation: 1612

  PrintF('%-10s XOR',[inttobinbyte((10 OR 12)-(12 AND 10))])

00000110 XOR

Upvotes: 0

jkobject
jkobject

Reputation: 69

in python 

...:def xor(a,b):
...:     c = (not a) and b
...:     d = (not b) and a
...:     e = not c
...:     f = not d
...:     g = e and f
...:     h = not g
...:     return h

Upvotes: -1

MGoksu
MGoksu

Reputation: 529

"The systems ({T, F}, and) and ({T, F}, or) are monoids."

"The system ({T, F}, xor) is an abelian group" which has the property of invertibility unlike monoids.

Therefore, 'and' and 'or' fail to construct 'xor' operation.

Source: https://en.wikipedia.org/wiki/Exclusive_or#Relation_to_modern_algebra

Upvotes: 7

Zack
Zack

Reputation: 1703

(a XOR b) = ((a OR b) - (a AND b)), or in other words, the union set minus the intersection set.

Code example (in javascript):

var a = 5;
var b = 12;
var xor = (a | b) - (a & b); // result: 9

Upvotes: 12

Callie J
Callie J

Reputation: 31296

Creating my own scripting language - ChrisScript - you just need something like:

#!/bin/chrish

bit XOR (bit A, bit B)
{
   bit notA;
   bit notB;

   IF (A == 0) notA = 1 ELSE notA = 0;
   IF (B == 0) notB = 1 ELSE notB = 0;

   F = ((A && notB) || (notA && B));

   RETURN F;
}

Even without NOT, it can be emulated like this. But this is the best solution you're going to get without having some form of inverter. I find it hard to believe you don't have some form of inverter availble -- what scripting environment are you using?

Upvotes: 4

user1527227
user1527227

Reputation: 2238

In C: x ^ y = (x & ~y) | (~x & y)

Upvotes: 4

T.E.D.
T.E.D.

Reputation: 44794

Wikipedia's entry on XOR goes over this in detail. Probably a good first place to check before aksing a SO question.

If you already have bits you don't care about masked off, it seems to me the easiest way to do it (as far as writing the code goes anyway) is to just use your not equal operator.

Upvotes: 2

Lou Franco
Lou Franco

Reputation: 89142

Truth table for AND

  A  B  AND
  T  T  T
  T  F  F
  F  T  F
  F  F  F

Truth table for OR

  A  B  OR
  T  T  T
  T  F  T
  F  T  T
  F  F  F

Truth table for XOR

  A  B  XOR
  T  T  F
  T  F  T
  F  T  T
  F  F  F

So, XOR is just like OR, except it's false if A and B are true.

So, (A OR B) AND (NOT (A AND B)), which is (A OR B) AND (A NAND B)

  A  B  OR  AND NAND [(A OR B) AND (A NAND B)]
  T  T  T    T    F        F
  T  F  T    F    T        T
  F  T  T    F    T        T
  F  F  F    F    T        F

Not sure if it can be done without NOT or NAND

Upvotes: 17

Noray
Noray

Reputation: 165

i am pretty sure that the formula below is correct:

a xor b = not((a and b) or not(a+b))

Upvotes: -1

developer
developer

Reputation: 53

Best advice is to look up XOR in reference manuals and encyclopedia sites on the net and then write code or script which does the same as the description of what a XOR built-in function does and use your own return or status values. We can not tell you how to do that type of bit compares from within the software community.

Upvotes: -4

Related Questions