Clicky

Mustafa Veysi Soyvural: An Impressing Operator (Xor)

Tuesday, 11 December 2007

An Impressing Operator (Xor)

Now, lets talk about Xor operator. You can use this operator in many ways that you will see in some exercises here.

i ll give some remindful information about Xor gate:
- it yields 1 if there exists odd number of 1 value inputs
- x Xor 1 = not(x)
- x Xor 0 = x

Q.1.) Given two arrays A and B. Array 'A' contains all the elements of 'B' but
one more element extra.....

Find out the extra element......

Restrictions: Dont use any relational ops ( > or > or == etc....), array
elements are not in order ...,

int getDistinctElementFromTwoArrays( int arr1[ ], int len1, int arr2[ ], int len2 ) {
if ( len1 < 0 || len2 < 0 ) throw out_of_range( "Length of arrays must be bigger than 0." );

int result = arr1[ 0 ];
for ( int i = 1; i < len1; i++ ) {
result ^= arr1[ i ];
}

for ( int i = 0; i < len2; i++ ) {
result ^= arr2[ i ];
}

return result;
}

#include <iostream>
using namespace std;

int main ( int argc, char *argv[] ) {
try {
int arr1[ ] = { 1, 3, 5, 6, 7, -1, -3 };
int arr2[ ] = { 7, -3, 6, 1, -1, 5 };
int len1 = sizeof( arr1 ) / sizeof( arr1[ 0 ] )
int len2 = sizeof( arr2 ) / sizeof( arr2[ 0 ] );

cout << getDistinctElementFromTwoArrays( arr1, len1, arr2, len2 ) << endl;
}
catch ( out_of_range orex ) {
cout << orex.what( ) << endl;
}
return 0;
}






Q.2.)Given an array of numbers, except for one number all the others, occur
twice. Give an algorithm to find that number which occurs only once in the
array.

int getDistinctElement( int arr1[], int len1 ) {
if ( len1 < 0 ) throw out_of_range("Length must be bigger than 0");
int result = arr1[ 0 ];

for ( int i = 1; i < len1; i++ ) {
result ^= arr1[ i ];
}

return result;
}



#include <iostream>
#include <stdexcept>
using namespace std;

int main ( int argc, char *argv[] ) {
try {
int arr1[ ] = { -1, 1, 2, 3, 2, 1, -1 };
int len1 = sizeof( arr1 ) / sizeof( arr1[ 0 ] );

cout << getDistinctElement( arr1, len1 ) << endl;
}
catch ( out_of_range orex ) {
cout << orex.what( ) << endl;
}

return 0;
}

1 comment:

emreknlk said...

n) How to swap two variable using xor ?