## Thursday, April 17, 2014

### Problem

Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation.
Example
Next higher number for 3 is 5. i.e. (00000011 => 00000101)
Likewise next lower number of 5 is 3.

### Solution

Method 1 - Adding or subtracting 1 until we have same number of 1s
For the next largest, keep adding 1 to the number until find the number that has same number of 1 bits. For the next smallest, keep decreasing 1.
```public static int findNextSmallest(int number) {
int result = number - 1;
while (Integer.bitCount(result) != Integer.bitCount(number))
result--;
return result;
}

public static int findNextLargest(int number) {
int result = number + 1;
while (Integer.bitCount(result) != Integer.bitCount(number))
result++;
return result;
}
```

Definitely gonna work but terribly boring. We know this is not what the interviewer expects, he wants some bit manipulation.

Method 2- Change the bits

For getting the next higher number
• Traverse from right to left i.e. LSB to MSB. Once we’ve passed a 1, turn on the next 0. We’ve now increased the number by 2^i. Yikes!
Example: xxxxx011100 becomes xxxxx111100.
• Turn off the one that’s just to the right side of that. We’re now bigger by 2^i - 2^(i-1).
Example: xxxxx111100 becomes xxxxx101100
• Make the number as small as possible by rearranging all the 1s to be as far right as possible:
Example: xxxxx101100 becomes xxxxx100011
For the next smaller number
We can do something like this.
```int getNextSmaller(int num) {
return ~getNextLarger(~num);
}
```
i.e. follow the above algorithm for number's complement.

Java code
```public static boolean GetBit(int n, int index) {
return ((n & (1 << index)) > 0);
}

public static int SetBit(int n, int index, boolean b) {
if (b) {
return n | (1 << index);
} else {
int mask = ~(1 << index);
return n & mask;
}
}

public static int GetNext_NP(int n) {
if (n <= 0)
return -1;
int index = 0;
int countOnes = 0;

// Find first one.
while (!GetBit(n, index))
index++;

// Turn on next zero.
while (GetBit(n, index)) {
index++;
countOnes++;
}
n = SetBit(n, index, true);

// Turn off previous one
index--;
n = SetBit(n, index, false);
countOnes--;

// Set zeros
for (int i = index - 1; i >= countOnes; i--) {
n = SetBit(n, i, false);
}

// Set ones
for (int i = countOnes - 1; i >= 0; i--) {
n = SetBit(n, i, true);
}

return n;
}

public static int GetPrevious_NP(int n) {
if (n <= 0)
return -1; // Error

int index = 0;
int countZeros = 0;

// Find first zero.
while (GetBit(n, index))
index++;

// Turn off next 1.
while (!GetBit(n, index)) {
index++;
countZeros++;
}
n = SetBit(n, index, false);

// Turn on previous zero
index--;
n = SetBit(n, index, true);
countZeros--;

// Set ones
for (int i = index - 1; i >= countZeros; i--) {
n = SetBit(n, i, true);
}

// Set zeros
for (int i = countZeros - 1; i >= 0; i--) {
n = SetBit(n, i, false);
}

return n;
}
```

References