Pairwise Swap: 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, and so on).
Hints:#145, #248, #328, #355
解法1
意思是把所有奇数位的和偶数位的交换。
先举几个例子：
1
2
3
4
|
bit: 3 2 1 0 | 3 2 1 0 | 3 2 1 0 | 3 2 1 0
--------|---------|---------|--------
num: 0 0 0 1 | 0 0 1 1 | 1 0 1 0 | 0 1 1 0
swap: 0 0 1 0 | 0 0 1 1 | 0 1 0 1 | 1 0 0 1
|
如果我们两个bit两个bit看会发现：
1
2
3
4
5
6
|
before swap | after swap | operation
------------|------------|----------
0 0 | 0 0 | 什么都不做
0 1 | 1 0 | 取反
1 0 | 0 1 | 取反
1 1 | 1 1 | 什么都不做
|
过程：
1
2
3
4
5
6
7
|
n: 10 10 00
mask: 00 11 00
n & mask: 00 10 00 // tmp
~tmp: 11 01 11
tmp & mask: 00 01 00 // a: swapped bits
n & ~mask: 10 00 00 // b
a | b: 10 01 00
|
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public int pairSwap(int n) {
int c = n;
int mask = 3; // bit: 0000 ... 0011
while (mask != 0) {
int tmp = c & mask;
if (tmp != 0 && tmp != mask) {
int sbits = ~tmp & mask; // swap bits
c &= ~mask; // clear bits
c |= sbits; // put swap bits back
}
mask <<= 2;
}
return c;
}
|
解法2
- 把所有偶数位的bit挑出来，向右位移1
- 把所有奇数位的bit挑出来，向左位移1
- 让后把两者OR
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
num: 11 10 01 10
mask1: 10 10 10 10
num & mask1: 10 10 00 10 // a 把偶数bit挑出来
a >> 1 : 01 01 00 01 // a
num: 11 10 01 10
mask2: 01 01 01 01
num & mask2: 01 00 01 00 // b 把奇数bit挑出来
b << 1 : 10 00 10 00 // b
a : 01 01 00 01
b : 10 00 10 00
a | b : 11 01 10 01
num: 11 10 01 10
|
代码：
1
2
3
4
5
6
7
|
public int pairSwap(int n) {
int maskEven = 0xaaaaaaaa;
int maskOdd = 0x55555555;
int a = (n & maskEven) >>> 1;
int b = (n & maskOdd) << 1;
return a | b;
}
|
评论