XOR operator and its use

Question

0.00/5 (No votes)

See more:

USAGE OF XOR OPERATOR IN THIS PROBLEM:

You are given an array A of n - 2 integers which are in the range between 1 and n. All numbers appear exactly once, except two numbers, which are missing. Find these two missing numbers.

have to find the solution by using XOR operator
METHOD OF FINDING USING XOR :

LET the two elements be u and v
THE ALGORITHM:

1 ^ 2 ^ ... ^ n ^ A[0] ^ A[1] ^ ... ^ A[n - 3]

We will denote these elements by u and v, mostly because we have not used those letters before. BY applying the above algorithm, we are thus left with u ^ v. What can we do with that? We somehow need to extract u and v from this value, but it is not immediately clear to do that.

We can do this by

Partitioning based on inspecting u ^ v

If we analyze the individual bits in u ^ v, then every 0 means that the bit had the same value in both u and v. Every 1 means that the bits differed.

Using this, we find the first 1 in u ^ v, i.e. the first position i where u and v have to differ. Then we partition A as well as the numbers from 1 to n according to that bit. We end up with two partitions, each of which contains two sets:

 1. Partition 0
The set of all values from 1 to n where the i-th bit is 0
The set of all values from A where the i-th bit is 0

 2.Partition 1
The set of all values from 1 to n where the i-th bit is 1
The set of all values from A where the i-th bit is 1
Since u and v differ in position i, we know that they have to be in different parttions.

Next, we can use another insight, 

While we worked on integers from 1 to n so far, this is not required. In fact, the previous algorithm works in any situation where there is (1) some set of potential elements and (2) a set of elements actually appearing. The sets may only differ in the one missing (or duplicated) element.

These two sets correspond exactly to the sets we have in each partition. We can thus search for u by applying this idea to one of the partitions and finding the missing element, and then find v by applying it to the other partition.

This is actually a pretty nice way of solving it: We effectively reduce this new problem to the more general version of the problem we solved earlier.

Could you please explain
partition 0:

The set of all values from 1 to n where the i-th bit is 0 and

partition 1:
The set of all values from 1 to n where the i-th bit is 1
that were discussed in this!

What I have tried:

Did not understand that part......

Posted 26-Jun-21 3:13am

_-_-_-me

Updated 26-Jun-21 18:24pm

Add a Solution

2 solutions

Solution 2

C++

#include<stdio.h>
void findthemissingelements(int nums[],int n)
{
    int i=0;
    int XOR1=0,XOR2=0;
    for(i=1;i<=n;i++)
    {
        XOR1=XOR1^i;
    }
    for(i=0;i<n-2;i++)
    {
        XOR2=XOR2^nums[i];
    }
    int XOR=XOR1^XOR2;
    int x=0, y=0;
    int set_bit=XOR & ~(XOR-1);
    for(i=0;i<n-2;i++)
    {
        if(nums[i] & set_bit)
        {
            x=x^nums[i];
        }
        else
        {
            y=y^nums[i];
        }
    }
    
     for(i=1;i<=n;i++)
    {
        if(i & set_bit)
        {
            x=x^i;
        }
        else
        {
            y=y^i;
        }
    }
    printf("%d    %d",x,y);
}
int main()
{
    int nums[]={1,3,5,6,7};
    findthemissingelements(nums,7);
    return 0;
}

Posted 26-Jun-21 18:24pm

_-_-_-me

Updated 26-Jun-21 18:26pm

v2

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

OriginalGriff · Accepted Answer · 2021-06-26T04:15:00

XOR is a simple bitwise binary operator, su=imilar to AND and OR.
AND returns 1 if both inputs are one, and 0 in all other cases:

a  b  a & b
0  0    0
0  1    0
1  0    0
1  1    1

Similarly, OR returns 1 if any input is one, and 0 only when both are zero:

a  b  a | b
0  0    0
0  1    1
1  0    1
1  1    1

XOR is very similar: it returns 1 if both the inputs are different: one zero and one one. If they are the same, it returns 0:

a  b  a ^ b
0  0    0
0  1    1
1  0    1
1  1    0

Because these are bitwise operators, the return value is the "collection" of output bits: one for each pair of bits in the input.
So if your input is 52 XOR 31, you first think ot it as binary:

C#

56 = 111000b
31 = 011111b

XOR them together and you get:

C#

56 = 111000
31 = 011111
XOR  ------
     100111

Which doesn't look too useful at first glance.
But ... What if you XOR that result with either of the two inputs?

C#

56 = 111000
?? = 100111
XOR  ------
     011111

C#

31 = 011111
?? = 100111
XOR  ------
     111000

Which is the "other value" from the original operation!

So if a ^ b = x then a ^ x = band b ^ x = a
This is really useful, and it's basically what makes a RAID 5 drive work: you write a on one drive, b on the second, and a ^ b on the third. When any disk fails, the "missing information" can be rebuilt perfectly from the information on the remaining two!

So ... now think about your task, and try it manually with - say - five numbers: 1, 2, 3, 4, and 5. Remove two numbers at random, and see if you can make the algorithm work out what they were!
When you have that working, it should be pretty simple for you to code it.