LeetCode 231 Power of Two | 判断数是否为2的幂

题目来源：LeetCode: 231. Power of Two

Given an integer, write a function to determine if it is a power of two.

思路

  • 按位操作为出发点
  • 所有2的幂数共性为：二进制中某一位为1，其他位均为0
  • 逐位右移，当遇到首个非0的位时，判断是否仅存在唯一的1

时间复杂度：O(logn), 空间复杂度O(1)

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//231. Power of Two
//LeetCode: https://leetcode.com/problems/power-of-two/
#include<stdio.h>
#include<stdbool.h>

bool isPowerOfTwo(int n) {
    if(n==0)
        return false;
    int val = n&1;
    while(val==0) {
        n >>= 1;
        val = n&1;
    }
    val = n^0;
    if(val==1)
        return true;
    else
        return false;
}

void main(){
    int n = 1024;
    bool res = isPowerOfTwo(n);
    printf("Result whether %d isPowerOfTwo is : %s\n", n, (res==0)?"False":"True");
}

运行结果：

1108 / 1108 test cases passed.
Status: Accepted
Runtime: 4 ms
Submitted: 0 minutes ago

You are here! Your runtime beats 47.39% of csubmissions.

总结

  1. 注意特殊情况的处理，即n=0的情况。
  2. 判断一个数奇偶性时，可以用%2的形式，也可以用&1的方式。
  3. 注意运算符的优先级

    ==和!=的优先级高于地址操作符(&, ^, |)

  4. C99标准后的C语言支持bool布尔类型，需引入头文件stdbool.h

    C语言不同标准的差异，参见ANSI C与C89、C99、C11区别差异

附表：C和C++中运算符优先级与结合性

C语言运算符优先级与结合性
C++语言运算符优先级与结合性