231.2的幂
231.1 题目
给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true；否则，返回 false。
如果存在一个整数 x 使得 n == 2^x，则认为 n 是 2 的幂次方。
示例 1：
输入：n = 1
输出：true
解释：2^0 = 1
示例 2：
输入：n = 16
输出：true
解释：2^4 = 16
示例 3：
输入：n = 3
输出：false
提示：
-2^31 <= n <= 2^31 - 1
231.2 题解
方法一：循环除以2
思路
最直观的方法：反复除以2，看最终能不能变成1。
如果过程中出现奇数（除了最后的1），说明不是2的幂。
举个例子：
- n=16：16→8→4→2→1 ✓
- n=18：18→9（奇数！）✗
复杂度分析
- 时间复杂度：
O(log n)，n 最多被除 log n 次 - 空间复杂度：
O(1)
代码
// 方法一：循环除以2
// 反复除以2，直到n变为1。如果n最终变为1，说明它是2的幂次方。
static bool IsPowerOfTwo1(int n)
{
while (n > 1)
{
// 如果n为奇数，说明不是2的幂次方
if (n % 2 != 0)
{
return false;
}
// 除以2，继续检查下一位
n /= 2;
}
// 如果循环结束，n等于1，说明是2的幂次方
return n == 1;
}
方法二：位运算
思路
2的幂的二进制特点：只有一个1。
- 1 = 0001
- 2 = 0010
- 4 = 0100
- 8 = 1000
利用 n & (n-1) 可以消除最低位的1。如果 n 是2的幂，消除后结果为0。
举个例子：
- n=8 (1000)，n-1=7 (0111)，1000 & 0111 = 0 ✓
- n=6 (0110)，n-1=5 (0101)，0110 & 0101 = 0100 ≠ 0 ✗
注意：n 必须是正数，因为负数和0都不是2的幂。
复杂度分析
- 时间复杂度：
O(1)，一次位运算 - 空间复杂度：
O(1)
代码
// 方法二：位运算
// 如果n是2的幂次方，则它的二进制表示中有且只有一个1。
// 利用 n 且 (n - 1) 的二进制结果，如果是2的幂次方，结果为0。
// 例如，对于 n = 8，其二进制表示为 1000。n - 1 = 7，其二进制表示为 0111。计算 (n & (n - 1))，即 (1000 & 0111)，结果为 0。
static bool IsPowerOfTwo2(int n)
{
// 要求n是正整数
return n > 0 && (n & (n - 1)) == 0;
}
方法三：对数运算
计算以 2 为底的对数，如果结果为整数，则 n 是 2 的幂。由于浮点数精度问题，需要判断对数与最近整数的差值是否足够小。
复杂度分析：
- 时间复杂度：
O(1)，对数运算。 - 空间复杂度：
O(1)，无额外空间。
// 方法三：对数运算
// 判断对数是否近似为整数，若是，则n是2的幂次方。
static bool IsPowerOfTwo3(int n)
{
// 使用对数运算判断2的幂次方，Math.Log(n, 2)得到以2为底的对数
double logarithm = Math.Log(n, 2);
// 判断对数是否近似为整数，使用 Math.Round 近似到最接近的整数
// 使用 Math.Abs 判断对数的小数部分是否足够接近0，以确定是否为整数
// 调整精度，使用足够小的值，例如0.00000000001
return Math.Abs(logarithm - Math.Round(logarithm)) < 0.00000000001;
}
231.3 代码
using System;
class Program
{
static void Main()
{
#region 题目
// 给你一个整数 n，请你判断该整数是否是 2 的幂次方。
// 如果是，返回 true ；否则，返回 false 。
// 如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。
// 示例 1：
// 输入：n = 1
// 输出：true
// 解释：2^0 = 1
// 示例 2：
// 输入：n = 16
// 输出：true
// 解释：2^4 = 16
// 示例 3：
// 输入：n = 3
// 输出：false
// 示例 4：
// 输入：n = 4
// 输出：true
// 解释：2^2 = 4
// 示例 5：
// 输入：n = 5
// 输出：false
// 提示：-231 <= n <= 231 - 1
// 进阶：你能够不使用循环/递归解决此问题吗？
#endregion
#region 测试
// 示例 1
int num1 = 1;
bool result1 = IsPowerOfTwo1(num1);
Console.WriteLine($"示例1 方法1 输出：{result1}");
bool result1_2 = IsPowerOfTwo2(num1);
Console.WriteLine($"示例1 方法2 输出：{result1_2}");
bool result1_3 = IsPowerOfTwo3(num1);
Console.WriteLine($"示例1 方法3 输出：{result1_3}");
// 示例 2
int num2 = 16;
bool result2 = IsPowerOfTwo1(num2);
Console.WriteLine($"示例2 方法1 输出：{result2}");
bool result2_2 = IsPowerOfTwo2(num2);
Console.WriteLine($"示例2 方法2 输出：{result2_2}");
bool result2_3 = IsPowerOfTwo3(num2);
Console.WriteLine($"示例2 方法3 输出：{result2_3}");
// 示例 3
int num3 = 3;
bool result3 = IsPowerOfTwo1(num3);
Console.WriteLine($"示例3 方法1 输出：{result3}");
bool result3_2 = IsPowerOfTwo2(num3);
Console.WriteLine($"示例3 方法2 输出：{result3_2}");
bool result3_3 = IsPowerOfTwo3(num3);
Console.WriteLine($"示例3 方法3 输出：{result3_3}");
// 示例 4
int num4 = 4;
bool result4 = IsPowerOfTwo1(num4);
Console.WriteLine($"示例4 方法1 输出：{result4}");
bool result4_2 = IsPowerOfTwo2(num4);
Console.WriteLine($"示例4 方法2 输出：{result4_2}");
bool result4_3 = IsPowerOfTwo3(num4);
Console.WriteLine($"示例4 方法3 输出：{result4_3}");
// 示例 5
int num5 = 5;
bool result5 = IsPowerOfTwo1(num5);
Console.WriteLine($"示例5 方法1 输出：{result5}");
bool result5_2 = IsPowerOfTwo2(num5);
Console.WriteLine($"示例5 方法2 输出：{result5_2}");
bool result5_3 = IsPowerOfTwo3(num5);
Console.WriteLine($"示例5 方法3 输出：{result5_3}");
#endregion
}
#region 答案
// 方法一：循环除以2
// 反复除以2，直到n变为1。如果n最终变为1，说明它是2的幂次方。
static bool IsPowerOfTwo1(int n)
{
while (n > 1)
{
// 如果n为奇数，说明不是2的幂次方
if (n % 2 != 0)
{
return false;
}
// 除以2，继续检查下一位
n /= 2;
}
// 如果循环结束，n等于1，说明是2的幂次方
return n == 1;
}
// 方法二：位运算
// 如果n是2的幂次方，则它的二进制表示中有且只有一个1。
// 利用 n 且 (n - 1) 的二进制结果，如果是2的幂次方，结果为0。
// 例如，对于 n = 8，其二进制表示为 1000。n - 1 = 7，其二进制表示为 0111。计算 (n & (n - 1))，即 (1000 & 0111)，结果为 0。
static bool IsPowerOfTwo2(int n)
{
// 要求n是正整数
return n > 0 && (n & (n - 1)) == 0;
}
// 方法三：对数运算
// 判断对数是否近似为整数，若是，则n是2的幂次方。
static bool IsPowerOfTwo3(int n)
{
// 使用对数运算判断2的幂次方，Math.Log(n, 2)得到以2为底的对数
double logarithm = Math.Log(n, 2);
// 判断对数是否近似为整数，使用 Math.Round 近似到最接近的整数
// 使用 Math.Abs 判断对数的小数部分是否足够接近0，以确定是否为整数
// 调整精度，使用足够小的值，例如0.00000000001
return Math.Abs(logarithm - Math.Round(logarithm)) < 0.00000000001;
}
#endregion
}
231.4 运行结果
示例1 方法1 输出：True
示例1 方法2 输出：True
示例1 方法3 输出：True
示例2 方法1 输出：True
示例2 方法2 输出：True
示例2 方法3 输出：True
示例3 方法1 输出：False
示例3 方法2 输出：False
示例3 方法3 输出：False
示例4 方法1 输出：True
示例4 方法2 输出：True
示例4 方法3 输出：True
示例5 方法1 输出：False
示例5 方法2 输出：False
示例5 方法3 输出：False
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
