How to make bit wise XNOR in C

Question

I'm having trouble writing a bitwise XNOR function with at most 7 ~ and | operators. Example: bitXnor(6, -5) = 2. How do I do this without &?

So far I have this:

int bitXnor(int x, int y) {
  return ~(~x | ~y);

but I'm getting the error:

ERROR: Test bitXnor(-2147483648[0x80000000],-2147483648[0x80000000]) failed...
...Gives -2147483648[0x80000000]. Should be -1[0xffffffff]

Answer 1

Negate (~) either parameter and XOR them (^)

int bitXnor(int x, int y) { 
  return x ^ ~y;
}

Answer 2

XNOR has the following truths:

0 XNOR 0 = 1 0 XNOR 1 = 0 1 XNOR 0 = 0 1 XNOR 1 = 1

equivalent to ~(x ^ y)

To do this using only ~ and |

Your logic is ~(~x | ~y) doesn't work logically for the case of 0 XNOR 0, as 1 | 1 is 1 and ~1 is 0. You've implemented the AND gate.

If I'm not mistaken, you can do XNOR using (x | ~y) & (~x | y)

but we need to add in your AND gate.

in one expression: ~(~(x | ~y)) | (~(~x | y))

EDIT: yes, this leaves us with 8 operators. I believe can fortunately be simplified to:

~(x | y) | ~(~x | ~y)

Answer 3

Now is a good time to learn De Morgan's laws, i.e.

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

An XNOR is

(~a & ~b) | (a & b)

rewrite by adding double inverts (aka double NOTs) to get

~~(~a & ~b) | ~~(a & b)

and then rewrite using De Morgan

~(~~a | ~~b) | ~(~a | ~b)

and reduce the first part (i.e. remove the double inverts)

~(a | b) | ~(~a | ~b)

That's an XNOR using 7 ~ and |

Source: https://en.wikipedia.org/wiki/De_Morgan%27s_laws

BTW:

Using the same principle De Morgans law can lead to

(~a & ~b) | (a & b)

to

~~((~a & ~b) | (a & b))

to

~(~(~a & ~b) & ~(a & b))

for an XNOR constructed using only ~ and &. In this case 8 operators is needed.

EDIT:

As pointed out by user "chux - Reinstate Monica" it is possible to do it with only ~ and & and 7 operators.

For instance by adding a few extra steps like:

(~a & ~b) | (a & b)

to

~~((~a & ~b) | (a & b))

to

~(~(~a & ~b) & ~(a & b))

to

~((a | b) & (~a | ~b))

to

~(((a & (~a | ~b)) | (b & (~a | ~b)))

to

~((a & ~a) | (a & ~b) | (b & ~a) | (b & ~b))

to

~((a & ~b) | (b & ~a))

to

~(a & ~b) & ~(b & ~a)

Now it's down to 7 operators.

Answer 4

A XNOR B is true if and only if A and B are both false or both true. Expressing this directly gives:

A XNOR B = ((not A) and (not B)) or (A and B)

In order to use only "not" and "or", we can use the logical identities (De Morgan's laws):

not (A or B) = (not A) and (not B)

not (A and B) = (not A) or (not B)

as well as

not (not A) = A

Thus,

A XNOR B = not (A or B) or not ((not A) or (not B))

Translating this into C, we get:

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

The OP code misses the first part of the expression.