正如您所讀到的，我創建了一個十進制轉二進制程式，它運行良好，但它無法處理等于 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;
}
uj5u.com熱心網友回復：
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.
uj5u.com熱心網友回復：
因此，正如評論所解釋的那樣，十進制數 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
and if I want to compute the sum
high1 low1
high2 low2
-----------
high3 low3
the way I do it is to add low1 and low2 to get the low half of the sum, low3. If low3 is less than 1000000000000000000 — that is, if it has 18 digits or less — I'm okay, but if it's bigger than that, I have a carry into the next column. And then to get the high half of the sum, high3, I just add high1 plus high2 plus the carry, if any.
Multiplication is harder, but it turns out for this problem we're never going to have to compute a full 36-digit × 36-digit product. We're only ever going to have to multiply one of our big numbers by a small number, like 2 or 10. The problem will look like this:
high1 low1
× fac
-----------
high3 low3
So, again by the rules of paper-and-pencil arithmetic we learned long ago, low3 is going to be low1 × fac, and high3 is going to be high1 × fac, again with a possible carry.
The next question is how we're going to carry these low and high halves around. As I said, normally we'd use an array, but we can't here. The second choice might be a struct, but you may not have learned about those yet, and if your crazy instructor won't let you use arrays, it seems that using structures might well be out of bounds, also. So we'll just write a few functions that accept high and low halves as separate arguments.
Here's our first function, to add two 36-digit numbers. It's actually pretty simple:
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;
}
The way I've written it, it doesn't compute c = a b; it's more like a = b. That is, it takes addhi and addlo and adds them in to hi and lo, modifying hi and lo in the process. So hi and lo are passed in as pointers, so that the pointed-to values can be modified. The high half is *hi, and we add in the high half of the number to be added in, addhi. And then we do the same thing with the low half. And then — whoops — what about the carry? That's not too hard, but to keep things nice and simple, I'm going to defer it to a separate function. So my final long_add function looks like:
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);
}
And then check_carry is simple, too. It looks like this:
void check_carry(unsigned long long int *hi, unsigned long long int *lo)
{
if(*lo >= 1000000000000000000ULL) {
int carry = *lo / 1000000000000000000ULL;
*lo %= 1000000000000000000ULL;
*hi = carry;
}
}
Again, it accepts pointers to lo and hi, so that it can modify them.
The low half is *lo, which is supposed to be at most an 18-bit number, but if it's got 19 — that is, if it's greater than or equal to 1000000000000000000, that means it has overflowed, and we have to do the carry thing. The carry is the extent by which *lo exceeds 18 digits — it's actually just the top 19th (and any greater) digit(s). If you're not super-comfortable with this kind of math, it may not be immediately obvious that taking *lo, and dividing it by that big number (it's literally 1 with eighteen 0's) will give you the top 19th digit, or that using % will give you the low 18 digits, but that's exactly what / and % do, and this is a good way to learn that.
In any case, having computed the carry, we add it in to *hi, and we're done.
So now we're done with addition, and we can tackle multiplication. For our purposes, it's just about as easy:
void long_multiply(unsigned long long int *hi, unsigned long long int *lo,
unsigned int fac)
{
*hi *= fac;
*lo *= fac;
check_carry(hi, lo);
}
It looks eerily similar to the addition case, but it's just what our pencil-and-paper analysis said we were going to have to do. (Again, this is a simplified version.) We can re-use the same check_carry function, and that's why I chose to break it out as a separate function.
With these functions in hand, we can now rewrite the binary-to-decimal program so that it will work with these even bigger numbers:
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("%llu8llu", anshi, anslo);
printf(" in Binary Form.\n");
}
This is basically the same program as in the question, with these changes:
- The
ansandplace_valuevariables have to be greater than 64 bits, so they now exist as_hiand_lohalves. - We're calling our new functions to do addition and multiplication on big numbers.
- We need a
tmpvariable (actuallytmp_hiandtmp_lo) to hold the intermediate result in what used to be the simple expressionans = ans (rem * place_value);. - There's no need for the user's
inputvariable to be big, so I've reduced it to a plainunsigned int.
There's also some mild trickiness involved in printing the two halves of the final answer, anshi and anslo, back out. But if you compile and run this program, I think you'll find it now works for any input numbers you can give it. (It should theoretically work for inputs up to 68719476735 or so, which is bigger than will fit in a 32-bit input inp.)
Also, for those still with me, I have to add a few disclaimers. The only reason I could get away with writing long_add and long_multiply functions that looked so small and simple was that they are simple, and work only for "easy" problems, without undue overflow. I chose 18 digits as the maximum for the "high" and "lo" halves because a 64-bit unsigned long long int can actually hold numbers up to the equivalent of 19 digits, and that means that I can detect overflow — of up to one digit — simply, with that > 1000000000000000000ULL test. If any intermediate result ever overflowed by two digits, I'd have been in real trouble. But for simple additions, there's only ever a single-digit carry. And since I'm only ever doing tiny multiplications, I could cheat and assume (that is, get away with) a single-digit carry there, too.
If you're trying to do multiprecision arithmetic in full generality, for multiplication you have to consider partial products that have up to twice as many digits/bits as their inputs. So you either need to use an output type that's twice as wide as the inputs, or you have to split the inputs into halves ("sub-halves"), and work with them individually, basically doing a little 2×2 problem, with various carries, for each "digit".
Another problem with multiplication is that the "obvious" algorithm, the one based on the pencil-and-paper technique everybody learned in elementary school, can be unacceptably inefficient for really big problems, since it's basically O(N2) in the number of digits. People who do this stuff for a living have lots of more-sophisticated techniques they've worked out, for things like detecting overflow and for doing multiplication more efficiently. And then if you want some real fun (or a real nightmare, full of bad flashbacks to elementary school), there's long division...
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/319238.html