欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

c#二进制逆序方法详解

程序员文章站 2024-02-19 23:53:04
原题 一个整数,可以表示为二进制的形式,请给出尽可能多的方法对二进制进行逆序操作。 例如:10000110 11011000的逆序为 00011011 01100001...

原题

一个整数,可以表示为二进制的形式,请给出尽可能多的方法对二进制进行逆序操作。 例如:10000110 11011000的逆序为 00011011 01100001

分析

题目中说是一个整数,对它的二进制进行逆序。并不是一个01字符串,或者01的数组。那么我们该如何解决这个问题呢?方法还是比较多的,有的中规中矩、有的非常巧妙。我们要掌握中规中规的方法,见识更多的巧妙的方法。慢慢的,能够举一反三,在遇到新的问题时,能够有灵思妙想。

最直接的方法

直接的方法,很容易想到:有如下代码:

复制代码 代码如下:

直接的方法,很容易想到:有如下代码: int v = 111;
int r = v;
int s = 32;
for (; 0 != v; v >>= 1) {
    r <<= 1;
    r |= v & 1;
    s--;
}
r <<= s;
system.out.println(r);

代码比较好理解,取到v的最低位,作为r的最高位;v每取一次最低位,则右移一位;r每确定一位,则左移一位。同时记录移动了多少位,最终要补齐。

通过查表的方法

在遇到位操作的问题时,往往题目中限定了总的位数,比如这个题目,我们可以认为32位。这就给我们带来了一个以空间换时间的解决思路:查表法。位数是固定的,可以申请空间,存储预先计算好的结果,在计算其他的结果的时候,则查表即可。

32位相对于查表来讲,还是太大了。既然这样缩小范围,32个bit,也就是4个byte。每个byte 8bit,可以表示0-255的整数。可以通过申请256大小的数组,保存这256个整数,二进制逆序之后的整数。然后将一个32位的整数,划分为4个byte,每一个byte查表得到逆序的整数:r1,r2,r3,r4。按照r4r3r2r1顺序拼接二进制得到的结果就是最终的答案。

这是一个思路,大家可以进一步思考,尝试。

巧妙的方法

我们这里主要分析这个巧妙的方法,核心思想是:分治法。即:

•逆序32位分解为两个逆序16位的
•逆序16位分解为两个逆序8位的
•逆序8位分解为两个逆序4位的
•逆序4位分解为两个逆序2位的
最后一个2位的逆序,直接交换即可。也就是分治递归的终止条件。但是,在上面的过程中,还没有应用到位操作的技巧。根据动态规划的思想,我们可以自底向上的解决这个问题:

•每2位为一组,进行交换,完成2位逆序
•每4位为一组,前面2位与后面2位交换,完成4位逆序
•每8位为一组,前面4位和后面4为交换,完成8位的逆序
•每16位为一组,前面8位和后面8位交换,完成16位的逆序
2组16位的交换,完成32位的逆序

通过下面的例子,详解上面的过程,我们以16位为例:10000110 11011000

1 0 0 0 0 1 1 0 1 1 0 1 1 0 0 0
0 1 0 0 1 0 0 1 1 1 1 0 0 1 0 0
0 0 0 1 0 1 1 0 1 0 1 1 0 0 0 1
0 1 1 0 0 0 0 1 0 0 0 1 1 0 1 1
0 0 0 1 1 0 1 1 0 1 1 0 0 0 0 1

经过4步,逆序完成。推而广之,总的时间复杂度为o(logn),n是二进制的位数。这个方法可以推广到任意位。

示例代码如下:

int v =111;
v =((v >>1)&0x55555555)|((v &0x55555555)<<1);
v =((v >>2)&0x33333333)|((v &0x33333333)<<2);
v =((v >>4)&0x0f0f0f0f)|((v &0x0f0f0f0f)<<4);
v =((v >>8)&0x00ff00ff)|((v &0x00ff00ff)<<8);
v =( v >>16)|( v <<16);system.out.println(v);上面的思路理解了,代码不难理解。例如第二行,前边是取偶数位,后面是取奇数位,奇数位左移一位,偶数位右移一位,再取或,就是交换了奇数偶数位。也就是第一个步骤。

基于位运算的一些巧妙的方法有很多。大家可以自行研究,后面会和大家分享更多的面试题目。

【分析完毕】