frendguo's blog

【LeetCode】190. Reverse Bits

原文地址:https://leetcode.com/problems/reverse-bits/#/description

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?

一般看到这类与位相关的首先就应该想到位运算。

本题首先想到的解题思路就是,从给定的无符号整数的最低位开始,依次移位相加到最终值中。代码如下:

static uint ReverseBits(uint n)
{
	if (n == 0) return 0;
	if (n == 1) return 1;
	uint res = 0;
	for (int i = 0; i < 32; i++)
	{
		res = (res << 1) | (n & 1);
		n >>= 1;
	}

	return res;
}

其中要注意的是,题目的要求是不管给定数最高位是不是0,都应该有32位。所以这里用了个 for 循环 32 次。

这里再来一个厉(装)害(逼)点的算法,纯纯的位运算:

static uint ReverseBits2(uint n)
{
	/// **************************************************
	/// for 8 bit binary number abcdefgh, the process is as follow:
	/// abcdefgh -> efghabcd -> ghefcdab -> hgfedcba
	/// **************************************************
	n = (n >> 16) | (n << 16);
	n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
	n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
	n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
	n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
	return n;
}

时间复杂度应该就是O(log sizeof(int)) 了。。

只能感叹这些神操作啊~继续Coding.......

Happy Coding!o(* ̄▽ ̄*)o

Add comment

Loading