LeetCode | 231.2的幂

这次来写一下 LeetCode 的第 231 题，2的幂。

题目描述

题目直接从 LeetCode 上截图过来，题目如下：

这道题目是考察的是位运算相关的知识，起初开始做的时候认为使用循环解题还是比较容易的，但是后来在学习 Swift 的位运算时，看到了另外的解法，思路简单、代码简洁。

此题，给出了一个简单的函数定义，该函数的定义如下：

bool isPowerOfTwo(int n) {
}

题目分析

题目要求计算一个整数是否是 2 的幂次方。2 的幂次方有一个特点，根据这个特点通过循环可以得出指定的整数是否为 2 的幂次方。来观察一下它的特点。

从上面的图中可以看出，2 的幂次方中，只有一个位为 1，其余位都为 0，且为 1 的位在最高位。只要按照这个规律进行查找，那么就可以很容易的得出一个整数是否为 2 的幂次方。方法很简单，使用循环一边“按位与”一边做“右移”操作，在一个整数大于 1 的情况下，它的最低位如果为 1，那么这个数就不是 2 的幂次方。举个例子。

第一次，整数为 4 时，它的最低位为 0，然后让 4 进行右移操作后变为 2；2 仍然大于 1，且 2 的最低位也为 0，2 进行右移操作后变为 1。此时循环结束。那么 4 是 2 的幂次方。在来看一个反例，比如 6。

通过上面的图可以看出，6 进行右移操作以后变为了 3，而 3 > 1，但是它的最低位为 1，那么，就说明 6 不是 2 的幂次方。

这个方法是我想到的方法，个人感觉比较直观。在我学习 Swift 的位运算时，看到了 2 的幂次方这道题目，但是有不一样的解法，而且不用循环，也超级简单。看图说话吧。

在上面的图中，给出了公式，如果 n & (n - 1) == 0，那么 n 就是 2 的幂次方。比如 4 & (4 - 1) = 0，那么 4 就是 2 的幂次方。而 6 & (6 - 1) = 4，那么 6 就不是 2 的幂次方。这种计算方法真是太优秀了。

代码实现

先来看一下我实现的代码，代码如下：

bool isPowerOfTwo(int n) {
    int num = n;
    
    if ( n <= 0 ) return 0;
       
    while ( num > 1 ) {
        if ( num & 1 == 1 ) {
            return 0;
        }
        num = num >> 1;
    }
    
    return 1;
}

我最开始的思路就是通过循环来判断一个整数是否为 2 的幂次方，但是这样的代码貌似的确是不好理解。甚至我自己再看时，也会对我的代码而感到迷茫。

在来看一下另外的思路，代码如下：

bool isPowerOfTwo(int n) {
    if (n <= 0) return false;

    return (n & (n - 1)) == 0;
}

代码简洁了许多，而且思路也非常的清晰。

提交结果

在写完 isPowerOfTwo 函数体后，点击右下角的 “执行代码”，然后观察 “输出” 和 “预期结果” 是否一致，一致的话就点击 “提交” 按钮。点击 “提交” 按钮后，系统会使用更多的测试用例来测试我们写的函数体，如果所有的测试用例都通过了，那么就会给出 “通过” 的字样，如果没有通过，会给出失败的那一组测试用例，我们继续修改代码。

下面是两种计算方法的执行情况，上面的图是第一种解法的执行情况，下面的图是第二种解法的执行情况。哪个好，哪个差，真的是太明显了。