XOR from only OR and AND

R

11

14

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

Remittee answered 17/1, 2011 at 16:8 Comment(6)

I am pretty sure that you need NOT as well. – Butternut 17/1, 2011 at 16:11

@Oded nope, I just want to know. I'm programming in a scripting environment which only has AND and OR, but neither NOT or XOR, and I need XOR. You guys at StackOverflow sure are quick to judge something as homework. Also, I don't understand that link, I had already looked at it before posting the question. – Remittee 17/1, 2011 at 16:13

I'm pretty sure you need a NOT to create an XOR = (a && !b) || (!a && b) is the simplest way to put it – Stratocracy 17/1, 2011 at 16:17

You need NOT otherwise it's not possible. If it doesn't have NOT (what scripting environment is this that doesn't have NOT -- that's a fairly fundamental omission) -- then you should just be able to use conditional logic to invert the bit... if (x == 0) x = 1, then it should be straightforward. – Vivianaviviane 17/1, 2011 at 16:18

No NOT? Seriously? That's not funny. (Oh ana @nixon: NOR works as well; but it's no fun with NAND and NOR) – Dewain 17/1, 2011 at 16:19

Is it permissible to use arithmetic operators, such as + and - ? If so then see my answer below... – Collocation 21/3, 2011 at 11:49

V

4

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?

Vivianaviviane answered 17/1, 2011 at 16:24 Comment(3)

A very limited Javascript environment. – Remittee 17/1, 2011 at 16:28

Also, I need to do it int by int, not bit by bit, since I can't get individual bits, for lack of bit shifting operators. – Remittee 17/1, 2011 at 16:33

Define "very limited" -- do you have the actual javascript engine you're using (e.g., Microsoft JScript)? Is this part of some proprietary thing, if so, what product and version? It would be nice to have as much information about your environment as possible. – Vivianaviviane 17/1, 2011 at 16:56

S

18

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

Sarisarid answered 17/1, 2011 at 16:18 Comment(3)

I think we all know what those operations do an how their truth tables look like. The question is, can you combine the first two to form the third, and if so, how? – Dewain 17/1, 2011 at 16:20

I was starting my answer in the event that it was homework. To be a direction rather than an answer. I don't think it can be done. – Sarisarid 17/1, 2011 at 16:24

Since the latter half which is (NOT (A AND B)) is the same as ((NOT A) OR (NOT B)), the entire can also be written as (A OR B) AND ((NOT A) OR (NOT B)), or (A+B)(!A+!B). The (A+B) handles the part where either A or B are true, the (!A+!B) handles when both A and B are false, the AND in between makes sure that both parts are true for the entire expression to be true. – Iodic 26/3, 2023 at 22:14

R

12

(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

Renz answered 1/12, 2017 at 6:48 Comment(0)

M

6

"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

Mathia answered 19/10, 2015 at 13:49 Comment(0)

C

5

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

Collocation answered 21/3, 2011 at 11:47 Comment(5)

gcc 6.x onward is smart enough to transform this to a ^ b – Foible 11/2, 2019 at 16:2

(a | b) - (a & b) may be more efficient. It starts with non-exclusive OR, then clears the bits where both inputs were set. (The value being subtracted from always has a set bit at those positions, so there's no borrow/carry propagation into other bits.) Credit tor @harold for suggesting this in a comment on How to XOR on a CPU that doesn't have an XOR instruction. Oh, that's Zack's answer here. – Menial 29/11, 2023 at 3:35

@PeterCordes: yes, I like that solution - I think one of the other more recent answers uses this too. – Collocation 29/11, 2023 at 15:51

@PeterCordes isn't it possible to do this with (a | b) & ~(a & b)? This has the advantage that only uses bitwise primitives (and, or, not) without the need for a subtraction – Gittern 24/7 at 18:6

@olivarra1: Yeah, you could do that for cases where that advantage is relevant. If doing it with CPU instructions on a CPU that has a native sub, or, and and, but not xor, (a|b) - (a&b)` is fewer operations, and sub costs the same as bitwise booleans on normal CPUs (e.g. single uop for any ALU). – Menial 24/7 at 20:41

V

4

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?

Vivianaviviane answered 17/1, 2011 at 16:24 Comment(3)

A very limited Javascript environment. – Remittee 17/1, 2011 at 16:28

Also, I need to do it int by int, not bit by bit, since I can't get individual bits, for lack of bit shifting operators. – Remittee 17/1, 2011 at 16:33

Define "very limited" -- do you have the actual javascript engine you're using (e.g., Microsoft JScript)? Is this part of some proprietary thing, if so, what product and version? It would be nice to have as much information about your environment as possible. – Vivianaviviane 17/1, 2011 at 16:56

M

4

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

Mancini answered 29/8, 2014 at 16:53 Comment(0)

P

2

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.

Philippines answered 17/1, 2011 at 16:19 Comment(0)

B

0

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

00000110 XOR

Bartholomeus answered 1/3, 2021 at 15:31 Comment(0)

O

-1

i am pretty sure that the formula below is correct:

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

Orth answered 17/1, 2011 at 16:18 Comment(2)

Read the question again. NOT is not available. – Dewain 17/1, 2011 at 16:20

+ is also not a boolean operator last I checked let alone an AND or OR operation – Staub 13/1, 2022 at 7:38

Q

-1

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

Questionary answered 19/1, 2020 at 23:44 Comment(0)

E

-4

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.

Enteric answered 17/1, 2011 at 16:17 Comment(0)

Recommended topics

Hot tags