231.2的幂

LeetCode LeetCode 数学位运算递归

发布时间 : 2000-01-10 02:03

字数:1.5k 阅读 :

评论:

231.2的幂

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
  // 反复除以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;
  }

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