Google Interview Question
Software Engineer / Developers#include<stdio.h>
main()
{
int n, i, j, s;
printf("enter values of n, i and j");
scanf("%d%d%d",&n,&i,&j);
s = swap(n,i,j);
printf("%d",s);
}
swap(int n,int i,int j)
{
if(i!=j)
{
n^= 1<<i;
n^= 1<<j;
}
return n;
}
I'm not sure it's necessary to check for i != j. It would still be correct if i == j; you don't need to incur the cost of a branch.
{
void swap(int&n, int i, int j) {
int xori = (((1 << i) & n ) >> i ) ^ (((1 << j) & n ) >> j );
n ^= xori << i;
n ^= xori << j;
}
}
I do not understand how this solution works out.
let n = 01'1'1 01'1'0
i = 6,j=2 ( quoted those two bit positions - bit position starting from 1 from left end).
n^=(1<<i)
1<<6 => 0100 0000
n = n^(1<<6) = 0011 0110
n=n^(1<<j) = n^(1<<2)
1<<2 => 0000 0100
n = n^(1<<2) = 0011 0010
Swapping individual bits with XOR
unsigned int i, j; // positions of bit sequences to swap
unsigned int n; // number of consecutive bits in each sequence
unsigned int b; // bits to swap reside in b
unsigned int r; // bit-swapped result goes here
unsigned int x = ((b >> i) ^ (b >> j)) & ((1U << n) - 1); // XOR temporary
r = b ^ ((x << i) | (x << j));
int d=5,i=2,j=1;
int tmp1=d;
d=d&(0xFFFFFF^1<<i);
d=d&(0xFFFFFF^1<<j);
d=d+(pow(2,i)*((tmp1>>j)&1))+(pow(2,j)*((tmp1>>i)&1));
cout<<d;
/* Swap bits "i" and "j" inside "num" and return the result.
* The idea used here is from how to swap two integers using exclusive-ORs. */
int swapBits(int num, int i, int j)
{
int temp ;
if ((i >= 0) && (i < 8*sizeof(int)) && (j >= 0) && (j < 8*sizeof(int)) && (i^j))
{
temp = (num >> i) ^ (num >> j) & 0x01 ;
num ^= temp << j ;
num ^= temp << i ;
}
return (num) ;
}
int Swapbits(int num, int pos1, int pos2)
{
int temp1 = num>>(pos1-1) & 1;
int temp2 = num>>(pos2-1) &1;
int swapnum = num;
//int temp3 = 0;
if(temp1 ^ temp2)
{
//bits are different
int temp3 = 1<<(pos1-1);
int temp4 = 1<<(pos2-1);
swapnum = num ^(temp3 | temp4);
}
return swapnum;
}
int _tmain(int argc, _TCHAR* argv[])
{
int num = 102;
int newnum = Swapbits(num, 3,6);
return 0;
}
void swap(int *a,int i,int j)
{
int p = *a;
unsigned int k = 1;
#if 0
*a = ((p&(~(k<<(i-1))))& (p&(~(k<<(j-1)))) )| (k<<(j-1) & (p <<(j -1))) | (k<< (i - 1) & p>>(j - i));
#endif
if((p>>(j - 1) & 1) == 0x01)
{
p = p&(~(k<<(j-1)));
}
else
{
p = p | (1<<j-1);
}
if((p>>(i-1) & 1) == 0x01)
{
p = p&(~(k<<(i-1)));
}
else
{
p = p | (1<<i-1);
}
*a = p;
}
main()
{
int a,i,j;
printf("enter a,i,j\n");
scanf("%d%d%d",&a,&i,&j);
swap(&a,i,j);
printf("%d\n",a);
swap(&a,i,j);
printf("%d\n",a);
}
This assumes j > i; printfs for clarity.
bitswap( unsigned char i, unsigned char j, unsigned int& num )
{
unsigned int mask = 0x00000001;
// Mask to turn off ith and jth position
unsigned int m1 = mask << (i-1); printf( "m1: %x\n", m1 );
unsigned int m2 = mask << (j-1); printf( "m2: %x\n", m2 );
unsigned int sw1 = (m1 & num) << (j-i);
unsigned int sw2 = (m2 & num) >> (j-i);
// Turn OFF ith and jth position in the original num, and OR with swapped bits.
unsigned int val = ( ~(m1 | m2) & num ) | sw1 | sw2;
printf( "num: %X\n", num );
printf( "val: %X\n", val );
num = val;
}
public static int setBit(int num, int i, boolean value){
if (value == true){
return (1 << i) | num;
}else{
return (~(1 << i)) & num;
}
}
public static boolean getBit(int num, int i){
return (((1 << i) & num) != 0);
}
public static int swapBits(int num, int i, int j){
boolean bitI = getBit(num, i);
boolean bitJ = getBit(num, j);
boolean temp = bitI;
num = setBit(num, i, bitJ);
num = setBit(num, j, temp);
return num;
}
public class HelloWorld{
public int swap(int num,int i,int j)
{
int lowcheck,highcheck,hcheck,lcheck,partial,mask,intermediate;
lowcheck=1;
highcheck=1;
lowcheck<<=j;
lcheck=lowcheck;
highcheck<<=i;
hcheck=highcheck;
lowcheck=num&lowcheck;
highcheck=num&highcheck;
highcheck>>>=(i-j);
if (lowcheck==highcheck)
System.out.println ("The bits are same");
else
{
lowcheck<<=(i-j);
partial=lowcheck|highcheck;
mask=~lcheck&~hcheck;
intermediate=mask#
num=intermediate|partial;
}
return num;
}
public void start()
{
int num,i,j,s;
num=10;
i=3;
j=0;
s=swap(num,i,j);
System.out.println(s);
}
public static void main(String []args){
HelloWorld hw=new HelloWorld();
hw.start();
}
}
public class HelloWorld{
public int swap(int num,int i,int j)
{
int lowcheck,highcheck,hcheck,lcheck,partial,mask,intermediate;
lowcheck=1;
highcheck=1;
lowcheck<<=j;
lcheck=lowcheck;
highcheck<<=i;
hcheck=highcheck;
lowcheck=num&lowcheck;
highcheck=num&highcheck;
highcheck>>>=(i-j);
if (lowcheck==highcheck)
System.out.println ("The bits are same");
else
{
lowcheck<<=(i-j);
partial=lowcheck|highcheck;
mask=~lcheck&~hcheck;
intermediate=mask#
num=intermediate|partial;
}
return num;
}
public void start()
{
int num,i,j,s;
num=10;
i=3;
j=0;
s=swap(num,i,j);
System.out.println(s);
}
public static void main(String []args){
HelloWorld hW=new HelloWorld();
hW.start();
}
}
public class HelloWorld{
public int swap(int num,int i,int j)
{
int lowcheck,highcheck,hcheck,lcheck,partial,mask,intermediate;
lowcheck=1;
highcheck=1;
lowcheck<<=j;
lcheck=lowcheck;
highcheck<<=i;
hcheck=highcheck;
lowcheck=num&lowcheck;
highcheck=num&highcheck;
highcheck>>>=(i-j);
if (lowcheck==highcheck)
System.out.println ("The bits are same");
else
{
lowcheck<<=(i-j);
partial=lowcheck|highcheck;
mask=~lcheck&~hcheck;
intermediate=mask#
num=intermediate|partial;
}
return num;
}
public void start()
{
int num,i,j,s;
num=10;
i=3;
j=0;
s=swap(num,i,j);
System.out.println(s);
}
public static void main(String []args){
HelloWorld hW=new HelloWorld();
hW.start();
}
}
public class HelloWorld{
public int swap(int num,int i,int j)
{
int lowcheck,highcheck,hcheck,lcheck,partial,mask,intermediate;
lowcheck=1;
highcheck=1;
lowcheck<<=j;
lcheck=lowcheck;
highcheck<<=i;
hcheck=highcheck;
lowcheck=num&lowcheck;
highcheck=num&highcheck;
highcheck>>>=(i-j);
if (lowcheck==highcheck)
System.out.println ("The bits are same");
else
{
lowcheck<<=(i-j);
partial=lowcheck|highcheck;
mask=~lcheck&~hcheck;
intermediate=mask#
num=intermediate|partial;
}
return num;
}
public void start()
{
int num,i,j,s;
num=10;
i=3;
j=0;
s=swap(num,i,j);
System.out.println(s);
}
public static void main(String []args){
HelloWorld hW=new HelloWorld();
hW.start();
}
}
The simple code for swapping the two bits of a given integer will be to iterate to the given two bits and store them in a variable as (x>>i) & 1 and the other as (x>>j) & 1 now, we will xor the two bits and store in a variable as x = (b1 ^ b2) and the, we will put back the bits in their place as x = (x<<i) | (x<<j) and at the end return the xor of the number and x to swap the two bits finally
Implementation:
int swapp(unsgned int n, unsigned i, unsigned int j){
unsigned int p1 = (n<<i) & 1;
unsigned int p2 = (n<<j) & 1;
unsigned int x = (p1^p2);
x = (n<<p1) | (n<<p2);
return n^x;
}
swap(int n,int i,int j)
- Anonymous April 24, 2010{
if( (n & 1<<i)>>i ^ (n & (i<<j))>>j) ) // if bits i and j are different
{
n^= 1<<i;
n^= 1<<j;
}
return n;
}