Cracking the coding interview--Q5.6

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



题目

原文:

Write a program to swap odd and even bits in an integer with as few instructions as possible (e.g., bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, etc).

译文:

写程序交换一个整数二进制表示中的奇数位和偶数位,用尽可能少的代码实现。 (比如,第0位和第1位交换,第2位和第3位交换…)

解答

这道题目比较简单。分别将这个整数的奇数位和偶数位提取出来,然后移位取或即可。

代码如下:

int swap_bits(int x){
    return ((x & 0x55555555) << 1) | ((x >> 1) & 0x55555555);
}

当然也可以采用更自然的方式来写这段代码:

int swap_bits1(int x){
    return ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);
}

上面的代码思路和作用都是一样的,不过按照《Hacker’s delight》这本书里的说法, 第一种方法避免了在一个寄存器中生成两个大常量。如果计算机没有与非指令, 将导致第二种方法多使用1个指令。总结之,就是第一种方法更好。:P

完整代码如下:

#include <iostream>
#include <string>
using namespace std;

void print_binary(int x){
    string s = "";
    for(int i=0; i<32 && x!=0; ++i, x >>= 1){
        if(x&1) s = "1" + s;
        else s = "0" + s;
    }
    cout<<s<<endl;
}
int swap_bits(int x){
    return ((x & 0x55555555) << 1) | ((x >> 1) & 0x55555555);
}
int swap_bits1(int x){
    return ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);
}
int main(){
    int x = -7665543;
    print_binary(x);
    print_binary(swap_bits(x));
    print_binary(swap_bits1(x));
    return 0;
}

全书题解目录:

Cracking the coding interview–问题与解答

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

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