XOR vs ^

[SuchtyTV]

Hey,

this XOR Calculator Online calculates:

1 XOR 4 = 5

However:

1^4

in C turns out to be 7.

Why?

[GReaper]

in C turns out to be 7.

It shouldn't. The correct answer is 5. Are you sure you didn't do something wrong?

[Guest]

Post your code, I get 5 in C as well.

[SuchtyTV]

It shouldn't. The correct answer is 5. Are you sure you didn't do something wrong?

Yet Another Minimax Problem | HackerRank

I do not get challenges point afer all. The calculator is on challenges site...

[flp1969]

5 as well...

$ gcc -xc -include stdio.h - <<EOF
int main(void){printf("%d\n",1^4);}
EOF
$ ./a.out
5

[GReaper]

I do not get challenges point afer all.

It's a bit complicated, but nothing difficult. The problem definition had me confused for a minute, but the following explanation made the task much clearer.

A permutation is a specific arrangement of the members of a set, integers in this case. Brute-forcing it, you'll have to shift through (n!) possible orderings. There must be some trick to lower the complexity, but I'm too lazy to think about it...

[SuchtyTV]

Sorry. I did something wrong.

int anotherMinimaxProblem(int a_count, int* a) {    int max = INT_MIN;
    for(int i = 0; i < a_count-1; i++){
        int k = a[i]^a[i+1];
        printf("%d \n", k);
        if(k > max){
            max = k;
        }
    }
    return max;

}

However this code should work for the challenge.
Given this input the answer shall be 5, but I do not see why...:

4
1 2 3 4

1^2 --> 3
2^3 --> 1
3^4 --> 7

Oh, gosh, I got my mistake:












does not mean that the one and the following. (Wrongly suggested in the examples...)

[flp1969]

Are you sure you need to deal with signed integers?
let's say a[0] = -1 and a[1] = -2. XORing this two values will result in +1.
Is that what you want?

[Click_here]

You do understand why the answer should be 5, right?

1 xor 4

001 xor
100
=
101

When the numbers are viewed as there binary number, xor compares both of the first bits - if they are different, the result for that bit is 1, otherwise it is 0. It then goes through the rest and compares bit by bit...

i.e.
1010010
1100101
=
0110111

[flp1969]

When the numbers are viewed as there binary number, xor compares both of the first bits - if they are different, the result for that bit is 1, otherwise it is 0. It then goes through the rest and compares bit by bit...

There are other useful interpretations as well.

1- XOR is eXclusive OR, i.e, an OR that excludes the possibility of equal 1's;
2- XOR is a binary caryless sum;
3- XOR is also a binary borrowless subtraction;

OR:
0 or 0 = 0
0 or 1 = 1
1 or 0 = 1
1 or 1 = 1 <-- exclude this and you get XOR.

Just ignore the Carry (C):
0+0=0 (C=0)
0+1=1 (C=0)
1+0=1 (C=0)
1+1=0 (C=1)

Obs: Notice C = A and B.

Just ignore the Borrow (B):
0-0 = 0 (B=0)
0-1 = 1 (B=1)
1-0 = 1 (B=0)
1-1 = 0 (B=0)

[Click_here]

Your first interpritation is how I learnt - The reason is that my background is in electronics and when it comes to logic gates, XOR is considered a more advanced one. It's because it's a little more involved when implemented with NAND gates.


Breaking out the old boolean algebra...

using (.=AND | /=NOT | +=OR) 

A XOR B = A./B + /A.B

becomes..
A./(B.B) + /(A.A).B

//(A./(B.B)) + //(/(A.A).B)

/(/(A./(B.B)) .(/(/(A.A).B))

or rather...
((A NAND (B NAND B)) NAND ((A NAND A) NAND B) )


Or alternatively...
By using
A./B = 
A./A + A./B = 
A.(/A + /B) =
A./(A.B)

We can say that an XOR gate can also be
/( /(A. /(A.B)) . /(B . /(B.A)))
( (A NAND (A NAND B)) NAND (B NAND (B NAND A)))

Which is nice, because you can use the same gate result for (A NAND B) on both sides and only use 4 gates instead of 5.  This meant that you only needed one 74LS00 chip!

On a side note: I tried to track down a 74LS07 chip (TTL hex inverter) earlier this year and places that use to have buckets of logic gates, but they are now are a thing of the past: I had to order them online.

[flp1969]

Your first interpritation is how I learnt - The reason is that my background is in electronics...

My background as well, a long time ago...

But the interpretations as caryless sums and borrowless differences are particularly interesting to understand why instructions as ADD or SUB are so fast. If a processor don't have an ALU, but is capable of simple logical operations, including shifts, ADD and SUB can be implemented easily:

// sum: x = a + b; (all ints)
x = ( a ^ b ) ^ ( ( a & b ) << 1 );

// sub: x = a - b; (all ints)
x = ( a ^ b ) ^ ( ( ~a & b ) << 1 );

Indeed, routines as crc32 uses this tactics to implement polynomial binary sums.

It is no coincidence that, in certain literature, ⊕ is the symbol for XOR.

[Click_here]

My background as well, a long time ago...

I guessed that, because I remember that you said something about the XC8 compliler the other week - Most people who programme 8bit PICs have an electronics background.

... And the k-maps were the other clue...