leetcode-190-Reverse Bits

题目描述:

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?

要完成的函数:

uint32_t reverseBits(uint32_t n)

说明:

1、给定一个32位的无符号型整数,转化为二进制,二进制反转,再输出对应的十进制。

2、传统方法是:模仿人类思维,十进制转化为二进制,然后用栈反转输出,最后二进制再转化为十进制输出。可以完成本道题目,但是太麻烦了。

3、在计算机中,数值本身就是用二进制存储的,所以我们可以用位操作得到每一位的值,然后“或”到反转之后对应的位上面去,最后直接输出就是十进制了。

   我们这样子做,避免了十进制转化为二进制的浪费时间的操作;避免了用栈,直接“或”到uint32_t类型的数字对应的位上;最后返回的这个数字就是我们要的十进制了。

      经历了前面几道题的洗礼, 现在可以说是十分喜欢位操作了呢,感觉十分简洁。

代码:(笔者本人代码,实测6ms,beats 62.28% of cpp submissions)

uint32_t reverseBits(uint32_t n) 
{
    uint32_t b=1;//要“与”的数值
    uint32_t c;//存放“与”完的数值
    uint32_t d=0;//最终结果,uint32_t类型
    int index=32;
    for(int i=1;i<=16;i++)//处理后面的十六位
    {
        c=n&b;//取出每一位的值
        d|=(c<<(index-i));//把值放到相应的位上
        b<<=1;
        index--;
    }
    for(int i=17;i<=32;i++)//此时index=16,处理前面的十六位
    {
        c=n&b;
        d|=(c>>(i-index));
        b<<=1;
        index--;
    }
    return d;
}

时间复杂度是O(n),比起传统的方法快得不是一丁半点,避免了很多不必要的操作。

但是在discuss区,又看到了大神的更加简洁的做法,跟大家分享一下。

uint32_t reverseBits(uint32_t n) 
{
    uint32_t m = 0;
    for (int i = 0; i < 32; i++, n >>= 1)
    {
        m <<= 1;
        m |= n & 1;
    }
    return m;
}

这样做更加简洁,代码更好写。但其实原理都是一样的,只不过笔者自己的代码中使用了更多的变量,变量也有一些操作,浪费了一点时间。而大神的代码比较巧妙,使用了类似十进制数字翻转的方法,数字不断x10往前挪。

实测5ms,beats 86.90% 0f cpp submissions。

本代码来源于leetcode用户@xcv58。侵删。

在discuss区还看到了时间复杂度为O(logn)的做法,觉得有点厉害哈哈。分享给大家。

uint32_t reverseBits(uint32_t n) 
{
        n = (n >> 16) | (n << 16);//第一次变换
        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);//第二次变换。注意把数字写成二进制形式要在前面加上“0x”
        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);//第三次变换
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);//第四次变换
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);//第五次变换
        return n;
}

其实逻辑是这样的:

以四个二进制数字作为一个单位,初始化为abcdefgh

经过第一次变换,成为efghabcd

经过第二次变换,成为ghefcdab

经过第三次变换,成为hgfedcba

接着对四个二进制数字内部做反转变化,假设四个数字为abcd

经过第四次变换,成为cdab

经过第五次变换,成为dcba

至此,32位数值全部反转完成。

实测5ms,beats 86.90% 0f cpp submissions。

本代码来源于leetcode用户@tworuler。侵删。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏后端技术探索

视觉直观感受 7 种常用的排序算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。...

1012
来自专栏恰童鞋骚年

数据结构基础温故-7.排序

排序(Sorting)是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为按关键字“有序”的记录序列。如何进行排序,特别是高效率地进行排序时计算...

1041
来自专栏Java 源码分析

八大排序算法

​ 八大排序算法是面试经常考到的,尤其是快排,希尔排序和归并也是经常会让写代码的题目,其实只要用一句话说明了他们的原理我们写起代码就没那么困难。 冒泡排序...

5113
来自专栏木头编程 - moTzxx

PHP常见排序算法整理学习

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u011415782/article/de...

2123
来自专栏Golang语言社区

【Go 语言社区】Golang 语言再谈常量

常量是指该程序可能无法在其执行期间改变的固定值。这些固定值也被称为文字。 常量可以是任何像一个整型常量,一个浮点常量,字符常量或字符串文字的基本数据类型。还有枚...

3608
来自专栏desperate633

深入理解python中的排序

进行一个简单的升序排列直接调用sorted()函数,函数将会返回一个排序后的列表:

861
来自专栏C/C++基础

C++虚拟继承与虚基类

C++虚拟继承一般发生在多重继承的情况下。C++允许一个类有多个父类,这样就形成多重继承。多重继承使得派生类与基类的关系变得更为复杂,其中一个容易出现问题是某个...

762
来自专栏菩提树下的杨过

数据结构与算法C#版笔记--排序(Sort)-下

5、堆排序(HeapSort) 在接触“堆排序”前,先回顾一下数据结构C#版笔记--树与二叉树 ,其中提到了“完全二叉树”有一些重要的数学特性: ? 上图就是一...

2035
来自专栏云霄雨霁

字符串排序----高位优先的字符串排序

2481
来自专栏高性能服务器开发

全排列(含递归和非递归的解法)

全排列在近几年各大网络公司的笔试中出现的比较频繁 首先来看看题目是如何要求的(百度迅雷校招笔试题)。 用C++写一个函数, 如 Foo(const char *...

1793

扫码关注云+社区

领取腾讯云代金券