
问题
颠倒给定的 32 位无符号整数的二进制位。
输入: 43261596
输出: 964176192
解释: 43261596 的二进制表示形式为 00000010100101000001111010011100 ,返回 964176192,其二进制表示形式为 00111001011110000010100101000000 。
进阶:如果多次调用这个函数,你将如何优化你的算法?
Reverse bits of a given 32 bits unsigned integer.
Input: 43261596
Output: 964176192
Explanation: 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?
示例
public class Program { public static void Main(string[] args) { var n = 43261596U; var res = reverseBits(n); Console.WriteLine(res); n = 13U; res = reverseBits2(n); Console.WriteLine(res); n = 168U; res = reverseBits3(n); Console.WriteLine(res); Console.ReadKey(); } public static uint reverseBits(uint n) { //10进制转2进制,除2取余法 var res = 0U; var bit = 0; var times = 32;//Math.Ceiling(Math.Log(n, 2)); //整型4字节,32位 while(n != 0) { //10进制的1,2,3,4,5对应于2进制的1,10,11,100,101 //由于2进制的特点,末位数在1,0之间循环 //用 n 和 1 做“与运算”若值为1,必为奇数 //即除2余1 if((n & 1) == 1) { res += (uint)Math.Pow(2, times - bit - 1); } bit++; //2进制右移1位即10进制除2 n >>= 1; } return res; } public static uint reverseBits2(uint n) { //定义结果 var res = 0U; //执行32次 for(var i = 0; i < 32; i++) { //将结果 *2 res <<= 1; #line 100 //奇数时,把结果 +1 if((n & 1) == 1) res++; //将 n 除以 2 n >>= 1; } //返回结果 return res; } public static uint reverseBits3(uint n) { var res = 0U; for(var i = 0; i < 32; i++) { res <<= 1; //res = res | (n & 1); //奇数跟0进行“或运算”,原值 //偶数跟0进行“或运算”,原值 //奇数跟1进行“或运算”,原值 //偶数跟1进行“或运算”,原值+1 //以下一行代码相当于 #line 100 下的一行 res |= (n & 1); n >>= 1; } return res; } }
以上给出3种算法实现,以下是这个案例的输出结果:
964176192 2952790016 352321536
分析:
显而易见,reverseBits 的时间复杂度为: ,reverseBits2 和 reverseBits3 的时间复杂度为:
。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/4050。