Cracking the coding interview--Q5.5

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

题目

原文:

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的个数即可。

代码如下:

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);
}

完整代码如下:

#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