文档章节

二进制串反转 Reverse Bits

叶枫啦啦
 叶枫啦啦
发布于 2017/08/22 11:26
字数 770
阅读 7
收藏 0

问题:

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?

Related problem: Reverse Integer

解决:

① 目标:将二进制串反转,原数不断右移取出最低位,赋给新数的最低位后新数再不断左移。

public class Solution { // 2ms
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0;i < 32 ;i ++,n >>= 1) {
            res = res << 1 | (n & 1); //将结果左移然后将最低位取出赋值给新的数(移位运算符优先于|)
        }
        return res;
    }
}

更好理解一点的写法

public class Solution { //2ms
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0;i < 32 ;i ++ ) {
            res = (res << 1) + (n & 1);
            n = n >> 1;
        }
        return res;
    }
}

② 分段相或法:根据Java标准的Integer.reverse()源码。将数字的位按照整块整块的翻转,例如32位分成两块16位的数字,16位分成两个8位进行翻转,这样以此类推直到只有一位。

public class Solution{ //2ms
    public int reverseBits(int n) {
        int res = n;
        res = res >>> 16 | res << 16; //交换前后两个双字节
        res = (res & 0xff00ff00) >>> 8 | (res & 0x00ff00ff) << 8; //交换相邻的两个字节
        res = (res & 0xf0f0f0f0) >>> 4 | (res & 0x0f0f0f0f) << 4; //交换每8位中的前四位和后四位
        res = (res & 0xcccccccc) >>> 2 | (res & 0x33333333) << 2; //交换每4位中的前两位和后两位
        res = (res & 0xaaaaaaaa) >>> 1 | (res & 0x55555555) << 1; //交换每两位
        return res;
    }
}

上面的16进制数字中:

0xff00ff00 = ‭1111 1111 0000 0000 1111 1111 0000 0000‬

0x00ff00ff = 0000 0000 1111 1111 0000 0000 1111 1111

0xf0f0f0f0 = 1111 0000 1111 0000 1111 0000 1111 0000

0x0f0f0f0f = 0000 1111 0000 1111 0000 1111 0000 1111

0xCCCCCCCC =   1100 1100 1100 1100 1100 1100 1100 1100

0x33333333 =      0011 0011 0011 0011 0011 0011 0011 0011

0xAAAAAAAA =    1010 1010 1010 1010 1010 1010 1010 1010

0x55555555 =        0101 0101 0101 0101 0101 0101 0101 0101

/*
    0000 0010 1001 0100 0001 1110 1001 1100
    0001 1110 1001 1100 0000 0010 1001 0100 //每16位交换
    1001 1100 0001 1110 1001 0100 0000 0010 //每8位交换
    1100 1001 1110 0001 0100 1001 0010 0000 //每4位交换
    0011 0110 1011 0100 0001 0110 1000 0000 //每2位交换
    0011 1001 0111 1000 0010 1001 0100 0000 //每1位交换
 */

③ Follow Up:如果该方法被大量调用,或者用于处理超大数据(Bulk data)时有什么优化方法?discuss

大规模数据时算法最基本的优化方法。其实道理很简单,反复要用到的东西记下来就行了,所以我们用Map记录之前反转过的数字和结果。更好的优化方法是将其按照Byte分成4段存储,节省空间。。。。。

public class Solution{ //7ms
    private final Map<Byte, Integer> map = new HashMap<Byte, Integer>();
    public int reverseBits(int n) {
        byte[] bytes = new byte[4];
        for (int i = 0; i < 4; i ++) // convert int into 4 bytes
            bytes[i] = (byte)((n >>> 8 * i) & 0xFF);
        int result = 0;
        for (int i = 0; i < 4; i ++) {
            result += reverseByte(bytes[i]); // reverse per byte
            if (i < 3)
                result <<= 8;
        }
        return result;
    }
    private int reverseByte(byte b) {
        Integer value = map.get(b); // first look up from map
        if (value != null)
            return value;
        value = 0;
        // reverse by bit
        for (int i = 0; i < 8; i ++) {
            value += ((b >>> i) & 1);
            if (i < 7)
                value <<= 1;
        }
        map.put(b, value);
        return value;
    }
}

© 著作权归作者所有

共有 人打赏支持
叶枫啦啦
粉丝 10
博文 563
码字总数 334343
作品 0
海淀
把整数转换成2的n次方的和数组

大概这样:125 => [1, 4, 8, 16, 32, 64] 写几种实现:Ruby: 或者: Haskell:Haskell的整数转成二进制序列比较麻烦,先写一个函数来实现: bits 函数用来将一个整数转换成 二进制的整数 数组...

hell0cat
2016/09/04
35
0
leetcode算法题解(Java版)-2-最长回文子串

一、int数字反转 题目描述 Reverse digits of an integer. Example1: x = 123, return 321 Example2: x = -123, return -321 思路: 题目很简单,需要注意的是:int型是32位的。1000000003 ...

kissjz
04/28
0
0
短信部分——PDU简介及其格式

(九) 短信部分——PDU简介及其格式   PDU是大多数手机短信通讯的核心,仅有少数手机只支持Text模式(例如笔者的MOTO C330)。PDU模式比起Text模式可以提供能为强大的功能,但其编码较Text模...

zhengyijie
2014/02/17
0
0
二进制逆序数

Reverse bits of a given 32 bits unsigned integer. For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in......

golang_yh
2016/02/13
58
0
java简单算法总结

1、翻转字符串 function reverseString(str) { }reverseString("hello"); 2、阶乘算法 public static int factorialize(int num) { } else { } } public static void main(String[] args......

晚天吹凉风
2017/12/18
4
0

没有更多内容

加载失败,请刷新页面

加载更多

打开eclipse出现an error has occurred see the log file

解决方法: 1,打开eclipse安装目录下的eclipse.ini文件; 2,打开的文本文件最后添加一行 --add-modules=ALL-SYSTEM 3,保存重新打开Eclipse。...

任梁荣
昨天
3
0
搞定Northwind示例数据库,无论哪个版本的SQLServer都受用

Northwind数据库 从这里可以找到突破口: http://social.msdn.microsoft.com/Forums/zh-CN/Vsexpressvb/thread/8490a1c6-9018-40c9-aafb-df9f79d29cde 下面是MSDN: http://msdn2.microsoft......

QQZZFT
昨天
1
0
mysql主从同步,安装配置操作

准备 两台mysql服务,我这里准备了如下: 主库:192.168.176.128 从库:192.168.176.131 如何在Linux上安装mysql服务,请看https://blog.csdn.net/qq_18860653/article/details/80250499 操作...

小致dad
昨天
3
0
一个手机装天下,走遍中国都不怕!

导读 “1200元(人民币,下同),微信支付,可以,你扫我。”来自西非马里共和国的展商Albert拿着手机,和一位买走他手鼓的中国游客用简单的汉语交流着。 近日,“第十四届中俄蒙经贸洽谈暨商品...

问题终结者
昨天
2
0
Redis的“死键”问题

大规模的数据库存储系统中,数据的生命周期管理是很有必要的;从业务角度发现过期数据,数据归档和数据碎片整理等。以MySQL为例,1个运行很久的TB级MySQL实例中,极有可能数百GB的数据,对业...

IT--小哥
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部