题目
原文:
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位交换…)
解答
这道题目比较简单。分别将这个整数的奇数位和偶数位提取出来,然后移位取或即可。
代码如下:
1
2
3
int swap_bits(int x){
return ((x & 0x55555555) << 1) | ((x >> 1) & 0x55555555);
}
当然也可以采用更自然的方式来写这段代码:
1
2
3
int swap_bits1(int x){
return ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);
}
上面的代码思路和作用都是一样的,不过按照《Hacker’s delight》这本书里的说法, 第一种方法避免了在一个寄存器中生成两个大常量。如果计算机没有与非指令, 将导致第二种方法多使用1个指令。总结之,就是第一种方法更好。:P
完整代码如下:
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
#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
声明:自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证,转载请注明作者及出处
出处:http://hawstein.com/2013/01/04/5.6/