C语言实现大数转二进制

本是古典何须时尚 2022-01-28 08:55 252阅读 0赞

基本思想是列竖式，每轮求出商和余数。  
例如：  
大数字符串是“1234”  
第一次 “1234” / 2 = 0617 … 0

在本文例子中，首先将大数最高位字符 '1' 转换成整数转换成整数 1   
    然后计算 1 / 2 = 0, 再把 0 转换成字符 '0' 放到缓存区中，这是得到商  
    的最高位。计算次高位 '2' 时，由于前一位 1 % 2 = 1，此时会有借位  
    发生，也就是 (1*10 + 2) / 2 = 6，作为商的次高位，剩下位的计算和前面的  
    一样。

第二次 “0617” / 2 = 0308 … 1  
第三次 “0308” / 2 = 0154 … 0  
第三次 “0154” / 2 = 0077 … 0  
第四次 “0077” / 2 = 0038 … 1  
第五次 “0038” / 2 = 0019 … 0  
第六次 “0019” / 2 = 0009 … 1  
第七次 “0009” / 2 = 0004 … 1  
第八次 “0004” / 2 = 0002 … 0  
第九次 “0002” / 2 = 0001 … 0  
第十次 “0001” / 2 = 0000 … 1  
到最后商为0是结束，余数倒过来输出即可得到对应的二进制数"10011010010",  
在具体实现的时候值得关注的问题是借位，判断结束的条件。

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<unistd.h>
    
    #define BIGNUMLEN 1024
    
    // reverse a string 
    void reverse(char *num)
    { 
    	int i, j, len;
    	len = strlen(num);
    	j = len - 1;
    	for (i = 0; i < len / 2; i++)
    	{ 
    		// exchange num[i] and num[j]
    		num[i] = num[i] ^ num[j];
    		num[j] = num[i] ^ num[j];
    		num[i] = num[i] ^ num[j];
    	}
    }
    
    /** * judge all characters of a string wether are all '0'. * num: a string consit of number characters. * return: true in 0 * false in 1 **/
    
    int isstr0(char *num)
    { 
    	int i, len;
    	len = strlen(num);
    	for (i = 0; i < len; i++)
    	{ 
    		if (num[i] != '0')
    			return 1;
    	}
    	return 0;
    }
    
    void BigNumToBin()
    { 
    	char big_num[BIGNUMLEN];
    	char quotient[BIGNUMLEN];
    	char result[BIGNUMLEN * 2]; 
    	char temp, n;
    	char remider;
    	int i, j, k;
    	long long flag = 1;
    	memset(big_num, 0, BIGNUMLEN);
    	printf("big num: ");
    	scanf("%s", quotient);
    	i = j = 0;
    	if (strlen(quotient) >= BIGNUMLEN)
    	{ 
    		printf("big num string too long. %d bits limited\n", BIGNUMLEN - 1);
    		exit(0);
    	}
    	k = 0;
    	do
    	{ 
    		n = 0;
    		j = 0;
    		strcpy(big_num, quotient);
    		for(i = 0; i < strlen(big_num) ; i ++)
    		{ 
    			if (big_num[i] < '0' || big_num[i] > '9')
    			{ 
    				printf("invalid character in big num string.\n");
    				exit(0);
    			}
    			if (big_num[i] == '1' && i != strlen(big_num) - 1 && n != 10)
    			{ 
    				n = 10;
    				quotient[j] = '0';
    				j++;
    				continue;
    			}
    			else
    			{ 
    				temp = big_num[i] - '0';
    				temp = n + temp;
    				quotient[j] = (temp / 2) + '0';
    				j++;
    				if ((temp & 1) == 1)
    					n = 10; 
    				else n = 0;
    			}
    		}
    		quotient[j] = '\0';	
    		result[k] = (temp & 1) + '0';
    		k ++;
    	} while (isstr0(quotient));
    	result[k] = '\0';
    	reverse(result);
    	printf("binary: %s\n", result);
    }
    
    int main()
    { 
    	BigNumToBin();
    	return 0;
    }