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?

Related problem: Reverse Integer

题目链接：

---

思路分析

给一个32位unsigned int，要求返回它的按位颠倒后的结果。follow up：如果这个程序被大量访问，如何优化。

直接根据整形计算的定义，对于原来的n从高位开始计算，然后直接加和到返回值的地位上，完成反转。

代码

class Solution { public: uint32_t reverseBits(uint32_t n) { uint32_t res = 0; int count = 31; while(count >= 0){ if(n >= pow(2, count)){ res += pow(2, 31 - count); n = n - pow(2, count); } count--; } return res; } };

时间复杂度： O(1)

---

反思

一开始考虑的复杂了，还写了两个bit和int相互转换的函数，实际上这个问题并没有那么复杂。现在的方法已经是常数时间完成的了。

follow up：更快速的解决方案，直接对位进行操作，省去了复杂的数值计算过程。

class Solution { public: uint32_t reverseBits(uint32_t n) { bitset<32> x(n); bitset<32> y; int j = 31; for (int i = 0; i < 32; i++) { y[i] = x[j--]; } return y.to_ulong(); } };

bitset是C++语言的一个类库，用来方便地管理一系列的bit位而不用程序员自己来写代码。

bitset除了可以访问指定下标的bit位以外，还可以把它们作为一个整数来进行某些统计。

可以如下声明一个该类型变量： bitset<\N>varm (M) 其中varm为变量名。 N表示该类型在内存中占的位数，是二进制。 M表示变量varm的初始值。