## Find the nearest numbers that have same number of 1s for an integer

Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation.

My initial thoughts:
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.

My initial codes:

```	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.
Solutions:
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);
}
}

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;
}

Solution’s idea

Traverse from right to left. 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

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5b27ff12999df', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5b27ff1299a0d',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5b27ff1299a0f',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});