Problem
Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation.
Solution
#include <iostream>
#include <bitset>
using namespace std;
// assume num != 08000000 or 0
int leftest_1_pos(int num){
int pos = -1;
unsigned int n = num & 0x7FFFFFFF;
while(n > 0){
n >>= 1;
pos ++;
}
return pos;
}
int rightest_1_pos(int num){
int pos = -1;
unsigned int n = num & 0x7FFFFFFF;
while(pos < 31){
pos ++;
if(n & 1){
break;
}
n >>= 1;
}
return pos;
}
// not include sign bit
int bits_count(int num)
{
int bits = 0;
int one = 1;
int pos = 0;
unsigned int n = 0x7FFFFFFF;
num &= n;
while(num > 0){
if(one & num){
bits ++;
}
num >>= 1;
}
return bits;
}
int bits_set(int num, int v, int pos)
{
unsigned int mask = 1 << pos;
mask = ~mask;
num &= mask;
if(v){
num |= (1 << pos);
}
return num;
}
bool right_0_pos_in_range(int &pos, int num)
{
int most_left = leftest_1_pos(num);
int most_right = rightest_1_pos(num);
int bits = bits_count(num);
int one = 1;
if(bits == 0 || bits == 1){
return false;
}
if(most_left - most_right + 1 == bits){
return false;
}
pos = most_right;
while(pos < most_left){
if(((unsigned int)num & (one << pos)) == 0){
break;
}
pos ++;
}
return true;
}
bool next_smaller(int &smaller, int num)
{
int found = false;
int most_left = leftest_1_pos(num);
int most_right = rightest_1_pos(num);
int bits = bits_count(num);
int gap = most_left - most_right + 1;
if(bits == 0){
cout << "there is no bit ones in " << num << " except the sign bit." << endl;
cout << "so there is no nearest larger or smaller " << endl;
return false;
}
if(bits == 31){
cout << "there are all bit ones in " << num << " except the sign bit." << endl;
cout << "so there is no nearest larger or smaller " << endl;
return false;
}
if(most_right > 0){
num = bits_set(num, 0, most_right);
num = bits_set(num, 1, most_right - 1);
}
else{
int pos;
if(right_0_pos_in_range(pos, num)){
num = bits_set(num, 0, pos);
num = bits_set(num, 1, pos - 1);
}
else{
if(gap == bits){
cout << "it is alread smallest" << num << endl;
return false;
}
cout << "should never come here" << endl;
return false;
}
}
smaller = num;
return true;
}
bool next_larger(int &larger, int num)
{
int found = false;
int most_left = leftest_1_pos(num);
int most_right = rightest_1_pos(num);
int bits = bits_count(num);
int i;
int gap = most_left - most_right + 1;
if(bits == 0){
cout << "there is no bit ones in " << num << " except the sign bit." << endl;
cout << "so there is no nearest larger or smaller " << endl;
return false;
}
if(bits == 31){
cout << "there are all bit ones in " << num << " except the sign bit." << endl;
cout << "so there is no nearest larger or smaller " << endl;
return false;
}
int pos;
if(right_0_pos_in_range(pos, num)){
num = bits_set(num, 1, pos);
num = bits_set(num, 0, pos + 1);
for(i = 0; i< pos; i++){
num = bits_set(num, 0, i);
}
int count = bits_count(num);
for(i = 0; i < bits - count; i++){
num = bits_set(num, 1, i);
}
}
else{
if(most_right < 30){
num = bits_set(num, 1, most_right + 1);
num = bits_set(num, 0, most_right);
for(i = 0; i < bits -1; i++){
num = bits_set(num, 1, i);
}
}
else{
if(gap == bits){
cout << "it is already largest" << endl;
return false;
}
cout << "should never come here" << endl;
return false;
}
}
larger = num;
return true;
}
int main(int argc, char* argv[])
{
int num = 0x3FFFFFFF;
cout.unsetf(ios::dec);
cout.setf(ios_base::hex);
cout.setf(ios::showbase);
cout << "rightest bit pos: " << rightest_1_pos(num) << endl;
cout << "leftest bit pos: " << leftest_1_pos(num) << endl;
cout << "bit ones: " << bits_count(num) << endl;
int nl = 0;
int ns = 0;
cout << "number is: " << num << endl;
if(next_larger(nl, num)){
cout << "next larger is: " << nl << endl;
}
else{
cout << "it is already largest" << nl << endl;
}
if(next_smaller(ns, num)){
cout << "next smaller is: " << ns << endl;
}
else{
cout << "it is already smallest" << ns << endl;
}
return 0;
}
Output