今天在做蓝桥杯题目的时候看到一题十六进制转八进制的题目，题目如下：
问题描述
给定n个十六进制正整数，输出它们对应的八进制数。
输入格式
输入的第一行为一个正整数n （1<=n<=10）。
接下来n行，每行一个由0~9、大写字母A~F组成的字符串，表示要转换的十六进制正整数，每个十六进制数长度不超过100000。
输出格式
输出n行，每行为输入对应的八进制正整数。
注意
输入的十六进制数不会有前导0，比如012A。
输出的八进制数也不能有前导0。
样例输入
2
39
123ABC
样例输出
71
4435274
提示
先将十六进制数转换成某进制数，再由某进制数转换成八进制。
十六进制转化为八进制最直接想到的有两种方法：
1.将十六进制转换为十进制再转换为八进制
2.将十六进制转换为二进制再转换为八进制
分析：在第一种方法中用int类型来储存十进制数的话那么最大能处理80 000 000(H)也就是 2147483648 (D)，本题要求处理大数据，那么必须用数组储存。用第一种方法就涉及到了大整数的加法，模，除法。
第二种方法相对于第一种方法而言比较容易，只用定义一个字符数组就可以储存二进制数，每一个十六进制可以转换为4位2进制数，然后每3位二进制数可以转换为一个八进制数，在本题中输入的十六进制没有前导零，所以在十六进制最高的四位最小出现“0001”若最后三位相加为0那么就不输出即可。
以下是实现代码
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define N 100001
char str[N];
void prin(char *a,int n)
{
int i;
for(i=n-1;i>=0;i--){
printf("%d",a[i]);
}
putchar('
');
}
void change(int use)
{
int num=0;
char two[N*4];
int w[4]={1,2,4,8};
int i=0,j=0,cnt2=0,cnt8=0;
//totwo
while(use>=0){
num=isdigit(str[use])?str[use]-'0':str[use]-'A'+10;
use--;
for(i=0;i<4;i++){
two[cnt2++]=num&w[i];
}
}
//twoto
for(i=0;i<cnt2;){
for(num=0,j=0; i<cnt2&&j<3 ;j++){
if(two[i++]) num+=w[j];
}
two[cnt8++]=num;
}
if(!two[cnt8-1]) cnt8--;
//printf
for(i=cnt8-1;i>=0;i--)
{
printf("%d",two[i]);
}
putchar('
');
}
int main(void)
{
int n;
scanf("%d",&n);
if(n>=1&&n<=10){
while(n--){
scanf("%s",str);
change(strlen(str)-1);
}
}
return 0;
}
对于上述方法浪费的空间太大！我利用C语言对于底层的操作，位运算可以大大减少空间复杂度以及时间复杂度
实现如下
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define N 100001
char str[N];
int save=0;
void change(int use,int state)
{
int num;
if(use>=0){
if(state!=3){
num=isdigit(str[use])?str[use]-'0':str[use]-'A'+10;
num<<=state;
num|=save;
save=num>>3;
change(use-1,state+1);
printf("%d",num%8);
}else{
num=save;
save>>=3;
change(use,0);
printf("%d",num%8);
}
}else{
if(save){
printf("%d",save);
save=0;
}
}
}
int main(void)
{
int num;
scanf("%d",&num);
if(num>=1&&num<=10){
while(num--){
scanf("%s",str);
change(strlen(str)-1,0);
printf("
");
}
}
return 0;
}
内存使用之所以不降反升的原因是因为使用了递归
（作者水平有限，欢迎大家讨论批评）