面试题：不使用pow()函数优化指定C语言幂计算代码

题目要求 #

本题来自编程面试现场，核心约束为不允许调用pow()库函数优化给定C代码，代码需满足以下输入输出规则：

• 输入num=1时，输出8
• 输入num=2时，输出16
• 输入num=3时，输出32
• 输入num=4时，输出64
• 更大的输入值按上述规律对应输出结果

原有待优化代码 #

#include <stdio.h>
#include <stdlib.h> 

int main()
{
    int num,b;
    scanf("%d",&num);
    num=num+2;
    b=pow(2,num);
    printf("%d",b);
    return 0;
}

注：此前尝试自行编写通用pow()函数替换库函数调用的方案未获得面试官认可，需要找到符合考察点的最优优化方案。

优化思路 #

首先梳理输入输出规律：所有输出结果均为2的整数次幂，对应关系为输出值 = 2^(num + 2)。
面试官不认可自定义pow实现的核心原因是，本题场景固定为计算2的整数次幂，不需要实现通用幂计算逻辑：

1. 通用pow实现不管是迭代还是快速幂，都存在额外的计算开销，没有利用到2的幂的计算特性
2. 库函数pow本身是面向浮点数运算实现的，整数场景下调用存在浮点数转整数的精度误差风险
3. 对整数来说，左移n位的运算等价于乘以2^n，是O(1)时间复杂度的纯整数运算，完全适配本题场景，也是本题真正的考察点。

优化后代码 #

#include <stdio.h>

int main()
{
    int num, b;
    scanf("%d", &num);
    // 1左移(num+2)位 等价于计算2^(num+2)，无需任何幂函数实现
    b = 1 << (num + 2);
    printf("%d", b);
    return 0;
}

注意：实际工程中使用时需要确保num+2的结果不超过当前环境下int类型的位宽，避免移位溢出。

内容的提问来源于stack exchange，提问作者Karna Rai