Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

  1. If the Zeroth bit '0':

    1. find first occurrence of '1'
    2. find last occurrence of '0' before first '1'
    3. reverse them (I used OR and AND function to do that)
  2. If the Zeroth bit '1':

    1. find first occurrence of '0'
    2. find last occurrence of '1' before first '0'
    3. 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;
}
share|improve this question
    
Hint: You can find the least significant bit set in x by comparing x and x-1. Likewise, you can find the first 0 in x by comparing x and x+1. – ErikR Sep 4 '15 at 2:15
    
I guess that will increase the comparisons (Number++/-- and check LSBs for 0 and 1). Where-as in my method checking the bits and doing the bit manipulation would be fast enough to return the required number, what do you say? – JustVirtually Sep 4 '15 at 2:18

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 <<= 1;
    }
    // swap the bits.
    return input ^ mask;
}

private static boolean sameBits(final int input, final int mask) {
    final int bits = input & mask;
    final int swap = mask & ((bits << 1) | (bits >> 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) >> 1;
    // right most zero-bit.
    int zerobit = ((input ^ (input + 1)) + 1) >> 1;
    // where the change happens
    int change = onebit > zerobit ? onebit : zerobit;
    // create a mask of the two bits either side of the change.
    int mask = change | (change >> 1);
    // swap them
    return input ^ mask;
}
share|improve this answer
    
Yes, extremely sorry for unprofessional style of code. Except that code looks efficient right? was worried about more efficient algorithm. Next was considering defining it with "unsigned integers" with Java 8 – JustVirtually Sep 4 '15 at 3:23
    
Your algorithm is relatively efficient, ErikR's suggestion would be the most efficient. The least efficient would be testing each number larger/smaller until you get one with the same number of bits. – rolfl Sep 4 '15 at 3:27
    
onebit = input & -input and zerobit = ~input & (input+1) are simpler bit hacks. Source: this website. – JS1 Sep 4 '15 at 6:18
    
Also, I believe 0x7fffffff and 0x80000000 are special cases that require a different answer than what the normal algorithm would output. – JS1 Sep 4 '15 at 6:39
    
+1. Changing only changing int to long works for 0x7FFFFFFF. As Java Int and long are signed, will have to use Java 8 or Guava to work for 0x80000000 – JustVirtually Sep 4 '15 at 21:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.