当前位置：网站首页>数的奥秘之幂数与完全平方数

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

2022-06-10 23:10:00 【InfoQ】

️Part1.幂数️

️2 的幂️

题目详情

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

，则认为 n 是 2 的幂次方。

示例：

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

提示：

的范围为整型

的范围。

解题思路

利用

的幂的二进制序列中只有一个

1

并且大于

0

的性质，将此题转换为求二进制中

1

的个数，如果为

1

个，则该数为

的幂。二进制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

。

为什么

的二进制序列只有一个

1

？

不妨设一个数的二进制序列为，其中

为

0

或

1

：

则所对应十进制数

如果一个数为

的幂，则

中有且只有一个数为

其他均为

。推广一下，对于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 = 27
输出：true
输入：n = 45
输出：false

提示：

的范围为整型

的范围。

解题思路

如果一个数是

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 = 16
输出：true
输入：n = 5
输出：false

提示：

的范围为整型

的范围。

解题思路

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

推导：由二项式定理：

其中最末项系数

，所以

。

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

其中最末项系数

。x为偶数时，该数既是2的幂也是4的幂，此时

，

得到

。x为奇数时，该数是2的幂但不是4的幂，此时

，

得到

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

1

，所以可以得出结论：

源代码

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：暴力遍历，注意溢出，不推荐。方法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;
 }
}