LeetCode Algorithm

LeetCode - 231. 2的幂次（Power of Two）

Posted by zihengCat on 2018-02-26

前言

本文记录LeetCode - 231. 2的幂次（Power of Two）问题。

问题描述

给出一个整型数，判断该数是否是2的幂次。

注：只考虑是否为2的非负整数次幂即可。

例：

输入: 4
输出: true

输入: 6
输出: false

注: 4为2^2。

问题解法

常规解法

只需考虑是否为2的非负整数次幂，大大简化了问题。

2的幂次形如：2 * 2 * 2...* 2，均可被2无限整除。利用这个特性，我们就可以轻松解决此问题。

int isPowerOfTwo(int n) {
    /* 排除掉负数和0 */
    if(n <= 0) {
        return 0;
    }
    /* 设置商和余数 */
    int quotient  = n,
        remainder = 0;
    /* 循环退出条件: 商为1（除尽） */
    while(quotient != 1) {
        remainder = quotient % 2;
        quotient /= 2;
        /* 如果有余数（除不尽） */
        if(remainder) {
            return 0;
        }
    }
    return 1;
}

C/C++ 代码（常规解法）

特殊解法

这道题的特殊解法是利用2的幂次数的二进制特性。

例如：

2的幂次 十进制形式 二进制形式
2 ^ 0 1 00000001
2 ^ 1 2 00000010
2 ^ 2 4 00000100
2 ^ 3 8 00001000
2 ^ 4 16 00010000
2 ^ 5 32 00100000
2 ^ 6 64 01000000
2 ^ 7 128 10000000

所有2的幂次数，都是最高二进制位值为1，其他位均为0的数字。利用这个特性，我们可以使用位操作进行判断。

n-1得到最高位为0，其他位均为1的数，再与n做按位与&操作，得到0（所有二进制位都为0）。如果该数不是2的幂次，结果必然不会是0。

int isPowerOfTwo(int n) {
    return (n > 0) && !(n & (n - 1));
}

C/C++ 代码（特殊解法）

FEATURED TAGS
LeetCode Algorithm