力扣- -231. 2的幂

文章目录

力扣- -231. 2的幂一、题目描述二、问题分析三、代码方法一：暴力统计方法二：位运算(获取二进制中最右边的 1)方法三：位运算(去除二进制中最右边的 1) 看一道对位运算特别巧的简单题

一、题目描述

class Solution { public: bool isPowerOfTwo(int n) { } };

二、问题分析

这道题的主要思想是数字n的特殊性 因为数字n是2的幂(注意是2的幂，并不是2的倍数)，那么这道题就简单了，因为2的幂的数字的特性就是n的所有比特位中只有一个比特位为1；

三、代码

方法一：暴力统计

class Solution { public: bool isPowerOfTwo(int n) { if(n == 0) { return false; } while (n % 2 == 0) n /= 2; return n == 1; } }; 时间复杂度为 $O(logN)$ 该问题将通过位运算在 $O(1)$ 的时间复杂度解决，通过使用如下的按位技巧：如何获取二进制中最右边的 1：$x$ & $(-x)$。如何将二进制中最右边的 1 设置为 0：$x$ & $(x-1)$。

方法二：位运算(获取二进制中最右边的 1)

获取最右边的 1：$x$ & $(-x)$。

首先讨论为什么 $x$ & $(-x)$可以获取到二进制中最右边的 1，且其它位设置为 0。

在补码表示法中，$-x$ $=$ $\neg x$ $+$ $1$。换句话说，要计算 $-x$，则要将 $x$ 所有位取反再加 1。

在二进制表示中，$\neg x$ $+$ $1$表示将该 1 移动到 $\neg x$ 中最右边的 0 的位置上，并将所有较低位的位设置为 0。而 $\neg x$ 最右边的 0 的位置对应于 $x$ 最右边的 1 的位置。

总而言之，$-x$ $=$ $\neg x$ $+$ $1$，此操作将 $x$ 所有位取反，但是最右边的 1 除外。

因此，$x$ 和 $-x$ 只有一个共同点：最右边的 1。这说明 $x$ & $(-x)$ 将保留最右边的 1。并将其他的位设置为 0。

检测是否为 2 的幂：

我们通过 $x$ & $(-x)$ 保留了最右边的 1，并将其他位设置为 0 若 $x$ 为 2 的幂，则它的二进制表示中只包含一个 1，则有 $x$ & $(-x)=x$。

若 $x$ 不是 2 的幂，则在二进制表示中存在其他 1，因此 $x$ & $(-x)!=x$。

因此判断是否为 2 的幂的关键是：判断 $x$ & $(-x)==x$。

class Solution { public: bool isPowerOfTwo(int n) { if(n == 0) { return false; } long long ret = (long long)n; return (ret & (-ret)) == ret; } }; 时间复杂度：$O(1)$。空间复杂度：$O(1)$

方法三：位运算(去除二进制中最右边的 1)

去除二进制中最右边的 1：$x$ & $(x-1)$

首先讨论为什么 $x$ & $(x-1)$ 可以将最右边的 1 设置为 0。

$(x-1)$ 代表了将 $x$ 最右边的 1 设置为 0，并且将较低位设置为 1。

再使用与运算：则 x 最右边的 1 和就会被设置为 0，因为 1 & 0 = 0。

检测是否为 2 的幂：

2 的幂二进制表示只含有一个 1。

$x$ & $(x-1)$ 操作会将 2 的幂设置为 0，因此判断是否为 2 的幂是：判断 $x$ & $(x-1)==0$。

class Solution { public: bool isPowerOfTwo(int n) { if(n == 0) { return false; } long long ret = (long long)n; return (ret & (ret - 1)) == 0; } }; 时间复杂度：$O(1)$。空间复杂度：$O(1)$

总之，这道题还是比较简单的，就是位运算的运用