数的奥秘之幂数与完全平方数

2022 年 6 月 10 日
本文字数：3379 字
阅读完需：约 11 分钟

⛄️Part1.幂数⛄️

⭐️2 的幂⭐️

🔐题目详情

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。如果存在一个整数 x 使得 $n = 2^{x}$ ，则认为 n 是 2 的幂次方。

示例：

输入：n = 1输出：true解释：20 = 1输入：n = 16输出：true解释：24 = 16输入：n = 3输出：false

复制代码

提示： $n$ 的范围为整型 $i n t$ 的范围。

💡解题思路

利用 $2$ 的幂的二进制序列中只有一个1并且大于0的性质，将此题转换为求二进制中1的个数，如果为1个，则该数为 $2$ 的幂。二进制 1 的个数求法：参考历史博文：剑指offer系列——剑指 Offer 15. 二进制中1的个数（C语言）

方法 1： 以 C 语言为例，整型的储存形式是 32 位二进制序列，内存中储存的补码，对于正整数，二进制原码补码相同，对于负整数，补码是在原码除最高位取反得到反码的基础上加 1。最先想到的就是对输入的整数的二进制序列每一位进行判断是否是 1。我们可以将这个二进制序列与1进行按位与运算，由于1的二进制序列只有末位是1，所以如果这个二进制序列的末位为1则返回1，否则返回0。然后我们再对这个二进制序列进行右移位操作，这样就能舍弃最右边的一个序列，经过 32 次操作，就能判断整个二进制序列有多少个1。

方法 2： 假设输入的整数为n，我们不妨将n与n-1进行按位与运算，然后你会发现运算的结果与 n 相比，二进制序列中少了一个1，通俗来说，每进行一次这样的运算，二进制中的1就会减少一个，我们可以根据这种运算的特点来设计解法。我们可以将每次n&(n-1)的结果保存给n，直到n=0。计算进行运算的次数，即1的个数。

上面两种方法都可以求二进制序列中 1 的位数，本文采取方法 2。

❓为什么 $2 的幂$ 的二进制序列只有一个1？

不妨设一个数的二进制序列为，其中 $a, b, c, d$ 为0或1

：

a b c d

则所对应十进制数 $x = d \times 2^{0} + c \times 2^{1} + b \times 2^{2} + a \times 2^{3}$ 如果一个数为 $2$ 的幂，则 $a, b, c, d$ 中有且只有一个数为 $1$ 其他均为 $0$ 。推广一下，对于 32 位，64 位二进制也是如此。

🔑源代码

Java

//具体写class Solution {    public boolean isPowerOfTwo(int n) {        int count = 0;        if (n < 0){            return false;        }        while (n != 0){            n &= n - 1;            count++;        }        if(count == 1){            return true;        }        else{            return false;        }    }}

复制代码

//简略写class Solution {    public boolean isPowerOfTwo(int n) {        return n > 0 && ((n & (n - 1)) == 0);    }}

复制代码

bool isPowerOfTwo(int n){    return n > 0 && ((n & (n - 1)) == 0);}

复制代码

C++

class Solution {public:    bool isPowerOfTwo(int n) {        return n > 0 && ((n & (n - 1)) == 0);    }};

复制代码

⭐️3 的幂⭐️

🔐题目详情

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。整数 n 是 3 的幂次方需满足：存在整数 x 使得 $n = 3^{x}$ 。

示例：

输入：n = 27输出：true输入：n = 45输出：false

复制代码

提示： $n$ 的范围为整型 $i n t$ 的范围。

💡解题思路

如果一个数是3的幂，那么这个数一直除3，第一次不能被除尽时，被除数一定为1。比如 9，9/3=3,3/3=1，1不能被3除尽，此时被除数为1。如果一个数不是 3 的幂一直除3第一次不能除尽的被除数一定不是1。换个说法，3的幂由因子3与1组成，所以不断除以3，最后得到的数一定是另一个因子1。

🔑源代码

Java

class Solution {    public boolean isPowerOfThree(int n) {        if (n <= 0) {            return false;        }        int m = n;        while (m % 3 == 0) {            m /= 3;        }        if (m == 1) {            return true;        }        else {            return false;        }    }}

复制代码

bool isPowerOfThree(int n){    if (n <= 0)     {        return 0;    }    int m = n;    while(m % 3 == 0)    {        m /= 3;    }    if (m == 1)     {        return true;    }    return false;}

复制代码

C++

class Solution {public:    bool isPowerOfThree(int n) {        if (n <= 0)         {            return 0;        }        int m = n;        while(m % 3 == 0)        {            m /= 3;        }        if (m == 1)         {            return true;        }        return false;    }};

复制代码

⭐️4 的幂⭐️

🔐题目详情

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。整数 n 是 4 的幂次方需满足：存在整数 x 使得 $n = 4^{x}$ 。

示例：

输入：n = 16输出：true输入：n = 5输出：false

复制代码

提示： $n$ 的范围为整型 $i n t$ 的范围。

💡解题思路

一个大于 0 的数，该数的二进制只有一位是 1 且该数模 3 的结果为 1，则该数为 4 的幂。

