CODEWITHSUNDEEP
cbitxor
sebi
sebi

Reputation: 837

How to make bit wise XOR in C

I'm trying to get into C programming, and I'm having trouble writing a bitwise XOR function with only ~ and & operators. Example: bitXor(4, 5) = 1. How can I achieve this?

So far I have this:

int bitXor(int x, int y) {

    return z;
}

Upvotes: 12

Views: 76638

Answers (7)

douyu
douyu

Reputation: 2599

int bitXor(int x, int y) {
  return ~(~(~x & y) & ~(x & ~y));
}

explanation:

x ^ y = (~x & y) | (x & ~y) = ~(~(~x & y) & ~(x & ~y))

The last procedure is making use of De Morgan's laws

Upvotes: 0

MVP
MVP

Reputation: 21

You can perform a bitwise XOR operation in c using the ^ operator.

Upvotes: 0

vaibhav
vaibhav

Reputation: 11

int xorro(a, b)
{
    if (a == b)
        return 0;
    return 1; 
}

Upvotes: -3

David Schwartz
David Schwartz

Reputation: 182769

Using NAND logic:

int bitNand(int x, int y)
{
    return ~ (x & y);
}

int bitXor(int x, int y)
{
    return bitNand( bitNand(x, bitNand(x, y)),
                    bitNand(y, bitNand(x, y)) );
}

Or:

int bitXor(int x, int y)
{
    return ~( (x & y) | (~x & ~y) );
}

Or:

int bitXor(int x, int y)
{
    return (x & ~y) | (~x & y);
}

Of course this is easier:

int bitXor(int x, int y)
{
    return x ^ y;
}

Upvotes: 27

Mike
Mike

Reputation: 49403

Well, let's think about this. What does XOR do?

x   y    XOR
------------
0   0     0
1   0     1
0   1     1
1   1     0

So how do we turn that into a function? Let's think about AND, and the inverse order of AND (~x&~y) (this happens to be NOR):

              (~x&~y)
 x   y   AND    NOR   
 ---------------------
 0 & 0  = 0      1    
 1 & 0  = 0      0 
 0 & 1  = 0      0
 1 & 1  = 1      0

Looking at those two outputs, it's pretty close, all we have to do is just NOR the two previous outputs (x AND y) (x NOR y) and we'd have the solution! 

  (a)       (b)    ( a NOR b )
x AND y   x NOR y    ~a & ~b
-------------------------------
   0         1          0
   0         0          1
   0         0          1
   1         0          0

Now just write that out:

a = ( x & y )
b = ( ~x & ~y )
XOR'd result = (~a & ~b)

BINGO! Now just write that into a function

int bitXor(int x, int y) 
{
    int a = x & y;
    int b = ~x & ~y;
    int z = ~a & ~b;
    return z;
}

Upvotes: 40

user529758
user529758

Reputation:

I want it to write it only with ~ and &

That counts for NAND gates, right? After studying this circuit diagram:

int z = ~ ((~(a & ~(a & b)) & (~(b & ~(a & b)));

The same applies for the non-bitwise, i. e. logic one as well, just substitute ! instead of the ~.

Upvotes: 0

Daniel Fischer
Daniel Fischer

Reputation: 183888

It is easily seen that

x ^ y = (x | y) & ~(x & y)

so it remains to express | by only & and ~. De Morgan's laws tell us

x | y = ~(~x & ~y)

Upvotes: 8

Related Questions