本人第一篇博客，刚学算法半年的蒟蒻，用于进一步学习交流。

分~界~线~~~

进制转换

题目描述：

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

输入：

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

输出：

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

样例输入：

985
211
1126

样例输出：

1111011001
11010011
10001100110

注：每段代码变量不一致，以最后Code为标准。

分析：

每组数据输入长度不超过30位的十进制非负数。

不是30bits！不是30bits！不是30bits！

按照大数的一般操作，我们可以先用字符数组存储后，再进一步用整型数组存储，以便后续转为二进制。

char str[35];
int num[35];
for(int len=0;str[len];++len){
    num[len]=str[len]-'0';
}

进制转换，从十进制 -> x 进制，一般操作（应该没有其他办法了吧_小声_）是将十进制数 n 对 x 取模结果存入ans数组内（ 我是用ans数组存放转换成的二进制答案的 ），然后通过 n /= x 更新 n 的值。

int i=0;
int n,x;
int ans[MAXN];

do{
    ans[i++] = n % x;
    n /= x;
}while(n);

问题：

如果是普通整型范围内的非负整数是能直接进行运算的（或者用python，手动滑稽），本题数据均是超过30位的非负整数，就需要用到大数除以及取模操作。开始时，我能想到的只有暴力。显然，暴力不能解决问题。于是我就..打开了万能的百度......

本题特别的由十进制转二进制。在转二进制时，如何判断当前数值取模结果，主要在于当前十进制数末位奇偶状态，奇数为1，偶数为0。

int len = strlen(str);
ans = num[len-1]%2;

取模后，需要用当前数除进制数 ”2“得新数 ，按照除法运算的规则，可以明显发现，被除数当前位为奇时，借给下一位的值为10，反之为0。可以用和大整数加法类似的变量 x 来存储借位值。

int i,tmp,l=0,x=0;
for(i=l;i<len;++i){
    tmp=num[i];
    num[i]=(num[i]+x)/2;
    if(tmp&1)x=10;
    else x=0;
}
if(num[l]==0)++l;

我是选择在原值上进行修改，用 ' l ' 来记录十进制数最高位的位置，除数小于10，因此每次最高位的位数最多向右移一位，即若当前最高位的数值为0，就说明最高位已经向后移动一位。

Code：

代码如下，注释有空再加...

#include<iostream>
#include<cstdio>

using namespace std;

char str[35];
int num[35];

int ans[1005];

int main(){
    
    int i,j;
    
    int len=0,tmp;
    int x,l;
    
    while(scanf("%s",str)!=EOF){
        for(len=0;str[len];++len){
            num[len]=str[len]-'0';
        }
        j=0;
        l=0;
        while(l<len){
            ans[j++]=num[len-1]%2;
            x=0;
            for(i=l;i<len;++i){
                tmp=num[i];
                num[i]=(num[i]+x)/2;
                if(tmp&1)x=10;
                else x=0;
            }
            if(num[l]==0)++l;
        }
        for(i=j-1;i>=0;--i){
            printf("%d",ans[i]);
        }
        printf("\n");
        
    }
    
    return 0;
}

收获：

在做大整数进制转换的时候，遇到二进制可以特殊对待。相似的是，有些问题也是如此。

十进制转二进制，末尾奇偶确定取模结果，当前位奇偶确定借位值大小。