Thread: XOR vs ^

  1. #1
    Registered User
    Join Date
    Feb 2019
    Posts
    67

    XOR vs ^

    Hey,

    this XOR Calculator Online calculates:

    1 XOR 4 = 5

    However:

    Code:
    1^4
    in C turns out to be 7.

    Why?

  2. #2
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,728
    Quote Originally Posted by SuchtyTV View Post
    in C turns out to be 7.
    It shouldn't. The correct answer is 5. Are you sure you didn't do something wrong?
    Devoted my life to programming...

  3. #3
    Informer -Adrian's Avatar
    Join Date
    Jan 2013
    Posts
    816
    Post your code, I get 5 in C as well.

  4. #4
    Registered User
    Join Date
    Feb 2019
    Posts
    67
    Quote Originally Posted by GReaper View Post
    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...

  5. #5
    Registered User
    Join Date
    Feb 2019
    Posts
    550
    5 as well...

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

  6. #6
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,728
    Quote Originally Posted by SuchtyTV View Post
    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...
    Devoted my life to programming...

  7. #7
    Registered User
    Join Date
    Feb 2019
    Posts
    67
    Sorry. I did something wrong.

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

  8. #8
    Registered User
    Join Date
    Feb 2019
    Posts
    550
    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?

  9. #9
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,859
    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

  10. #10
    Registered User
    Join Date
    Feb 2019
    Posts
    550
    Quote Originally Posted by Click_here View Post
    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)
    Last edited by flp1969; 05-15-2019 at 05:45 PM.

  11. #11
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,859
    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...

    Code:
    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.
    Fact - Beethoven wrote his first symphony in C

  12. #12
    Registered User
    Join Date
    Feb 2019
    Posts
    550
    Quote Originally Posted by Click_here View Post
    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:

    Code:
    // 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.
    Last edited by flp1969; 05-16-2019 at 04:45 PM.

  13. #13
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,859
    Code:
    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...
    Fact - Beethoven wrote his first symphony in C

Popular pages Recent additions subscribe to a feed

Tags for this Thread