29. 进制转换

题目描述

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

输入描述:

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

输出描述:

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

示例1

输入

0
1
3
8

输出

0
1
11
1000

思路

大数需要用数组来存，数组的每一位存着十进制的每一位，难点在于怎么处理数组来等效于处理这个数，处理方法是：
从数组最低位开始，把每一位余 2 的值加到高一位，然后自己除以 2，
到数组最高位时，余 2 的值无法加到高一位了，便把这个值存到二进制数组，
反复执行这个步骤便直到数组全部为零便可得到二进制。

我通过一个例子来手动模拟一下就容易理解了。
假设输入的字符串是 1 2 3 4
把它转成数组则为 1 2 3 4
按照上述规则，第一趟下来则为 0 6 1 7，最高位余的是 0，存到二进制数组
第二趟下来为 0 3 0 8，最高位余的是 1， 存到二进制数组
...
一直做下去直到数组全为零，二进制数组里面存的便是对应的反过来的二进制

解法

#include <stdio.h>
#include <string.h>
#include <malloc.h>

void decToBin(char *str, int len) {    //十进制转二进制
    int devidend = 1;    //用来标记被除数是否为零了
    int k = 0;    //控制二进制数组的计数
    int tag = 0;    //控制二进制数组倒序输出
    int *res = (int *) malloc (sizeof(int) * len * 4);    //动态分配二进制数组，长度为十进制的四倍
    int *num = (int *) malloc (sizeof(int) * len);    //存字符串转成的十进制数组
    for (int i = 0; i < len * 4; i++)    //动态分配的是随机数，需要初始化二进制数组
        res[i] = 0;
    for (int i = 0; i < len; i++) {
        num[i] = str[i] - '0';
    }
    while (devidend) {    //被除数不为零则一直做下去
        devidend = 0;
        for (int i = 0; i < len; i++) {
            if (num[i] / 2)    //只要有一位不为零，则说明被除数不为零
                devidend = 1;
            if (i == len - 1)    //最后一位时取余放到二进制数组
                res[k++] = num[i] % 2;
            else     //不是最后一位时，取余乘上 10 加到高一位
                num[i + 1] += num[i] % 2 * 10;
            num[i] /= 2;
        }
    }
    for (int tag = 0, i = len * 4 - 1; i >= 0; i--) {    //倒序输出
        if (tag)    //最终判断标志一定要放在上面，不然会输出两次
            printf("%d", res[i]);
        if (res[i] && tag == 0) {
            printf("%d",res[i]);
            tag = 1;
        }  
    }
    printf("\n");
    free(res);
    free(num);
}

int main() {
    char str[31];
    while (~scanf("%s", &str)) 
        decToBin(str, strlen(str));
    return 0;
}