Home > 算法研究 > 使用递归位运算实现对字节的中心转置反转

使用递归位运算实现对字节的中心转置反转

字节的中心转置反转,这是一道的IBM技术面试题,供参考
原题如下:
给定一个任意字节长度的数据(以一个Byte为例),要求实现数据的位中心翻转,
也就是数据的对称位数据交换,比如:
1010 1100 -> 0011 0101
1111 1111 -> 1111 1111
0000 0000 -> 0000 0000
1111 0000 -> 0000 1111
解题思路也很简单,只要使用位运算实现以下的位变化即可,但是需要考虑到其他
位的情况,注意运算符的使用即可,IBM不愧是IBM
11 – > 11
00 – > 00
10 – > 01
01 – > 10


以下是C语言和VB.net语言的两种解题实现的代码,VB涉及位转换,效率较低
,但是算法是一样的,同时,这里使用了递归算法

VB.net

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
26
27
28
    '全局变量,保存需要转换的数据
    Private val As Byte
 
    ''' <summary>
    ''' 核心算法,使用递归实现一个Byte的字节中心转置
    ''' </summary>
    ''' <param name="a"></param>
    ''' <remarks></remarks>
    Private Sub fun(ByVal a As Byte)
        If a = 0 Then
            Exit Sub
        End If
        '11 - > 11
        '00 - > 00
        '10 - > 01
        '01 - > 10
        '算法在于排除11和00的情况,01和10反转
        '排除and之后全是0的情况
        If (val And a) <> (CByte(128 / a) And val) Then
            '其中一个为0,另一个必为1 , 全1的情况自然排除
            If (val And a) = 0 Or (CByte(128 / a) And val) = 0 Then
                '进行位运算
                val = CByte(val Xor (a + CByte(128 / a)))
            End If
        End If
        '递归调用
        fun(a / 2)
    End Sub

C/C++

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//C语言实现一个Byte的字节中心转置
#include <STDIO.H>
#include <MATH.H>
 
#define BYTE 8
//#define INTEGER 16
 
#define LENGTH  BYTE
//#define LENGTH INTEGER
 
//求出算子,用于参数传递
#define ARGUMENT pow(2 , (LENGTH / 2 - 1))
//#define ARGUMENT 1 << ( LENGTH/2 -1 ) 
 
#define HIGHT 0x80 /*1000 0000*/
//#define HIGHT 0x8000 /*1000 0000 0000 0000*/
 
unsigned short val = 0;
//unsigned int val = 0;
 
int fun(int a){
 //a为空,返回
 if (0 == a) {
  return 0;
 }
 //'11 - > 11
 //'00 - > 00
 //'10 - > 01
 //'01 - > 10
 //'算法在于排除11和00的情况,01和10反转
 //'排除and之后全是0的情况
 if ( (val &#038; a) != ((HIGHT / a) &#038; val) ){
  //其中一个为0,另一个必为1 , 全1的情况自然排除
  if ( 0 == (val &#038; a) || 0 == ((HIGHT / a) &#038; val) ) {
   //进行位运算
   val = val ^ ((HIGHT / a) + a);
  }
 }
 fun(a / 2);
 //func(a >> 1);
 return 1;
}
 
int main(int argc , char * args[]) {
 //输入
 scanf("%d", &#038;val);
 //递归调用
 fun(ARGUMENT);
 //输出
 printf("%d", val);
 return 0;
}

完整代码下载
http://www.lidaren.com/code/bytecvt/src.zip
VB运行效果

Categories: 算法研究 Tags: ,
  1. No comments yet.
  1. No trackbacks yet.