659
作者：小傅哥
博客：https://bugstack.cn
源码：https://github.com/fuzhengwei/java-algorithms
一、前言
二、判断2次方数
1. 整除法
2. 二进制
3. 求对数
4. 位计算
三、单元测试
四、常见面试题
一、前言
每一个知识的索引都可能会牵扯出一片的内容
记得以前看到一个文章内容，说国外的小孩留一个很开放的作文题目，但如果想把这样一个作业写下来，则需要索引大量的资料才能完成。但在这个过程中其实会收获很多，也学会了如何学习。
其实像小傅哥去编写这样的《程序员数学》资料时，也会去横向和纵向的对比一些数学上的文章和内容，有的来自维基百科，有的来自于论文资料，现在还可以从 chatGPT 中探索。
另外还有一份斯坦福大学的课程资料，小傅哥把它转成 PDF 有需要的伙伴可以下载学习使用。《计算机课程资料 - 斯坦福大学 @肖恩·埃隆·安德森》https://github.com/fuzhengwei/java-algorithms
二、判断2次方数
如果说判断一个数字是否满足2的次方，首先我会想到二进制，因为二进制的每一位都是2的次方数字。那么判断一个数字是否为2的次方可以从二进制中的数字特性下手，比如我们可以做二进制数字的判断，也就是一个数字的二进制必须只有1位为1，其他位都为0，那么这个数字就是2次方的数字。
🤔那除此之外还有其他手段吗？我们接下来就分别实现下
1. 整除法
代码实现
public boolean isPowerOfTwo01(int number) {
if (number < 1) return false;
int dividedNumber = number;
while (dividedNumber != 1) {
if (dividedNumber % 2 != 0) {
return false;
}
dividedNumber = dividedNumber / 2;
}
return true;
}
- 循环数字除以2的结果与2求模计算看余数是否为0，只要有一次为0，那么就不是2的次方数。
2. 二进制
代码实现
public boolean isPowerOfTwo02(int number) {
if (number < 1) return false;
return (number & (number - 1)) == 0;
}
-
- 在斯坦福大学的计算资料中，有这么一条关于判断2的次方数的内容；
f = (v & (v - 1)) == 0;
-
- 错位进行 & 与运算，结果为0则是2次方数【过程如图】。此外这里我们过滤了小于的数字，如果不过滤则需要使用；
f = v && !(v & (v - 1));
3. 求对数
代码实现
public boolean isPowerOfTwo03(int number) {
if (number == 0)
return false;
// log8 = log2^3 / log2 = 3
double x = Math.log(number) / Math.log(2);
// 向上和向下取整的结果判断
return (int)(Math.ceil(x)) == (int)(Math.floor(x));
}
- 此方式为计算2为底数的对数，如果得到的数字向上和向下取整结果一致，那么则是2的次方。这里做一个简单的推到，加入 number = 8，那么 log8 = log2^3 也就是用 log2^3 与 log2 做对比。这样就能看出来一个结果3，这个3是一个整数数字，则这个 number 也就是2次方数。
4. 位计算
代码实现
public boolean isPowerOfTwo04(int number){
int cnt = 0;
while (number > 0) {
if ((number & 1) == 1) {
cnt++;
}
number = number >> 1;
}
return cnt == 1;
}
- 这个其实就是最开始说的，如果一个数字满足2次方，那么只要在二进制的转换中，它只有1位是1就可以了。
三、单元测试
@Test
public void test_IsPowerOfTwo(){
IsPowerOfTwo isPowerOfTwo = new IsPowerOfTwo();
System.out.println(isPowerOfTwo.isPowerOfTwo01(8));
System.out.println(isPowerOfTwo.isPowerOfTwo02(8));
System.out.println(isPowerOfTwo.isPowerOfTwo03(163));
System.out.println(isPowerOfTwo.isPowerOfTwo04(12));
}
@Test
public void test_math(){
System.out.println(Math.ceil(Math.log(8) / Math.log(2)));
System.out.println(Math.log(1));
System.out.println(Math.E);
System.out.println(Math.pow(Math.E, Math.log(2)));
}
- 在单元测试中除了验证4种判断2次方数的计算方式，也提供了关于log的计算，默认log是基于指数E的计算。读者也可以进行测试验证。a 的 x 次方 = N 那么 x = log(a)N
四、常见面试题
- 如何判断一个数字是2的次方数在Java中怎么计算log公式
- END -
阅读全文
