图源：文心一言
上机题目练习整理~🥝🥝
本篇作为基础练习，提供了3种解法以及函数的详细解释，供小伙伴们参考~🥝🥝
- 第1版：在力扣新手村刷题的记录，方法一是自己写的，方法二与方法三是力扣的官方解法~🧩🧩
- 第2版：默默增加了一些小细节，便于理解~🧩🧩
编辑：梅头脑🌸
📇目录
目录
🧵2的幂
🧩题目
给你一个整数
n，请你判断该整数是否是 2 的幂次方。如果是，返回true；否则，返回false。如果存在一个整数
x使得n == 2x，则认为n是 2 的幂次方。示例 1：
输入：n = 1 输出：true 解释：20 = 1示例 2：
输入：n = 16 输出：true 解释：24 = 16示例 3：
输入：n = 3 输出：false示例 4：
输入：n = 4 输出：true示例 5：
输入：n = 5 输出：false
🌰方法一：取对数后幂运算
📇算法思路
- 算法思想：一个整数n，取对数后且再次以2为底的幂运算后记为a，若n==a，则说明这个数字是2的约数。
- 时间复杂度：O(1)。
- 空间复杂度：O(1)。
⌨️算法代码
class Solution {
public:
bool isPowerOfTwo(int n) {
int a = 0;
if (n > 0) {
a = log2(n); // 取余运算
} else {
return false;
}
int a1 = pow(2, a); // 以2为底的幂运算
if (a1 == n)
return true;
else
return false;
}
};⌨️温馨提示
可能问题：请注意，以下写法可能会导致下图的执行错误：
- 第5行直接写为： if (n > =0) ，而非“if (n > 0) ”
问题所在：这个错误是因为我试图将一个负无穷大的值赋给一个整数变量。在代码中，
log2(n)函数在n小于等于0时会返回负无穷大，这是由于log函数的定义所决定的。使用以下代码简单测试：#include <iostream> #include <cmath> using namespace std; int main(){ int a = log2(0); // 结果是-2147483648 // int a = log2(0.5); // 结果是-1 // int a = log2(1); // 结果是0 cout << a << endl; }
🌰方法二：位运算
📇算法思路1
- 算法思想：如果某数是二进制的幂次，则n 的二进制表示中仅包含 1 个 1。我们此处以打表法浅显举栗：
十进制 二进制 是否为二进制数 0 0...00000 否，不含1 1 0...00001 是，含1个1 2 0...00010 是，含1个1 3 0...00011 否，含2个1 4 0...00100 是，含1个1 5 0...00101 否，含2个1 6 0...00110 否，含2个1 7 0...00111 否，含3个1 8 0...01000 是，含1个1 9 0...01001 否，含2个1 10 0...01010 否，含2个1 11 0...01011 否，含3个1 12 0...01100 否，含2个1 13 0...01101 否，含3个1 14 0...01110 否，含3个1 15 0...01111 否，含3个1 16 0...10000 是，含1个1 - 为什么会出现这个现象？十进制转二进制，1=2^0，即2进制的第0位为1；2=2^1，即2进制的第1位为1；4=2^2，即4进制的第2位为2...；按照归纳法，就可以得到若n为2的幂次，则n的二进制只有1位为1；
- 所以问题的核心就在于怎么判断这个数字的二进制只含1个1。
- 力扣官方解法1： (n & (n - 1)) ，即减去1后，如果位数与原数均不相同（即按位与运算为0），则原数仅含1个1；
- 代入数据：
- n=1，则n的二进制 0...00001，n-1的二进制 0...00000，按位与运算0...00000，判断条件 n > 0 && (n & (n - 1)) == 0 为真；
- n=16，则n的二进制 0...10000，n-1的二进制 0...01111，按位与运算0...00000，判断条件 n > 0 && (n & (n - 1)) == 0 为真；
- n=3，则n的二进制 0...00011，n-1的二进制 0...00010，按位与运算0...00010，判断条件 n > 0 && (n & (n - 1)) == 0 为假；
- n=0，未满足条件n>0，跳过后续按位相与判定，为假。
- 时间复杂度：O(1)；
- 空间复杂度：O(1)；
⌨️算法代码1
class Solution {
public:
bool isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
};函数体中的逻辑如下：
return n > 0 && (n & (n - 1)) == 0;这里使用了位运算和逻辑运算来判断
n是否为2的幂次方。
n > 0：首先判断n是否大于0，因为负数和0都不是2的幂次方。(n & (n - 1)) == 0：这是核心的判断逻辑。
- 位与运算(&)会比较
n和n-1的每一位，如果结果为0，说明这两个数的相应位都为0；如果结果不为0，说明至少有一位不相同。- 因此，如果
n是2的幂次方，那么n-1会在二进制表示中至少有一位是1（除了最低位），而与运算的结果会是非零值。- 反之，如果
n-1的二进制表示都是0（除了可能的最高位），那么与运算的结果就是0，说明n是2的幂次方。
📇算法思路2
- 算法思想：
- 力扣官方解法2： (n & -n) ，负数是按照补码规则在计算机中存储的，−n 的二进制表示为 n 的二进制表示的每一位取反再加上 1。
- 补码规则：
- n的原码转-n的原码：int为有符号数字，符号位为最高位，符号为变负即最高位取反，其余不变；
- -n的原码转-n的反码：由于-n一定是负数，按照负数的反码规则，除了符号位（最高1位）不变，数值位（除了最高位）全部取反；
- -n的反码转-n的补码：反码+1；
- 按位与运算：若二进制对应位均为1，则按位与运算结果为1，否则为0；
- 代入数据：
- n=1
- n的二进制原码： 0...00001；
- -n的二进制原码：1...00001；
- -n的二进制反码 ：1...11110；
- -n的二进制补码 1...11111；
- 按位与运算n & (-n)：0...00001；
- 判断条件 n > 0 && (n & (-n) =n ) == 0 为真；
- n=16
- n的二进制原码：0...10000；
- -n的二进制原码：1...10000；
- -n的二进制反码：1...01111；
- -n的二进制补码：1...10000；
- 按位与运算n & (-n)：0...10000；
- 判断条件 n > 0 && (n & (-n) =n ) == 0 为真；
- n=3
- n的二进制原码：0...00011；
- -n的二进制原码：1...00011；
- -n的二进制反码： 1...11100；
- -n的二进制补码： 1...11101；
- 按位与运算n & (-n)：0...00001；
- 判断条件n > 0 && (n & (-n) =n ) == 0 为假；
- n=0，未满足条件n>0，跳过后续按位相与判定，为假。
⌨️算法代码2
class Solution {
public:
bool isPowerOfTwo(int n) {
return n > 0 && (n & -n) == n;
}
};⌨️知识扩展
思维导图：emmm...补码规则听起来有点绕对不对，而且正数负数的存储规则是不一样的，这就涉及到计组的知识了，正好是我来不及整理和发布的那一篇，稍等我Po一下草稿——
备注：
- （发现看着图更绕了对不对）图中只有涂紫色的部分是涉及本题的，其它的是原码、反码、补码、移码的相关知识，随意看看就好~看不清图片的话可以右键存到本地打开~
- 如果对于补码的浅显原理感兴趣，可以参考这个视频：🌸2.1_4_带符号整数的表示和运算_原反补_哔哩哔哩_bilibili
- 如果对于计组的其它知识感兴趣，可以参考这个系列，菜鸟博主明年再战可能还会补充：🌸计算机组成原理_梅头脑_的博客-CSDN博客
🌰方法三：枚举法
📇算法思路
算法思想：再次看向这个粗糙打表，二进制正数每次x2时，表示所有位数左移1位，右端补0；
十进制
二进制 备注 0 0...00000 —— 1 0...00001 —— 2 0...00010 1左移1位 3 0...00011 —— 4 0...00100 2左移1位
1左移2位
5 0...00101 —— 6 0...00110 3左移1位 7 0...00111 —— 8 0...01000 4左移1位
1左移3位
9 0...01001 —— 10 0...01010 5左移1位 11 0...01011 —— 12 0...01100 6左移1位 13 0...01101 —— 14 0...01110 7左移1位 15 0...01111 —— 16 0...10000 8左移1位
1左移4位
题目给定的最大范围是2^30，即为1左移30位的结果。理论上逐个判断1左移1~30次是否与n相同即可。
⌨️算法代码1
class Solution {
static constexpr int BIG = 1 << 30;
public:
bool isPowerOfTwo(int n) {
return n > 0 && BIG % n == 0;
}
};
作者：力扣官方题解
链接：https://leetcode.cn/problems/power-of-two/solutions/796201/2de-mi-by-leetcode-solution-rny3/
⌨️算法解释1
这段代码是一个C++类，名为
Solution，它包含一个私有静态常量整型成员BIG和一个公有成员函数isPowerOfTwo。- 这里定义了一个名为
BIG的静态常量整型变量，并使用左移操作符将其初始化为1向左移30位的结果，即2^30。这实际上是2的幂次方的最大值。static constexpr int BIG = 1 << 30;
- 接下来，我们来看公有成员函数
isPowerOfTwo：
- 这个函数接受一个整数参数
n，并返回一个布尔值。函数首先检查n是否大于0，因为负数和0都不是2的幂次方。- 然后，它使用模运算符（%）来检查
BIG是否能被n整除。如果可以，说明n是一个2的幂次方，函数返回true；否则，返回false。bool isPowerOfTwo(int n) { return n > 0 && BIG % n == 0; }
⌨️函数扩展
constexpr是 C++11 引入的一个关键字，用于声明常量表达式。它有两个主要用途：
编译时常量：当你在类中定义一个
constexpr成员变量时，该变量的初始化表达式必须是编译时常量。这意味着该表达式的值在编译时必须是已知的，并且不能包含任何运行时才能确定的表达式。class MyClass { public: constexpr static int value = 42; // 编译时常量 };
函数修饰符：当你在函数定义前加上
constexpr关键字时，该函数必须满足以下条件：
函数体必须非常小，只包含一个返回语句。
参数类型必须为编译时常量类型。
返回类型必须是
void或const类型。使用constexpr函数可以在编译时计算值，这可以用于优化和常量表达式的计算。constexpr int add(int a, int b) { return a + b; }使用
constexpr可以帮助编译器进行更多的优化，因为它知道变量的值在编译时是确定的，并且可以用于编译时的常量计算。然而，使用constexpr时需要确保你的代码满足其严格的条件，否则编译器会报错。
⌨️算法代码2
class Solution {
public boolean isPowerOfTwo(int n) {
switch (n) {
case 1:
case 2:
case 4:
case 8:
case 16:
case 32:
case 64:
case 128:
case 256:
case 512:
case 1024:
case 2048:
case 4096:
case 8192:
case 16384:
case 32768:
case 65536:
case 131072:
case 262144:
case 524288:
case 1048576:
case 2097152:
case 4194304:
case 8388608:
case 16777216:
case 33554432:
case 67108864:
case 134217728:
case 268435456:
case 536870912:
case 1073741824:
return true;
}
return false;
}
}备注：大佬的沙雕之作，仅供娱乐~~
🔚结语
博文到此结束，写得模糊或者有误之处，欢迎小伙伴留言讨论与批评，督促博主优化内容{例如有错误、难理解、不简洁、缺功能}等，博主会顶锅前来修改~~😶🌫️😶🌫️
我是梅头脑，本片博文若有帮助，欢迎小伙伴动动可爱的小手默默给个赞支持一下，感谢点赞小伙伴对于博主的支持~~🌟🌟
同系列的博文：🌸数据结构_梅头脑_的博客-CSDN博客
同博主的博文：🌸随笔03 笔记整理-CSDN博客
