I happened to come across one question:
Given an integer 'x' (Only positive), write an algorithm that returns integer 'y' such that it has the same number of bits set as 'x' and is not equal to 'x' and the distance |x-y| is minimized.
Example:
x: 01 y: 10
Now I wrote some bit manipulation as follows and it's working correctly. But I wanted to know if there is a more compact algorithm (we are not allowed to use any built-in functions).
Algorithm
If the Zeroth bit '0':
- find first occurrence of '1'
- find last occurrence of '0' before first '1'
- reverse them (I used OR and AND function to do that)
If the Zeroth bit '1':
- find first occurrence of '0'
- find last occurrence of '1' before first '0'
- reverse them (I used OR and AND function to do that)
Input:
x = 324095 <1001111000111111111>
Output:
324351 <1001111001011111111>
Input:
x = 12 <1100>
Output:
10 <1010>
private static int MinDiff(int x)
{
int y=0,a=0,b=0,countOne=0, countZero=0;
if(x == 0)
return -1;
if( (x&1)!=1)
{
y=x;
while( (y & 1) !=1 )
{
countOne++;
y=y>>1;
}
y=x;
while( (y&3) != 2 )
{
countZero++;
y=y>>1;
}
a=1;
while(countZero != 0)
{
a = a<<1;
countZero--;
}
b=1;
while(countOne != 0)
{
b = b<<1;
countOne--;
}
}
else
{
y=x;
while( (y&1) != 0 )
{
countOne++;
countZero++;
y=y>>1;
}
countOne--;
y=x;
a=1;
while(countZero != 0)
{
a = a<<1;
countZero--;
}
b=1;
while(countOne != 0)
{
b = b<<1;
countOne--;
}
}
b = ~b;
y = (x | a) & b;
return y;
}
x
by comparingx
andx-1
. Likewise, you can find the first 0 inx
by comparingx
andx+1
. – ErikR Sep 4 '15 at 2:15