h31i的吐槽

一个关于2的次方问题

发表于 分类于

问题：判断一个正整数是否是2的次方（比如16是2的四次方，返回1；不是则返回0）。（要求性能尽可能高）

解法一

1
2
3
4
5
6
7
8
9
10
int check(int number){
    int temp = 1;
    while(temp <= number){
        if(temp == number){
            return 1;
        }
        temp = temp * 2;
    }
    return 0;
}

思路简单一个一个比较，时间复杂度O(logN)

解法二

1
2
3
4
5
6
7
8
9
10
11
int check(int number){
    int temp = 1;
    while(temp <= number){
        if(temp == number){
            return 1;
        }
        temp = temp << 1;
    }
    return 0;
}

通过位运算进行了一点优化，时间复杂度仍然为O(logN)，本质上没什么区别

解法三

1
2
3
4
5
6
7
8
int check(int number){
    if(number & (number-1) == 0){
        return 1;
    }
    else{
        return 0;
    }
}

通过一次减法和与运算，时间复杂度只有O(1),在本质上有很大的优化。

具体思路： 2的n次方数的二进制是有规律的

2:  10          2-1:    1       &   0
4:  100         4-1:    11      &   0
8:  1000        8-1:    111     &   0
16: 10000       16-1:   1111    &   0
32: 100000      32-1:   11111   &   0
...             ...
2^n             2^n-1

7:  0111        7-1:    0110    &   0110
36: 100100      36-1：  100011  &   100000

将左右两边的结果做与运算，结果很明显。

计算机算加减乘除的时间对比

位运算 优化运算速度

2018/10/12

By PQ