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 ;
}
评论