将一个长度最多为30位数字的十进制非负整数转换为二进制数输出 c语言 大数处理

Time Limit: 1000 ms
Memory Limit: 32768 mb

将一个长度最多为30位数字的十进制非负整数转换为二进制数输出

输入描述:

多组数据，每行为一个长度不超过30位的十进制非负整数。
（注意是10进制数字的个数可能有30个，而非30bits的整数）

输出描述:

每行输出对应的二进制数。

输入样例#:

0
1
3
8

输出样例#:

0
1
11
1000

分析：考察点是进制转换，难点是涉及到大数。

int类型在C语言中占4个字节，即32个二进制位。当表示正数时，最高位为符号位（符号位为0），最大的正数是 0111 1111 1111 1111 1111 1111 1111 1111 即2^31 -1 = 2147483647。当表示负数时，最高位为符号位（符号位为1），最小的负数是 1000 0000 0000 0000 0000 0000 0000 0000 而在计算机中是以补码的形式存储的，C语言规定 1000 0000 0000 0000 0000 0000 0000 0000 的补码为-2147483648。所以C语言中int的取值范围为：-2147483648~2147483647

但是本题中有30位长度，明显超过了int型变量的范围，因此可以尝试一下以下思路。

思路：

进制转换的精髓就在于除n取余，那么可以运用手动除法运算的方法，具体如下：

//以输入十进制123转换为2进制为例
//声明，result数组用于存放每一轮运算所得的余数，k用于存放每一次运算所得的余数，当此次运算为本轮运算的最后一位，就将k存入result数组。注意区分每一轮与每一次运算的区别
//第一趟：这里一位一位的运算，先从百位运算，然后运算十位，然后运算个位，与手动运算除法的顺序一致。
//第一轮运算输入123
//百位运算
1/2=0				//百位置0，说明这一轮运算百位就可以结束了，不需要第二轮
1%2=1。     //由于余数是1，所以有余数需要传给下一位，本例中也就是十位
k=1.       //将k置为1，意味着在下一次运算中要给下一次运算中加上此次运算多出来的数
//十位运算，由于百位上有余数1，因此十位上的2运算不能按照2运算，而是按照1x10+2=12运算
12/2=6		//这次运算的结果是6，说明十位上是6，不是0，所以这趟运算还不能结束，说明十位上的运算还需要第二轮，第三轮，甚至更多，直至十位上的数位0才算这趟运算结束
12%2=0		//此次运算可以整除，因此将k置为0
k=0				
//个位运算第一次，由于十位上的余数是0，因此个位的运算按照原本的数进行运算
3/2=1
3%2=1
k=1				//第一轮运算结束，将k的值也就是1存入result数组中，此时result数组的值为1
//第二趟
//第二趟第一轮运算：输入的是61
//十位运算
6/2=3
6%2=0
k=0
//个位运算
1/2=0
1%2=1
k=1。    //本轮结束，将k=1存入result，此时result为11
//第二趟第二轮，输入的是：30
//十位运算
3/2=1
3%2=1
k=1//k=1，因此各位运算的时候要将此余数纳入考虑范围
//个位运算，上一位运算的余数乘10加上本位上的数1x10+0=10
10/2=5
10%2=0
k=0。   //本轮运算结束，将k=0存入result数组，此时result为110
//第二趟第三轮，输入的是：15
//十位运算
1/2=0		//注意十位上的数除之后剩0了，意味着本趟运算结束
1%2=1
k=1
//个位运算，所以看到这里了，此次运算的数是多少呢
15/2=7
15%2=1
k=1。  //本轮运算结束，将开存入result，此时result为1101
//第三趟
//第三趟第一轮。输入7
//个位运算，其实也就剩个位了
7/2=3
7%2=1
k=1//将k存入result，即result为11011
//第三趟第二轮，输入3
3/2=1
3%2=1
k=1//将k存入result，即result为110111
//第三趟第三轮，输入1
1/2=0 //个位除之后为0，本趟结束
1%2=1
k=1//将k存入result，即result为1101111
//最后将result：1101111逆序输出为1111011，也就是123转换为2进制是1111011

代码如下：

#include<stdio.h>
#include<string.h>
void conservatemton(int m,char *s,int n){
	int len=strlen(s);
	int k,lastn=0;						//变量k用于存放每次运算所得的余数。lastn用于标记result数组的长度，放便后续的一系列操作。
	char result[32]={'0'};				//result数组是用来存放每一趟进制除n之后得到的余数，将数组逆序输出就是进制转换需要的结果，本行代码是将数组初始化。
	for (int i = 0; i < len; )
	{
		k=0;
		for (int j = i; j < len; ++j)	//除n取余，进制转换累问题的核心。
		{
			int t=(k*m+s[j]-'0')%n;
			s[j]=(k*m+s[j]-'0')/n+'0';
			k=t;
		}
		lastn++;
		result[lastn]=((char)(k+'0'));
		while(s[i]=='0')i++;			//当s[i]位置上的字符是0时，才标志一趟运算的结束。
	}
	for (int k = strlen(result); k >0; k--)
	{
		printf("%c",result[k]);
	}
	printf("\n");
}
int main(int argc, char const *argv[])
{
	char a[100];
	while(~scanf("%s",a)){
		conservatemton(10,a,2);
	}
	return 0;
}

这里在自己电脑可以运行，但是在oj上提示runtime error，这里是因为在函数内部每一次都开辟一个result数组，导致报此类错误，于是进行了改进，设置result数组为公共变量，这就避免了报错，但是注意同时要增加对于result数组的初始化工作。

#include<stdio.h>
#include<string.h>
char result[32];						//定义一个全局变量，为了避免了在运行过程功函数多次开辟同样空间，节省空间，也避免了栈溢出。
										//result数组是用来存放每一趟进制除n之后得到的余数，将数组逆序输出就是进制转换需要的结果。
void conservatemton(int m,char *s,int n){
	int len=strlen(s);
	int k,lastn=0;						//变量k用于存放每次运算所得的余数。lastn用于标记result数组的长度，放便后续的一系列操作。
	for (int i = 0; i <32; ++i)			//这一步是对将result数组置为空，也就是初始化，防止前面一趟的数据对后面一趟的数据产生干扰。
	{
		result[i]='\0';
	}
	for (int i = 0; i < len;)
	{
		k=0;
		for (int j = i; j < len; ++j)	//除n取余，进制转换问题的核心
		{
			int t=(k*m+s[j]-'0')%n;
			s[j]=(k*m+s[j]-'0')/n+'0';
			k=t;
		}
		result[lastn++]=((char)k+'0');
		while(s[i]=='0')i++;			//当s[i]位置上的字符是0时，才标志一趟运算的结束
	}
	for (int k = lastn-1; k >=0; --k)
	{
		printf("%c",result[k]);
	}
	printf("\n");
}
int main(int argc, char const *argv[])
{
	char a[32];
	while(~scanf("%s",a)){
		conservatemton(10,a,2);
	}
	return 0;
}

这样就可以ac了。