C#LeetCode刷题之#231-2的幂(Power of Two)

给定一个整数,编写一个函数来判断它是否是 2 的幂次方。

C#LeetCode刷题之#231-2的幂(Power of Two)

问题

给定一个整数,编写一个函数来判断它是否是 2 的幂次方。

输入: 1

输出: true

解释: 20 = 1

输入: 16

输出: true

解释: 24 = 16

输入: 218

输出: false

Given an integer, write a function to determine if it is a power of two.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

示例

public class Program {

    public static void Main(string[] args) {
        var n = 8;
        var res = IsPowerOfTwo(n);
        Console.WriteLine(res);

        n = 513;
        res = IsPowerOfTwo2(n);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    private static bool IsPowerOfTwo(int n) {
        //先看原值是否能被2整除
        //若不能整除,不是2的幂;
        //若能整除,继续往下,直接<=1时为止
        //最后判断值是否为1即可
        while(n % 2 == 0 && (n /= 2) > 1) { }
        return n == 1;
    }

    private static bool IsPowerOfTwo2(int n) {
        //2为10,4为100
        //2-1为01,4-1为011
        //对它们进行“与”运算
        //10 & 01 = 0
        //100 & 011 = 0
        //得出结论,如果一个数n为2的幂,则n & (n - 1) = 0
        return ((n > 0) && (n & (n - 1)) == 0);
    }

}

以上给出2种算法实现,以下是这个案例的输出结果:

True
False

分析:

显而易见,IsPowerOfTwo 的时间复杂度为: O(logn) ,IsPowerOfTwo2 的时间复杂度为: O(1) 。

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

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

发表评论

登录后才能评论