文档章节

二进制串反转 Reverse Bits

叶枫啦啦
 叶枫啦啦
发布于 2017/08/22 11:26
字数 770
阅读 23
收藏 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;
    }
}

© 著作权归作者所有

共有 人打赏支持
叶枫啦啦
粉丝 13
博文 569
码字总数 354997
作品 0
海淀
私信 提问
把整数转换成2的n次方的和数组

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

hell0cat
2016/09/04
35
0
LeetCode算法题-Reverse Bits(Java实现)

这是悦乐书的第185次更新,第187篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第44题(顺位题号是190)。给定32位无符号整数,求它的反转位。例如: 输入:43261596 输出:9...

小川94
2018/11/28
0
0
leetcode算法题解(Java版)-2-最长回文子串

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

kissjz
2018/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

没有更多内容

加载失败,请刷新页面

加载更多

MySQL查询执行

当我们希望MySQL能够以更高的性能运行查询时,最好的办法就是弄清楚MySQL是如何优化和执行查询的。一旦理解了这一点,很多查询优化工作实际上就是遵循一些原则让优化器能够按照预想的合理方式...

问题终结者
47分钟前
0
0
CDH5动静态资源池配置与回滚

关于动态 静态资源池的配置以前都有提过,可以从以下几篇了解: YARN动态资源池配置案例 https://yq.aliyun.com/ziliao/346856# Hadoop YARN配置参数剖析(4)—Fair Scheduler相关参数 Hadoop...

hblt-j
52分钟前
3
0
WordPress仿站实战教程

有一个月没有写blog了,一直在学习wordpress的知识,现在能够进行简单的政府企业门户网站的仿制,wordpress的主题订制,一般是对前端要求比较高,wordpress学会了,建站还是非常的快的。下面...

临江仙卜算子
55分钟前
3
0
图像库stb_image

https://github.com/nothings/stb 目前一般主流的图像格式也就是bmp,jpg,png,tga,dds,除了DDS一般是给DX用的,虽然一堆OpenGL程序也有用的,但是我一般只用png和tga, png不用说了,带a...

robslove
今天
1
0
Spring 事务提交回滚源码解析

前言 在上篇文章 Spring 事务初始化源码分析 中分析了 Spring 事务初始化的一个过程,当初始化完成后,Spring 是如何去获取事务,当目标方法异常后,又是如何进行回滚的,又或是目标方法执行...

TSMYK
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部