@[toc]

零、写在前面

  从本节开始，我们就要开始 「 学习算法 」 了，很多没有接触过算法的同学都会问，没有任何基础，能学算法吗？我的回答是：没有任何一个人是没有任何基础的，1 + 1 总会吧 ？如果 1 + 1 都不会，可能都看不懂这段话😂。所以不要质疑自己的能力，学了再说，「 剩下的交给时间 」。
  作为 「 零基础算法 」 的第一节，我会从从高中的 「 数学知识 」 开始着手讲。算法其实没有想象的那么高深，如果刚开始接触，最好能有一门语言作为基础，这里我推荐 C 语言，如果没有的话，我觉得问题也不大，一路学下去发现遇到问题以后，再去看相关语法，然后来回看，加深记忆。
  我的学习策略很简单 —— 题海策略。当然，这 100 题 如果都能够自己认认真真把代码写出来，那入门肯定是没问题了，至于后面的进阶就要看 「 个人的天赋 」 以及 「 后天的努力 」 了。

一、概念定义

  本文主要讲解 数学上 的 幂 和 对数 的概念，以及如何在程序中进行运用。

1、幂

  「 幂 」 是指数运算的结果。 $n^m$ 看作乘方的结果，叫做 $n$ 的 $m$ 次幂，也叫 $n$ 的 $m$ 次方。
  当 $m$ 为正整数时， $n^m$ 代表 $m$ 个 $n$ 相乘；
  当 $m$ 为小数时， $m$ 可以写成 $\frac a b$ (其中 $a$、 $b$ 为整数）， $n^m$ 可以表示成：

$$n^m = n^{\frac a b} = \sqrt[b]{n^a}$$

  在C语言中，我们可以利用函数pow(n,m)来计算 $n$ 的 $m$ 次幂。

2、对数

  「 对数 」 是对 幂 的逆运算。当 $n$ 的 $m$ 次方等于 $T$ ( $n > 0$，且 $n \neq1$) ，即 $T = n^m$，那么数 $m$ 叫做 “以 $n$ 为底 $T$ 的对数”，记作 $m = log_nT$。其中， $n$ 叫做对数的 「 底数 」， $T$ 叫做 「 真数 」。

  在C语言中，我们可以利用函数log2(T)来计算以 $2$ 为底 $T$ 的对数；log10(T)来计算以 $10$ 为底 $T$ 的对数。

3、换底公式

  「 换底公式 」 常用于对数运算中，如下：

$$log_ab = \frac {log_cb}{log_ca}$$

  它的含义就是将底数从 $a$ 换成了 $c$，证明比较简单，不再累述。所以在 C语言中，如果我们要求以 $a$ 为底 $b$ 的对数，只需要将底换成 $2$ 求解即可：log2(b) / log2(a)

二、题目描述

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

三、算法详解

  根据上文中对数的定义， $x$ 是以 4 为底 $n$ 的对数，也就是 $log_4n$，利用换底公式，我们可以把它换成以 2 为底的方便程序计算，即：$$log_4n = \frac {log_2n}{log_24}$$
  那么，我们可以求出 $log_4n$ 的整数部分 $x'$，如果 $4^{x'}$ 和 $n$ 相等，则说明 $n$ 是 4 的幂。这里需要注意，相等的判定是建立在浮点数之间的，两个浮点数的判等需要采用 如下方式：

$$fabs(a - b) < 0.0000001$$

  即当两个数的差的绝对小于某个精度才认为它们相等。

四、源码剖析

bool isPowerOfFour(int n){
    if(n == 0) {
        return false;                          // (1)
    }
    int x = (int)(log2(n) / log2(4) + 1e-8);   // (2)
    return fabs(n - pow(4, x)) < 1e-8;         // (3)
}

• $(1)$ $n=0$ 的情况特殊判定；
• $(2)$ 换底公式，并且加上一个精度，避免精度损失导致取整出错；
• $(3)$ 浮点数的相等判定；

五、推荐专栏

六、习题练习

请参考原文