231.md

✏️Leetcode基础刷题之(231. Power of Two)

2019-03-20 吴亲库里 库里的深夜食堂

---

✏️描述

给定一个数判断是不是2的幂次方数

---

✏️题目实例

​

✏️题目分析

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

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

---

✏️其他

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

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

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

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

联系

​