### 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: xxxxx**0**11100 becomes xxxxx**1**11100. - Turn off the one that’s just to the right side of that. We’re now bigger by 2^i - 2^(i-1).

Example: xxxxx1**1**1100 becomes xxxxx1**0**1100 - Make the number as small as possible by rearranging all the 1s to be as far right as possible:

Example: xxxxx10**11**00 becomes xxxxx1000**11**

__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**

## 0 comments:

## Post a Comment