c#二进制逆序方法详解

原题

一个整数，可以表示为二进制的形式，请给出尽可能多的方法对二进制进行逆序操作。 例如：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);上面的思路理解了，代码不难理解。例如第二行，前边是取偶数位，后面是取奇数位，奇数位左移一位，偶数位右移一位，再取或，就是交换了奇数偶数位。也就是第一个步骤。

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

【分析完毕】

赞 (0)

相关推荐

  • 解析c#在未出现异常情况下查看当前调用堆栈的解决方法

    C#查看堆栈通常是在异常处理中,出现异常之后通过异常的堆栈可以很方便的得到出现这个错误的代码调用路径.这个很有用,是否可以在没有异常出现时使用这种方法排查一些非异常错误呢?答案是肯定的.起因:论坛发帖子有几个途径,有可能是新闻系统直接导入的帖子,也有可能是抓取的帖子,还有可能是用户通过正常途径发表.但是这两天出了一个问题,有些帖子的HasImage属性不对.通过几种方法做调试都不能重现问题,没有办法,只有在程序中添加回复的地方添加日志程序来记录堆栈,从而追踪到是哪个途径发帖出现了问题.代码: 复

  • C#数据结构与算法揭秘五 栈和队列

    C#数据结构与算法揭秘五 栈和队列

    这节我们讨论了两种好玩的数据结构,栈和队列. 老样子,什么是栈, 所谓的栈是栈(Stack)是操作限定在表的尾端进行的线性表.表尾由于要进行插入.删除等操作,所以,它具有特殊的含义,把表尾称为栈顶(Top) ,另一端是固定的,叫栈底(Bottom) .当栈中没有数据元素时叫空栈(Empty Stack).这个类似于送饭的饭盒子,上层放的是红烧肉,中层放的水煮鱼,下层放的鸡腿.你要把这些菜取出来,这就引出来了栈的特点先进后出(First in last out).   具体叙述,加下图. 栈通常记

  • C#递归实现将一整数逆序后放入一数组中

    本文实例讲述了C#递归实现将一整数逆序后放入一数组中的方法,分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: static void Main(string[] args) {     int m = 1236578;     int[] ms = new int[m.ToString().Length];     Rev(m.ToString().Length, m, ref ms);     for (int i = 0; i < m.ToString().Length; i+

  • C#使用foreach语句遍历堆栈（Stack）的方法

    本文实例讲述了C#使用foreach语句遍历堆栈(Stack)的方法.分享给大家供大家参考.具体如下: using System; using System.Collections; public class StacksW3 { static void Main(string[] args) { Stack a = new Stack(10); int x = 0; a.Push(x); x++; a.Push(x); foreach (int y in a) { Console.WriteL

  • 浅谈C#中堆和栈的区别（附上图解）

    浅谈C#中堆和栈的区别（附上图解）

    线程堆栈:简称栈 Stack 托管堆: 简称堆 Heap 使用.Net框架开发程序的时候,我们无需关心内存分配问题,因为有GC这个大管家给我们料理一切.如果我们写出如下两段代码: 代码段1: public int AddFive(int pValue) { int result; result = pValue + 5; return result; } 代码段2: public class MyInt { public int MyValue; } public MyInt AddFive(i

  • 一看就懂：图解C#中的值类型、引用类型、栈、堆、ref、out

    一看就懂：图解C#中的值类型、引用类型、栈、堆、ref、out

    C# 的类型系统可分为两种类型,一是值类型,一是引用类型,这个每个C#程序员都了解.还有托管堆,栈,ref,out等等概念也是每个C#程序员都会接触到的概念,也是C#程序员面试经常考到的知识,随便搜搜也有无数的文章讲解相关的概念,貌似没写一篇值类型,引用类型相关博客的不是好的C#程序员.我也凑个热闹,试图彻底讲明白相关的概念. 程序执行的原理 要彻底搞明白那一堆概念及其它们之间的关系似乎并不是一件容易的事,这是因为大部分C#程序员并不了解托管堆(简称"堆")和线程栈(简称"栈

  • C#使用Object类实现栈的方法详解

    本文实例讲述了C#使用Object类实现栈的方法.分享给大家供大家参考,具体如下: Stack类的代码: using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace 使用Object类实现后进先出队列 { class Stack { private Object[] _items; public Object[] Items { get { return this.

  • C#创建安全的栈(Stack)存储结构

    在C#中,用于存储的结构较多,如:DataTable,DataSet,List,Dictionary,Stack等结构,各种结构采用的存储的方式存在差异,效率也必然各有优缺点.现在介绍一种后进先出的数据结构. 谈到存储结构,我们在项目中使用的较多.对于Task存储结构,栈与队列是类似的结构,在使用的时候采用不同的方法.C#中栈(Stack)是编译期间就分配好的内存空间,因此你的代码中必须就栈的大小有明确的定义:堆是程序运行期间动态分配的内存空间,你可以根据程序的运行情况确定要分配的堆内存的大小.

  • c#栈变化规则图解示例(栈的生长与消亡)

    c#栈变化规则图解示例(栈的生长与消亡)

    栈的变化规则:1.方法调用会导致栈的生长,具体包括两个步骤:一.插入方法返回地址(下图中的Fn:):二.将实际参数按值(可以使用ref或out修饰)拷贝并插入到栈中(可以使用虚参数访问).2.遇到局部变量定义会向栈中插入局部变量.3.遇到return语句会导致栈消亡,一直消亡到方法返回地址,并把return的返回值设置到方法返回地址中.4.这里先不考虑中括号导致的栈的消亡. 复制代码 代码如下: using System;using System.Collections.Generic;usin

  • C#栈和堆的区别浅谈

    理解堆与栈对于理解.NET中的内存管理.垃圾回收.错误和异常.调试与日志有很大的帮助.垃圾回收的机制使程序员从复杂的内存管理中解脱出来,虽然绝大多数的C#程序并不需要程序员手动管理内存,但这并不代表程序员就无需了解分配的对象是如何被回收的,在一些特殊的场合仍需要程序员手动进行内存管理. 在32位的处理器上,每个进程的虚拟内存为4GB,.NET会在这4GB的内存块中开辟出3块内存,分别作为栈.托管堆.和非托管堆 堆(heap): 堆是从下往上分配,所以已用的空间在自由空间下面,C#中所有引用类型的

  • C#实现用栈求逆序的方法示例

    本文实例讲述了C#实现用栈求逆序的方法.分享给大家供大家参考,具体如下: 用栈求逆序 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Collections; namespace CSharp { class Program { static void Main(string[] args) { Stack stk = new Stack();//

  • C#数据结构之堆栈(Stack)实例详解

    C#数据结构之堆栈(Stack)实例详解

    本文实例讲述了C#数据结构之堆栈(Stack).分享给大家供大家参考,具体如下: 堆栈(Stack)最明显的特征就是"先进后出",本质上讲堆栈也是一种线性结构,符合线性结构的基本特点:即每个节点有且只有一个前驱节点和一个后续节点. 相对前面学习过的顺序表.链表不同的地方在于:Stack把所有操作限制在"只能在线性结构的某一端"进行,而不能在中间插入或删除元素.下面是示意图: 从示意图中可以看出,堆栈有二种实现方式:基于数组的顺序堆栈实现.类似链表的链式堆栈实现 先抽

随机推荐