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.

Naive Solution:
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.

Advanced Solution:

1. 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.
2. 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
3. Make the number as small as possible by rearranging all the 1s to be as far right as possible: Example: xxxxx101100 becomes xxxxx100011

Code:

boolean GetBit(int n, int index) {
    return ((n & (1 << index)) > 0);
}

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

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

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