题目
原文：
Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation.
译文：
给定一个整数x，找出另外两个整数，这两个整数的二进制表示中1的个数和x相同， 其中一个是比x大的数中最小的，另一个是比x小的数中最大的。
解答
对于这道题，我们先完成一个最朴素最直接的版本，以保证其正确性。 这个版本可以作为其它版本的验证工具。
什么方法是最直接的呢？给定一个数x，计算出它的二进制表示中1的个数为num， 然后x不断加1并计算其二进制表示中1的个数，当它再次等于num时， 就找到了比x大且二进制表示中1的个数相同的最小的数。类似地， 可以找到比x小且二进制表示中1的个数相同的最大的数，只不过x变为不断减1而已。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int next(int x){
int max_int = ~(1<<31);
int num = count_one(x);
if(num == 0 || x == -1) return -1;
for(++x; count_one(x) != num && x < max_int; ++x);
if(count_one(x) == num) return x;
return -1;
}
int previous(int x){
int min_int = (1<<31);
int num = count_one(x);
if(num == 0 || x == -1) return -1;
for(--x; count_one(x) != num && x > min_int; --x);
if(count_one(x) == num) return x;
return -1;
}
count_one函数的功能是计算一个数的二进制表示中1的个数，这个要怎么实现呢？ 一种方法是通过不断地移位判断最低位是否为1然后计数器累加，代码如下：
1
2
3
4
5
6
7
8
int count_one(int x){
int cnt = 0;
for(int i=0; i<32; ++i){
if(x & 1) ++cnt;
x >>= 1;
}
return cnt;
}
这里for循环可否换成while(x > 0)呢，如果x恒为正数是没问题的，可是如果x为负数，
那么x是无法通过不断地右移变为非负数的。所以这里用for循环比较保险。
这种方法非常直观，不过还有更高效更优美的方法。 这种方法先将相邻的位包含的1的个数相加，然后将相邻每2位包含的1的个数相加， 再然后将相邻每4位包含的1的个数相加……最后即可统计出一个数中包含的1的个数。 代码中大部分操作都是位操作，执行起来非常高效。
代码如下：
1
2
3
4
5
6
7
8
int count_one(int x){
x = (x & (0x55555555)) + ((x >> 1) & (0x55555555));
x = (x & (0x33333333)) + ((x >> 2) & (0x33333333));
x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f));
x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff));
x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff));
return x;
}
好了，接下来考虑除了朴素方案外，有没有更高效的方案。假设给定的数的二进制表示为： 1101110，我们从低位看起，找到第一个1，从它开始找到第一个0，然后把这个0变为1， 比这个位低的位全置0，得到1110000，这个数比原数大，但比它少了两个1， 直接在低位补上这两个1，得到，1110011，这就是最终答案。 我们可以通过朴素版本来模拟这个答案是怎么得到的：
1
1101110->1101111->1110000->1110001->1110010->1110011
接下来，我们来考虑一些边界情况，这是最容易被忽略的地方(感谢细心的读者)。 假设一个32位的整数， 它的第31位为1，即：0100..00，那么按照上面的操作，我们会得到1000..00， 很不幸，这是错误的。因为int是有符号的，意味着我们得到了一个负数。 我们想要得到的是一个比0100..00大的数，结果得到一个负数，自然是不对的。 事实上比0100..00大的且1的个数和它一样的整数是不存在的，扩展可知， 对于所有的0111..，都没有比它们大且1的个数和它们一样的整数。对于这种情况， 直接返回-1。-1的所有二进制位全为1，不存在一个数说1的个数和它一样还比它大或小的， 因此适合作为找不到答案时的返回值。
另一个边界情况是什么呢？就是对于形如11100..00的整数，它是一个负数， 比它大且1的个数相同的整数有好多个，最小的当然是把1都放在最低位了：00..0111。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
int next1(int x){
int xx = x, bit = 0;
for(; (x&1) != 1 && bit < 32; x >>= 1, ++bit);
for(; (x&1) != 0 && bit < 32; x >>= 1, ++bit);
if(bit == 31) return -1; //011.., none satisify
x |= 1;
x <<= bit; // wtf, x<<32 != 0,so use next line to make x=0
if(bit == 32) x = 0; // for 11100..00
int num1 = count_one(xx) - count_one(x);
int c = 1;
for(; num1 > 0; x |= c, --num1, c <<= 1);
return x;
}
类似的方法可以求出另一个数，这里不再赘述。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int previous1(int x){
int xx = x, bit = 0;
for(; (x&1) != 0 && bit < 32; x >>= 1, ++bit);
for(; (x&1) != 1 && bit < 32; x >>= 1, ++bit);
if(bit == 31) return -1; //100..11, none satisify
x -= 1;
x <<= bit;
if(bit == 32) x = 0;
int num1 = count_one(xx) - count_one(x);
x >>= bit;
for(; num1 > 0; x = (x<<1) | 1, --num1, --bit);
for(; bit > 0; x <<= 1, --bit);
return x;
}
完整代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
using namespace std;
int count_one0(int x){
int cnt = 0;
for(int i=0; i<32; ++i){
if(x & 1) ++cnt;
x >>= 1;
}
return cnt;
}
int count_one(int x){
x = (x & (0x55555555)) + ((x >> 1) & (0x55555555));
x = (x & (0x33333333)) + ((x >> 2) & (0x33333333));
x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f));
x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff));
x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff));
return x;
}
int next(int x){
int max_int = ~(1<<31);
int num = count_one(x);
if(num == 0 || x == -1) return -1;
for(++x; count_one(x) != num && x < max_int; ++x);
if(count_one(x) == num) return x;
return -1;
}
int previous(int x){
int min_int = (1<<31);
int num = count_one(x);
if(num == 0 || x == -1) return -1;
for(--x; count_one(x) != num && x > min_int; --x);
if(count_one(x) == num) return x;
return -1;
}
int next1(int x){
int xx = x, bit = 0;
for(; (x&1) != 1 && bit < 32; x >>= 1, ++bit);
for(; (x&1) != 0 && bit < 32; x >>= 1, ++bit);
if(bit == 31) return -1; //011.., none satisify
x |= 1;
x <<= bit; // wtf, x<<32 != 0,so use next line to make x=0
if(bit == 32) x = 0; // for 11100..00
int num1 = count_one(xx) - count_one(x);
int c = 1;
for(; num1 > 0; x |= c, --num1, c <<= 1);
return x;
}
int previous1(int x){
int xx = x, bit = 0;
for(; (x&1) != 0 && bit < 32; x >>= 1, ++bit);
for(; (x&1) != 1 && bit < 32; x >>= 1, ++bit);
if(bit == 31) return -1; //100..11, none satisify
x -= 1;
x <<= bit;
if(bit == 32) x = 0;
int num1 = count_one(xx) - count_one(x);
x >>= bit;
for(; num1 > 0; x = (x<<1) | 1, --num1, --bit);
x <<= bit;
return x;
}
int main(){
int a = -976756;//(1<<31)+(1<<29);//-8737776;
cout<<next(a)<<" "<<previous(a)<<endl; // very slow
cout<<next1(a)<<" "<<previous1(a)<<endl;;
return 0;
}
全书题解目录：
Cracking the coding interview–问题与解答
全书的C++代码托管在Github上：
https://github.com/Hawstein/cracking-the-coding-interview
声明：自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证，转载请注明作者及出处
出处：http://hawstein.com/2013/01/04/5.3/
