题目
分析
显然，这是一个递归的题目！
我们看一个例子，并用图来直观地展示过程：
- \(137=2^7+2^3+2^0\)
- 其中的
7、3都需要进一步处理，因为它们大于2，可以继续“裂开”表示。 - \(7=2^2+2+2^0\)。这就不需要继续处理了，因为所有用来表达
7的数字都是2或者0。题目的终止条件就是如此。
flowchart TD
A["137"]-->C[2^7]
A-->D["2^3"]
A-->E["2^0"]
C-->F["2^2"]
C-->G["2^1"]
C-->H["2^0"]
D-->I["2^1"]
D-->J["2^0"]
特殊次幂的表示
从上述分析可以看出，对于\(2^2, 2^1(=2), 2^0\)，我们可以按照题目要求，直接输出。这也是递归的终止条件。
// 基本情况
if (n == 0)
return "0";
if (n == 1)
return "2(0)";
if (n == 2)
return "2";找出最高次幂
既然\(n\gt 2\)（不是基本情况），我们就要求出它的最高次幂。
// 找出最高位的幂次
int highestBit = 0;
int temp = n;
while (temp > 1)
{
temp >> = 1;
highestBit++;
}我们用>>来快速地除以2。
递归处理最高幂次
string exponent;
if (highestBit == 1)
{
exponent = "2"; // 2^1 简写为 2
}
else
{
exponent = "2(" + represent(highestBit) + ")";
}注意这里对最高幂次为1的特别处理，以及对更高的最高幂次的递归处理。
递归处理剩余部分
处理完最高幂次后，还要对剩余部分（\(n-2^{highestBit}\)）进行递归处理。
// 计算2^highestBit
int power = 1 << highestBit;
// 递归处理剩余部分
int remainder = n - power;
if (remainder == 0)
{
return exponent;
}
else
{
return exponent + "+" + represent(remainder);
}我们用左移（<<）快速计算2的幂次。同时，注意余数为0时的特别处理。
答案
思考
一道非常精巧的递归练习题！从分析入手，可以很快地得到核心代码。
输出部分是由字符串拼接完成的，所以要特别注意+以及括号对出现的位置。