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
- Flip rightmost non-trailing zero
- Clear bits to the right of p
- add in c1 - 1 ones
Get Previous
- trailing ones, and trailing zeros to the left of trailing ones
- Flip the right most one-trailing one to a zero.
- clear all bits to the right of bit p
- Insert c1 + 1 ones immediately to the right of position p
Complexity
时间复杂度 O(n),空间复杂度 O(1)
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;
}