# Next Number

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

## Solution

Get Next

1. Flip rightmost non-trailing zero
2. Clear bits to the right of p
3. add in c1 - 1 ones

Get Previous

1. trailing ones, and trailing zeros to the left of trailing ones
2. Flip the right most one-trailing one to a zero.
3. clear all bits to the right of bit p
4. Insert c1 + 1 ones immediately to the right of position p

## Code

``````/**
* @param n
* @return
*/
int getNext(int n){
int temp = n;
int zeros = 0;
int ones = 0;

while(((temp & 1) == 0) && (temp != 0)){
zeros++;
temp = temp >> 1;
}

while((temp & 1) == 1){
ones++;
temp = temp >> 1;
}

if (zeros + ones == 31 || zeros + ones == 0){
return -1;
}

int rightmost = zeros + ones;

n = n | (1 << rightmost);
n = n & ~((1 << rightmost) - 1);
n = n | (1 << (ones - 1)) - 1;

return n;
}

/**
* @param n
* @return
*/
int getPrev(int n){
int temp = n;
int zeros = 0;
int ones = 0;

while((temp & 1) == 1){
ones++;
temp = temp >> 1;
}

while(((temp & 1) == 0) && (temp != 0)){
zeros++;
temp = temp >> 1;
}

if (zeros + ones == 31 || zeros + ones == 0){
return -1;
}

int rightmost = zeros + ones;

n = n & ~(1 << (rightmost + 1) - 1);
int mask = ((1 << (ones + 1)) - 1) << (zeros - 1);
n = n | mask;
return n;
}
``````