Leetcode之PHP版题目解析（231. Power of Two)

Created 6 years ago by 吴亲库里, Updated 6 years ago Revision #1 2570 views 0 likes 0 collects

2019-3-20 星期三开始吧

上一题链接 https://laravel.geekai.co/post/19519.html

题目描述

给定一个数,判断他是否是2的幂次方数.

题目分析

常规解法就是递归,因为如果是的话那么这个数肯定能被2整除,他的1/2也能被2整除...

具体实现

xxxxxxxxxx
 
/**
     * @param Integer $n
     * @return Boolean
     */
    function isPowerOfTwo($n) {
       if($n==1){
           return true;
       }
        if($n>=2 && $n%2==0) {
            return $this->isPowerOfTwo($n /2);
        }
    }

其他解法

对于这样的题我们还可以用与(&)运算.

xxxxxxxxxx
 
2的幂次方数   转二进制      减1     
       2         10         01   
       4         100        011 
       8         1000       0111  
      16         100000     011111 
        ............

符合2的幂次方的数他的二进制表示最低位都是1,有且只有一个,如果我们减去1的话,那么最低位就是0,之后位上的数都是1,然后我们吧减去1的数和2的幂次方数进行相与计算,那么最终的结果就是0

实现代码

xxxxxxxxxx
 
/**
     * @param Integer $n
     * @return Boolean
     */
    function isPowerOfTwo($n) {
        if($n<1) {
            return false;
        }
        return ($n & $n-1)===0;
    }