算法练习·2的平方判断

算法练习·2的平方判断

题目:判断一个整数是否为2的n次方

举例:

4 = 22

8 = 23

64 = 26

青铜解法:

cufa

由上图可知,只要是2的n次方,一直除以2,最终会等于1

    private static boolean power(Long number){
        //如果是0 直接返回true 2的0次方 = 1
        if(number == 0 ){
            return true;
        }
        while (number % 2 == 0){
            //循环除以2 
            number = number / 2;
        }
        //如果 == 1 说明是2的n次方
        return number == 1;
    }

黄金解法:

  • 所有是2的n次方的数,转换为二进制总会是10000....0的格式,如下图

jz

  • 如果以上的二进制数减一,则会得到如下效果

j1

  • 然后减一之后的结果&上n,则会得到如下效果

yys1

由此可以得出结论。如果m是2的n次方,那么 m & (m-1) = 0

代码实现

    private static boolean power2(Long number){
        if(number < 0 ){
            //2的n次方不存在负数
            return false;
        }
        if(number == 0){
            //如果是0,直接返回true
            return true;
        }
        return (number & (number - 1)) == 0;
    }

这种办法省略了第一种解法的循环,并且在计算机中,位运算是效率最快的方式。

# 算法  java 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×