Cracking the coding interview--Q5.3

January 4, 2013
作者:Hawstein
出处:http://hawstein.com/posts/5.3.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。



题目

原文:

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而已。

代码如下:

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然后计数器累加,代码如下:

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的个数。 代码中大部分操作都是位操作,执行起来非常高效。

代码如下:

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,这就是最终答案。 我们可以通过朴素版本来模拟这个答案是怎么得到的:

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。

代码如下:

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);
    for(; bit > 0; x <<= 1, --bit);
    return x;
}

完整代码如下:

#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