Return Y integer with same bit sets as X & having | X - Y | minimum value 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 &lt;1001111000111111111&gt;

  
  Output:

324351 &lt;1001111001011111111&gt;

  
  Input:

x = 12 &lt;1100&gt;

  
  Output:

10 &lt;1010&gt;





private static int MinDiff(int x) 
{
    int y=0,a=0,b=0,countOne=0, countZero=0;
    if(x == 0)
        return -1;

    if( (x&amp;1)!=1)
    {
        y=x;
        while( (y &amp; 1) !=1  )
        {
            countOne++;
            y=y&gt;&gt;1;
        }
        y=x;
        while( (y&amp;3) != 2 )
        {
            countZero++;
            y=y&gt;&gt;1;
        }
        a=1;
        while(countZero != 0)
        {
            a = a&lt;&lt;1;
            countZero--;
        }
        b=1;
        while(countOne != 0)
        {
            b = b&lt;&lt;1;
            countOne--;
        }
    }
    else
    {
        y=x;
        while( (y&amp;1) != 0  )
        {
            countOne++;
            countZero++;
            y=y&gt;&gt;1;
        }
        countOne--;
        y=x;

        a=1;
        while(countZero != 0)
        {
            a = a&lt;&lt;1;
            countZero--;
        }
        b=1;
        while(countOne != 0)
        {
            b = b&lt;&lt;1;
            countOne--;
        }
    }

    b = ~b;
    y = (x | a) &amp; b;
    return y;
}
Your algorithm is logical, but a little trick can make it much simpler too. Because applying the trick makes the code so much shorter, it seems better to just point out some smaller issues in your code, and then show the improved algorithm later....

So, first up.... the method name: MinDiff .... really? Java convention is to have camelCase method names, not PascalCase. The first letter should be a lower-case.

Your variable names also are horrible.... y, x, a, and b. With x and y variables I am always looking for cartesian coordinates or something. Choose more meaningful names.

Your handling of 0 and -1 is also broken. Since there are no bits set in 0, and no unset bits in -1, they are impossible to provide a solution for, so the best thing would be to handle them as exceptions. Returning -1 for an input of 0 is broken, and overflowing on the input of -1 is inconsistent too.

So, having said that, the best algorithm to use is to identify the right-most change in bit values... where bitn and bitn-1 are different. Then, just swap them. A swap is easy to do with and XOR:

public static final int leastBitFlip(final int input) {
    if (input == 0 || input == -1) {
        throw new IllegalArgumentException("0 or -1 are not possible to compute as inputs");
    }
    int mask = 0b11;
    while (sameBits(input, mask)) {
        mask &lt;&lt;= 1;
    }
    // swap the bits.
    return input ^ mask;
}

private static boolean sameBits(final int input, final int mask) {
    final int bits = input &amp; mask;
    final int swap = mask &amp; ((bits &lt;&lt; 1) | (bits &gt;&gt; 1));
    return bits == swap;
}


Now, as for determining whether two bits are the same, or not, I think that sameBits() function can be improved, but I have not really run the truth table on it. The code is simple enough to understand though, and readability is important in these things.

Using the hint from ErikR - this algorithm would be faster though too:

public static final int leastBitFlip(int input) {
    if (input == 0 || input == -1) {
        throw new IllegalArgumentException("0 or -1 are not possible to compute as inputs");
    }
    // right-most one-bit.
    int onebit = ((input ^ (input - 1)) + 1) &gt;&gt; 1;
    // right most zero-bit.
    int zerobit = ((input ^ (input + 1)) + 1) &gt;&gt; 1;
    // where the change happens
    int change = onebit &gt; zerobit ? onebit : zerobit;
    // create a mask of the two bits either side of the change.
    int mask = change | (change &gt;&gt; 1);
    // swap them
    return input ^ mask;
}