Latest Updates ☛
- Graphs: Introduction of graphs and types of graphs
- SPOJ : Geeky solves geeky solution
- Solution Code : Pass the time problem on SPOJ.
- Find the minimum shortest path solution in c language ! !
- Code
Author
Welcome !
Heya ! Firstly thanks for giving look to this website .Here you can find all the stuff related to programming plus its solutions means a pack for learners and coders.
So keep visiting and enjoy learning and browsing this Code Author ! !
About Me
- Java Programs
- C++
C++ Programs List
- Books
- C & Data Structures
Data Structures
Reference Book
This is a basic book for a starter to learn data structures in c programming language.Filled with total explanation of all programs working and many more.Read more...
- Privacy Policy
- Others
Saturday, September 7, 2013
Solution to a differnent XORing Problem
Question :
Let us suppose we have a “N” bit integer X. We call an integer X’ as neighbor-X, if X’ can be obtained by shuffling the bits of integer X.
For ex. If X = 6 and N = 5, then X will be represented as X = (00110)2, So all the 5 bit integers that have exactly two 1s in their binary representation are called neighbor-X. For ex. (00011)2, (01001)2, (10100)2, … all of these are neighbor-X.
Now you are given two N bit integers “X” and “Y”, then you have to find the maximum possible value of (X’ xor Y’) where X’ is neighbor-X.
xor operator takes two bit strings and performs XOR operation between them. For ex:(10010)2 xor (01011)2 =(11001)2
Let us suppose we have a “N” bit integer X. We call an integer X’ as neighbor-X, if X’ can be obtained by shuffling the bits of integer X.
For ex. If X = 6 and N = 5, then X will be represented as X = (00110)2, So all the 5 bit integers that have exactly two 1s in their binary representation are called neighbor-X. For ex. (00011)2, (01001)2, (10100)2, … all of these are neighbor-X.
Now you are given two N bit integers “X” and “Y”, then you have to find the maximum possible value of (X’ xor Y’) where X’ is neighbor-X.
xor operator takes two bit strings and performs XOR operation between them. For ex:(10010)2 xor (01011)2 =(11001)2
Inputs :
The first line of the input will contain an integer “T”, the no. of test cases. Each of the next “T” lines will contain three integers “N”, “X” and “Y”, N is the no. of bits in integers X and Y.
The first line of the input will contain an integer “T”, the no. of test cases. Each of the next “T” lines will contain three integers “N”, “X” and “Y”, N is the no. of bits in integers X and Y.
Outputs :
For each test case you have to print the maximum possible value of (X’ xor Y’) in a separate line.
For each test case you have to print the maximum possible value of (X’ xor Y’) in a separate line.
Constraints :
1 <= T <= 100, 1 <= N <= 10^5
1 <= T <= 100, 1 <= N <= 10^5
Level : Medium
Solution to the Problem :
#include<stdio.h>
int pow(int x,int k)
{
if(k==0)
return 1;
return x*pow(x,k-1);
}
int min(int i,int j)
{
return i<j?i:j;
}
int find(int n)
{
int c=0;
while(n>0)
{
if(n&1)
c++;
n=n>>1;
}
return c;
}
main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,a,b;
scanf("%d%d%d",&n,&a,&b);
int k=find(a);
int l=find(b);
int res=min(k,n-l)+min(n-k,l);
int kk=n-res;
printf("%d\n",(pow(2,res)-1)<<kk);
}
}
