Cracking the coding interview--Q5.5

Hawstein | January 4, 2013

题目

原文:

Write a function to determine the number of bits required to convert integer A to integer B.

Input: 31, 14

Output: 2

译文:

写程序计算从整数A变为整数B需要修改的二进制位数。

输入:31,14

输出:2

解答

这道题目也比较简单,从整数A变到整数B,所需要修改的就只是A和B二进制表示中不同的位, 先将A和B做异或,然后再统计结果的二进制表示中1的个数即可。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
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 convert_num(int a, int b){
    return count_one(a^b);
}

完整代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;

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 convert_num(int a, int b){
    return count_one(a^b);
}
int main(){
    int a = 7, b = 14;
    cout<<convert_num(a, b)<<endl;
    return 0;
}

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview

版权声明:自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证,转载请注明作者及出处。