正如你所读到的,我创建了一个十进制到二进制的程序,它运行良好,但它无法处理等于 100,000,000 的用户输入。我的解决方案是按原样打印每个字符,但我不知道要使用的适当循环是什么,而且我对数学也不是那么好,所以我不清楚要使用的主要公式。不允许使用数组。任何建议不胜感激。谢谢。
#include <stdio.h>
unsigned long long int input,inp,rem=0,ans=0,place_value=1,ans;
int main()
{
printf("nYou have chosen Decimal to Binary and Octal Conversion!n");
printf("Enter a decimal number:n");
scanf("%llu", &input);
inp=input;
while(input){
rem=input%2;
input=input/2;
ans=ans+(rem*place_value);
place_value=place_value*10;
}
printf("%llu in Decimal is %llu in Binary Form.n", inp,ans);
return 0;
}
编辑:我已经阅读了您的所有答案,并且已尽力理解它们。我能够理解大部分内容,但提到的一些术语或课程需要我更多时间来学习。我已经提交了我的输出,但没有解决 100,000,000 问题,但我打算利用我现在拥有的知识来创建更好的输出。我试着问我的一个朋友,他告诉我他可以使用方法2来做到这一点:https://www.wikihow.com/Convert-from-Decimal-to-Binary。也许我的导师只是想教我们如何充分利用控制结构和数据类型,这就是为什么有这么多限制的原因。谢谢大家的时间,上帝保佑。
因此,正如注释所解释的那样,十进制数 100000000 具有 27 位二进制表示101111101011110000100000000
。 因此,我们可以毫无问题地将其存储在 32 位 int 中。 但是,如果我们尝试存储十进制数101111101011110000100000000,它恰好看起来像一个二进制数,那么,这将需要87位,所以它甚至不适合64位long long
整数。
这个问题中的代码确实尝试将其结果计算为十进制数,ans
,恰好看起来像一个二进制数。 因此,此代码不适用于大于 1048575 的数字(假设 64 位unsigned long long int
)。
这就是为什么"十进制到二进制"转换(或者就此而言,转换为任何基数)通常不应该对整数的结果变量进行的原因之一。 通常,这种转换的结果 - 到任何基 - 应该对字符串的结果变量完成,或者应该立即打印出来。 (这里的寓意是,只有当一个数字被打印出来供人类阅读时,基数才重要,这意味着一个字符串和/或打印成stdout
的东西。
然而,在 C 中,字符串当然是一个数组。 因此,要求某人在不使用数组的情况下进行基本转换是一种反常的、毫无意义的练习。
如果立即打印出数字,则不必将它们存储在数组中。 但是标准算法 - 重复除以2(或任何基数)以相反的顺序生成数字,从最不重要到最重要,最终从右到左,这是打印出来的错误顺序。 传统的数字转换代码通常将计算出的数字存储到数组中,然后反转数组 - 但如果禁止使用数组,这种策略(再次毫无意义地)被我们拒绝。
另一种以其他顺序获取数字的方法是使用递归算法,正如@chux在他的答案中所证明的那样。
但只是为了以我自己的方式反常,我将展示另一种方法。
尽管这通常是一个可怕的想法,但将数字构造成一个整数,以 10 为基数,但看起来像是以 2 为基数,至少是一种存储东西的方法,并以正确的顺序用数字返回答案。 唯一的问题是,正如我们所看到的,这个数字可能会变得大得离谱,特别是对于以 2 为基数。 (另一个问题,在这里并不重要,是这种方法不适用于大于 10 的基数,因为显然没有办法构造一个恰好看起来像是基数 16 的十进制数。
问题是,我们如何表示可能高达 87 位的整数? 我的回答是,我们可以使用所谓的"多重精度算术"。 例如,如果我们使用一对64 位unsigned long long int
变量,理论上我们可以表示大小高达 128 位的数字,或者340282366920938463463374607431768211455!
多精度算术是一个高级但引人入胜且具有启发性的话题。 通常它也使用数组,但是如果我们把自己限制在大数的两"半",并进行某些其他简化,我们可以非常简单地做到这一点,并实现一些足够强大的东西来解决问题中的问题。
因此,重复一遍,我们将一个 128 位数字表示为"高半部分"和"低半部分"。 实际上,为了使事情更简单,它实际上不会是一个128位的数字。 为了更简单起见,"高半部分"将是 36 位十进制数的前 18 位数字,而"低半部分"将是其他 18 位数字。 这将只相当于我们大约 120 位,但对于我们的目的来说仍然足够了。
那么我们如何对表示为"高"和"低"两半的 36 位数字进行算术呢? 实际上,它最终或多或少与我们学习如何对表示为数字的数字进行纸笔算术的方式相同。
如果我有这些"大"数字之一,在它的两半中:
high1 low1
如果我有第二个,也是两半:
high2 low2
如果我想计算总和
high1 low1
+ high2 low2
-----------
high3 low3
我这样做的方法是将low1
和low2
相加,以获得总和的低一半,low3
. 如果low3
小于 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 然后为了得到总和的高一半,high3
,我只需加上high1
加上high2
加上结转,如果有的话。
乘法更难,但事实证明,对于这个问题,我们永远不必计算完整的 36 位× 36 位乘积。 我们只需要将一个大数乘以一个小数,比如 2 或 10。 问题将如下所示:
high1 low1
× fac
-----------
high3 low3
所以,再次按照我们很久以前学到的纸笔算术规则,low3
将被low1
×fac
,high3
将被high1
×fac
,再次可能携带。
下一个问题是我们将如何携带这些低半和高半。 正如我所说,通常我们会使用数组,但我们不能在这里。 第二种选择可能是结构体,但你可能还没有了解这些,如果你疯狂的教练不让你使用数组,那么使用结构似乎也可能是越界的。 因此,我们将只编写一些接受高半和低半作为单独参数的函数。
这是我们的第一个函数,将两个 36 位数字相加。 其实很简单:
void long_add(unsigned long long int *hi, unsigned long long int *lo,
unsigned long long int addhi, unsigned long long int addlo)
{
*hi += addhi;
*lo += addlo;
}
我写它的方式,它不计算c = a + b
;它更像是a += b
。 也就是说,它需要addhi
和addlo
并将它们添加到hi
和lo
中,在此过程中修改hi
和lo
。 因此,hi
和lo
作为指针传入,以便可以修改指向的值。 高半部分是*hi
,我们加上要添加的数字的高半部分,addhi
. 然后我们对低半部分做同样的事情。 然后 - 哎呀 - 携带呢? 这并不难,但为了保持简单,我将把它推迟到一个单独的函数中。 所以我的最终long_add
函数如下所示:
void long_add(unsigned long long int *hi, unsigned long long int *lo,
unsigned long long int addhi, unsigned long long int addlo)
{
*hi += addhi;
*lo += addlo;
check_carry(hi, lo);
}
然后check_carry
也很简单。 它看起来像这样:
void check_carry(unsigned long long int *hi, unsigned long long int *lo)
{
if(*lo >= 1000000000000000000ULL) {
int carry = *lo / 1000000000000000000ULL;
*lo %= 1000000000000000000ULL;
*hi += carry;
}
}
同样,它接受指向lo
和hi
的指针,以便它可以修改它们。
低半部分是*lo
,它最多应该是一个 18 位数字,但如果它有 19 — 也就是说,如果它大于或等于 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 进位是*lo
超过 18 位数字的程度——它实际上只是前 19 位(以及任何更大)的数字。 如果你对这种数学不是很满意,那么取*lo
,然后除以那个大数字(字面意思是1和18个0)会给你前19位数字,或者使用%
会给你低18位数字,但这正是/
和%
所做的, 这是学习这一点的好方法。
无论如何,计算完进位后,我们将其添加到*hi
中,我们就完成了。
所以现在我们已经完成了加法,我们可以解决乘法问题了。 就我们的目的而言,这同样简单:
void long_multiply(unsigned long long int *hi, unsigned long long int *lo,
unsigned int fac)
{
*hi *= fac;
*lo *= fac;
check_carry(hi, lo);
}
它看起来与加法案例非常相似,但这正是我们的铅笔和纸分析所说的我们必须做的事情。 (同样,这是一个简化版本。 我们可以重用相同的check_carry
函数,这就是为什么我选择将其分解为一个单独的函数。
有了这些函数,我们现在可以重写二进制到十进制的程序,以便它可以处理这些更大的数字:
int main()
{
unsigned int inp, input;
unsigned long long int anslo = 0, anshi = 0;
unsigned long long int place_value_lo = 1, place_value_hi = 0;
printf("Enter a decimal number:n");
scanf("%u", &input);
inp = input;
while(input){
int rem = input % 2;
input = input / 2;
// ans=ans+(rem*place_value);
unsigned long long int tmplo = place_value_lo;
unsigned long long int tmphi = place_value_hi;
long_multiply(&tmphi, &tmplo, rem);
long_add(&anshi, &anslo, tmphi, tmplo);
// place_value=place_value*10;
long_multiply(&place_value_hi, &place_value_lo, 10);
}
printf("%u in Decimal is ", inp);
if(anshi == 0)
printf("%llu", anslo);
else printf("%llu%018llu", anshi, anslo);
printf(" in Binary Form.n");
}
这基本上与问题中的程序相同,但进行了以下更改:
ans
和place_value
变量必须大于 64 位,因此它们现在以_hi
和_lo
半的形式存在。- 我们调用我们的新函数来对大数进行加法和乘法。
- 我们需要一个
tmp
变量(实际上是tmp_hi
和tmp_lo
)来保存曾经是简单表达式ans = ans + (rem * place_value);
的中间结果。 - 用户的
input
变量不需要很大,所以我将其简化为普通unsigned int
。
将最终答案的两半(anshi
和anslo
)打印出来也有一些轻微的棘手问题。 但是如果你编译并运行这个程序,我想你会发现它现在适用于你可以给它的任何输入数字。 (理论上它应该适用于高达 68719476735 左右的输入,这比 32 位输入inp
的输入要大。
另外,对于那些仍然和我在一起的人,我必须添加一些免责声明。 我能够侥幸编写看起来如此小而简单的long_add
和long_multiply
函数的唯一原因是它们很简单,并且只适用于"简单"的问题,没有过度溢出。 我选择了 18 位数字作为"高"和"lo"两半的最大值,因为 64 位unsigned long long int
实际上可以容纳相当于 19 位的数字,这意味着我可以通过该> 1000000000000000000ULL
测试简单地检测到最多一位数的溢出。 如果任何中间结果溢出两位数,我就会遇到真正的麻烦。 但对于简单的加法,只有个位数的进位。 而且由于我只做过微小的乘法,所以我也可以作弊并假设(也就是说,侥幸逃脱)个位数的进位。
如果您尝试完全通用地进行多精度算术,对于乘法,您必须考虑其位数/位数是其输入数的两倍的部分乘积。 因此,您要么需要使用宽度为输入宽度两倍的输出类型,要么必须将输入分成两半("子半"),并单独使用它们,基本上为每个"数字"做一个小的 2×2 问题,具有不同的进位。
乘法的另一个问题是,"显而易见"的算法,即基于每个人在小学学习的纸笔技术的算法,对于真正的大问题来说可能是不可接受的低效,因为它基本上是O(N2)的位数。 以做这些事情为生的人有很多更复杂的技术,比如检测溢出和更有效地进行乘法。 然后,如果你想要一些真正的乐趣(或者一个真正的噩梦,充满了小学的糟糕闪回),那么会有很长的划分......
OP的代码在place_value*10
中存在溢出
避免没有数组和范围限制的一种方法是使用递归。
也许超出了OP现在的位置。
#include <stdio.h>
void print_lsbit(unsigned long long x) {
if (x > 1) {
print_lsbit(x / 2); // Print more significant digits first
}
putchar(x % 2 + '0'); // Print the LSBit
}
int main(void) {
printf("nYou have chosen Decimal to Binary and Octal Conversion!n");
printf("Enter a decimal number:n");
//scanf("%llu", &input);
unsigned long long input = 100000000;
printf("%llu in Decimal is ", input);
print_lsbit(input);
printf(" in Binary Form.n");
return 0;
}
输出
You have chosen Decimal to Binary and Octal Conversion!
Enter a decimal number:
100000000 in Decimal is 101111101011110000100000000 in Binary Form.