🔎推导：由二项式定理：

4^{x} = (3 + 1)^{x} = k_{0} \times 3^{x} \times 1^{0} + k_{1} \times 3^{x - 1} \times 1^{1} + . . . + k_{x} \times 3^{0} \times 1^{x}

其中最末项系数 $k_{x} = C_{x}^{x} = 1$ ，所以 $4^{x}$ 。

4 的幂一定也是 2 的幂，所以它的二进制中与 2 的幂一样只有一个 1，一个数是 2 的幂但不是 4 的幂，同由二项式定理，该数模 3 结果一定是 2：

y = 2^{x} = (3 - 1)^{x} = k_{0} \times 3^{x} \times (- 1)^{0} + k_{1} \times 3^{x - 1} \times (- 1)^{1} + . . . + k_{x} \times 3^{0} \times (- 1)^{x}

其中最末项系数 $k_{x} = C_{x}^{x} = 1$ 。x 为偶数时，该数既是 2 的幂也是 4 的幂，此时 $(- 1)^{x} = 1$ ，

原 式 = k_{0} \times 3^{x} \times (- 1)^{0} + k_{1} \times 3^{x - 1} \times (- 1)^{1} + . . . + 1

得到 $y$ 。x 为奇数时，该数是 2 的幂但不是 4 的幂，此时 $(- 1)^{x} = - 1$ ，

原 式 = k_{0} \times 3^{x} \times (- 1)^{0} + k_{1} \times 3^{x - 1} \times (- 1)^{1} + . . . - 1 = k_{0} \times 3^{x} \times (- 1)^{0} + k_{1} \times 3^{x - 1} \times (- 1)^{1} + . . . - 3 + 2

得到 $y$ 。再加上 4 的幂和 2 的幂一样，二进制序列中只有一个1

，所以可以得出结论：

一 个 大 于 0 的 数 ， 该 数 的 二 进 制 只 有 一 位 是 1 且 该 数 模 3 的 结 果 为 1 ， 则 该 数 为 4 的 幂 。

🔑源代码

Java

class Solution {    public boolean isPowerOfFour(int n) {        return n > 0 && ((n &(n-1)) == 0) && n % 3 == 1;    }}

复制代码

bool isPowerOfFour(int n){    return n > 0 && ((n &(n-1)) == 0) && n % 3 == 1;}

复制代码

C++

class Solution {public:    bool isPowerOfFour(int n) {        return n > 0 && ((n &(n-1)) == 0) && n % 3 == 1;    }};

复制代码

⛄️Part2.完全平方数⛄️

⭐️完全平方数⭐️

🔐题目详情

给定一个正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。进阶：不要使用任何内置的库函数，如 sqrt 。

示例：

输入：num = 16输出：true输入：num = 14输出：false

复制代码

提示： $1 < = n u m < = 2^{31} - 1$

💡解题思路

方法 1：暴力遍历，注意溢出，不推荐。方法 2：利用 $1 + 3 + 5 + 7 + 9 + \dots + (2 n - 1) = n^{2}$ 公式计算。方法 3：二分查找，具体看代码。

🔑源代码

方法 1：Java

class Solution {    public boolean isPerfectSquare(int num) {        for (int i = 1; (long)(i * i) <= (long)num && i <= num / 2 + 1; i++) {            if (i * i == num) {                return true;            }        }        return false;    }}

复制代码

方法 2：C

bool isPerfectSquare(int num){    int i = 1;    long sum = 0;    while (sum <= num) {        if (sum == num) {            return true;        }        sum += i;        i += 2;    }    return false;}

复制代码

方法 3：Java

class Solution {    public boolean isPerfectSquare(int num) {        int left = 1;        int right = num;        while (left <= right) {            int mid = left + (right - left) / 2;            int div = num / mid;            if (mid == div) {                if (mid * div == num) {                    return true;                }                left = mid + 1;            }else if (mid > div) {                right = mid - 1;            }else {                left = mid + 1;            }        }        return false;    }}

复制代码

🌱总结🌱

$2$ 的幂的二进制序列中只有一个1并且大于0。
$3$ 的幂由因子3与1组成，所以不断除以3，最后得到的数一定是另一个因子1。
一个大于0的数，该数的二进制只有一位是1且该数模3的结果为1，则该数为 $4$ 的幂。
计算完全平方数公式： $1 + 3 + 5 + 7 + 9 + \dots + (2 n - 1) = n^{2}$

发布于: 刚刚阅读数: 3

未见花闻

关注

还未添加个人签名 2021.11.15 加入

还未添加个人简介

发布

暂无评论

创作场景

数的奥秘之幂数与完全平方数

⛄️Part1.幂数⛄️

⭐️2 的幂⭐️

🔐题目详情

💡解题思路

🔑源代码

⭐️3 的幂⭐️

🔐题目详情

💡解题思路

🔑源代码

⭐️4 的幂⭐️

🔐题目详情

💡解题思路

🔑源代码

⛄️Part2.完全平方数⛄️

⭐️完全平方数⭐️

🔐题目详情

💡解题思路

🔑源代码

🌱总结🌱

未见花闻

评论