C#LeetCode刷题之#190-颠倒二进制位(Reverse Bits)

C#LeetCode刷题之#190-颠倒二进制位(Reverse Bits)

问题

颠倒给定的 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 的时间复杂度为: O(logn)​ ,reverseBits2 和 reverseBits3 的时间复杂度为: O(1)​ 。

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/4050

发表评论

登录后才能评论