CODEWITHSUNDEEP
javacalgorithm
Deepankar Singh
Deepankar Singh

Reputation: 674

Implementing bitwise XNOR

I saw a question for finding non repeatitive number from the set that contains only one distict number and rest numberes can be repeated any even number of times. A constraint was there that you need to find that number in a single pass using constant memory. {assume all are positive numbers}.
i acheived this easily by making this function 

  private static int nonRepeatingElement(int[] set) 
  {
        int element = 0;
        for (int i = 0; i < set.length; i++) 
        {
            element = (element ^ set[i]);
            System.out.println(element);
        }
    return element;
 }

and this is working fine.
Now just because of curiosity i thought to change the problem with similar constraints.
Problem1
I thought of a set that now contains elements which can occur any odd number of time except one element which occures even no of time. for example {2,5,7,5,7,1,2,7,1,5,2}
Now consereding the logic that XNOR gives 0 for every odd occurence of 1 i changed the code a little like

 for (int i = 0; i < set.length; i++) 
            {
                element = (element ^ set[i]);
                System.out.println(element);
            }
        return ~element;

but this didn't work.
Problem2
if i take elements in the set like {2,5,7,5,7,1,2,7,5,2} thinking XNORing will make every thrice occurence of number to 0 and XNORing with 1(single occurrence) to 0 will flip the bits of 1.So final result can be acheived if i flip(~) the bits of what I'm gettting from XNOR operation.But this also doesnt work.

I know why this semantics is going wrong as it is bitwise operation not logical.But if xoring can be used for finding odd occurance of a number Isn't there any way with XNOR for finding even occurrent of a number?

I'm not sure about the feasibility of this problem I'm asking just out of curiosity so forgive my ignorance if it's irrelevent in any context.

Upvotes: 1

Views: 2069

Answers (1)

Bathsheba
Bathsheba

Reputation: 234665

XOR and XNOR are commutative. This means that any re-ordering of the sequence will always yield the same result.

You already know that a ^ a is zero. That's how the single number abstraction works: a ^ b ^ a equals a ^ a ^ b which equals 0 ^ b which is b.

But a XNOR a is also not a function of a. It's simply a whole load of 1 bits. Therefore you can't recover the value of a using a XNOR a and so your approach will not work.

Upvotes: 3

Related Questions