资讯专栏INFORMATION COLUMN

leetcode190 Reverse Bits

kyanag / 2911人阅读

摘要:思路一比特位移动将比特位逆转过来也就是将十进制数转化为二进制数,再从右往左获得每一位上的值,再将这个值添加至结果值中。根据分治思想,逆转个比特位等价于分别将每个比特位进行逆转。

题目要求
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?
你首先需要知道的事

这里涉及了十进制和二进制之间转化这个知识点。在数学中,我们都是采用十进制进行计算,通俗说就是逢十进一。但是计算机没有那么多类型的信号来对应是十进制数中的十个数字,因此采用了二进制来进行计算。

二进制,也就是所谓的逢二进一,每一位上只有两个数字,分别是0和1。每一个十进制都有一个唯一的二进制数作为对应。我们先来看一下十进制数的计算,比如945等价于9*100+4*10+5*1,也就是9*10^2 + 4*10^1 + 5*10^0。同理我们知道,二进制数011代表0*2^2 + 1*2^1 + 1*2^0也就是十进制的3。这样,我们知道如何将二进制数转化为十进制数。

那么计算机是怎么进行计算的呢?计算机首先将十进制数转化为二进制数,再将二进制数根据需求进行计算。假设计算机需要计算3+6,那么转化为二进制就是11+110,那么计算机的计算流程如下。

1.对齐 在左侧补零位使的两个数字位数相同,因此就是011+110
2.逢二进一 类似于十进制数的逢十进一,因此计算的结果为1001,转化为十进制数就是9

基于二进制的位计算上,除去加减乘除,计算机还定义了一些其他的位运算符

>> 将二进制数右移,左边根据数字的正负形补0或者补1,正数补0,负数补1。
<< 将二进制数左移,右边补0
>>> 将二进制数右移,左边补0

在这些知识的基础上,我们再来看这道题目。

思路一:比特位移动

将比特位逆转过来也就是将十进制数转化为二进制数,再从右往左获得每一位上的值,再将这个值添加至结果值中。

    public int reverseBits(int n) {
        //获得最后一位的值
        int mask = 1;
        int result = 0;
        for(int i=0 ; i<32 ; i++){
            result <<= 1;
            result |= (n & mask);
            n >>= 1;
        }
        return result;
    }
思路二:多次计算的话利用缓存提高销量

为了将比特位逆转,意味着我们至少需要32次循环才能将整个遍历完成。那么如果这个逆转比特位方法会被调用多次的话,我们可以使用一个Map来缓存已经遍历过的情况
但是,32位的重复值往往很少,因此我们可以将整数分解为多个片段存入缓存中,只要遇到重复的片段,就可以将已经得到的结果返回给调用方。根据分治思想,逆转32个比特位等价于分别将每8个比特位进行逆转。因此我们可以将长度为32的unsigned int拆解成4个长度为8的byte。每8个byte对应的值可以作为片段存在缓存中,只要遇到重复的片段,就可以直接返回。

    Map cache = new HashMap();
    public int reverseBits2(int n){
        byte[] bytes = new byte[4];
        for(int i = 0 ; i<4 ; i++){
            // 获得8位并转换为1个byte
            bytes[i] = (byte) ((n>>>(i*8)) & 0xff);
        }
        int result = 0;
        for(int i = 0 ; i<4 ; i++){
            result += reverseByte(bytes[i]);
            if(i<3) result<<=8;
        }
        return result;
    }
    
    public int reverseByte(byte b){
        Integer value = cache.get(b);
        if(value != null) return value;
        value = 0;
        for(int i = 0 ; i<8 ; i++){
            value += ((b>>>i) & 1);
            if(i<7) value <<= 1;
        }
        cache.put(b, value);
        return value;
    }


想要了解更多开发技术,面试教程以及互联网公司内推,欢迎关注我的微信公众号!将会不定期的发放福利哦~

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/61934.html

相关文章

  • leetcode190 Reverse Bits

    摘要:思路一比特位移动将比特位逆转过来也就是将十进制数转化为二进制数,再从右往左获得每一位上的值,再将这个值添加至结果值中。根据分治思想,逆转个比特位等价于分别将每个比特位进行逆转。 题目要求 Reverse bits of a given 32 bits unsigned integer. For example, given input 43261596 (represented in...

    赵连江 评论0 收藏0
  • leetcode部分题目答案之JavaScript版

    摘要:自己没事刷的一些的题目,若有更好的解法,希望能够一起探讨项目地址 自己没事刷的一些LeetCode的题目,若有更好的解法,希望能够一起探讨 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...

    alphahans 评论0 收藏0
  • 前端 | 每天一个 LeetCode

    摘要:在线网站地址我的微信公众号完整题目列表从年月日起,每天更新一题,顺序从易到难,目前已更新个题。这是项目地址欢迎一起交流学习。 这篇文章记录我练习的 LeetCode 题目,语言 JavaScript。 在线网站:https://cattle.w3fun.com GitHub 地址:https://github.com/swpuLeo/ca...我的微信公众号: showImg(htt...

    张汉庆 评论0 收藏0
  • LeetCode 攻略 - 2019 年 7 月上半月汇总(55 题攻略)

    摘要:微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容,进行补充,并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目录 不...

    warmcheng 评论0 收藏0
  • [Leetcode] Reverse Bits 反转位

    摘要:移位法复杂度时间空间思路最简单的做法,原数不断右移取出最低位,赋给新数的最低位后新数再不断左移。代码分段相或法复杂度时间空间思路标准的源码。更好的优化方法是将其按照分成段存储,节省空间。 Reverse Bits Reverse bits of a given 32 bits unsigned integer. For example, given input 43261596 (r...

    notebin 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<