Can anyone explain to me about this decimal to binary convertion program

Question

Can someone explain to me how the calculation works? what I don't understand is:

1. the getch(); function, what does that function does?

2. Can someone explain to me how the int decimal_binary(int n) operates mathematically?

#include<stdio.h>

int decimal_binary (int n);

void main()
{
    int n;
    printf("Enter decimal number: ");
    scanf("%d", &n);
    printf("\n%d", decimal_binary(n));
    getch();
}

int decimal_binary(int n)
{
    int rem, i = 1, binary = 0;
    while(n!=0)
    {
        rem = n % 2;
        n = n/2;
        binary = binary + rem*i;
        i = i*10;
    }
    return binary;
}

if for example the n = 10 and this is how i calculate it

Answer 1

I'm not going to explain the code in the question, because I fundamentally (and rather vehemently) disagree with its implementation.

When we say something like "convert a number to base 2", it's useful to understand that we are not really changing the number. All we're doing is changing the representation. An int variable in a computer program is just a number (although deep down inside it's already in binary). The base matters when we print the number out as a string of digit characters, and also when we read it from as a string of digit characters. So any sensible "convert to base 2" function should have as its output a string, not an int.

Now, when you want to convert a number to base 2, and in fact when you want to convert to base b, for any base "b", the basic idea is to repeatedly divide by b.

For example, if we wanted to determine the base-10 digits of a number, it's easy. Consider the number 12345. If we divide it by 10, we get 1234, with a remainder of 5. That remainder 5 is precisely the last digit of the number 12345. And the remaining digits are 1234. And then we can repeat the procedure, dividing 1234 by 10 to get 123 remainder 4, etc.

Before we go any further, I want you to study this base-10 example carefully. Make sure you understand that when we split 12345 up into 1234 and 5 by dividing it by 10, we did not just look at it with our eyes and pick off the last digit. The mathematical operation of "divide by 10, with remainder" really did do the splitting up for us, perfectly.

So if we want to determine the digits of a number using a base other than 10, all we have to do is repeatedly divide by that other base. Suppose we're trying to come up with the binary representation of eleven. If we divide eleven by 2, we get five, with a remainder of 1. So the last bit is going to be 1.

Next we have to work on five. If we divide five by 2, we get two, with a remainder of 1. So the next-to-last bit is going to be 1.

Next we have to work on two. If we divide two by 2, we get one, with a remainder of 0. So the next bit is going to be 0.

Next we have to work on one. If we divide one by 2, we get zero, with a remainder of 1. So the next bit is going to be 1.

And now we have nothing left to work with -- the last division has resulted in 0. The binary bits we've picked off were, in order, 1, 1, 0, and 1. But we picked off the last bit first. So rearranging into conventional left-to-right order, we have 1011, which is the correct binary representation of the number eleven.

So with the theory under our belt, let's look at some actual C code to do this. It's perfectly straightforward, except for one complication. Since the algorithm we're using always gives us the rightmost bit of the result first, we're going to have to do something special in order to end up with the bits in conventional left-to-right order in the final result.

I'm going to write the new code as function, sort of like your decimal_binary. This function will accept an integer, and return the binary representation of that integer as a string. Because strings are represented as arrays of characters in C, and because memory allocation for arrays can be an issue, I'm going to also have the function accept an empty array (passed by the caller) to build the return string in. And I'm also going to have the function accept a second integer giving the size of the array. That's important so that the function can make sure not to overflow the array.

If it's not clear from the explanation so far, here's what a call to the new function is going to look like:

#include <stdio.h>

char *integer_binary(int n, char *str, int sz);

int main()
{
    int n;
    char result[40];
    printf("Enter decimal number: ");
    scanf("%d", &n);
    char *str = integer_binary(n, result, 40);
    printf("%s\n", str);
}

As I said, the new function, integer_binary, is going to create its result as a string, so we have to declare an array, result, to hold that string. We're declaring it as size 40, which should be plenty to hold any 32-bit integer, with some left over.

The new function returns a string, so we're printing its return value using %s.

And here's the implementation of the integer_binary function. It's going to look a little scary at first, but bear with me. At its core, it's using the same algorithm as the original decimal_binary function in the question did, repeatedly dividing by 2 to pick off the bits of the binary number being generated. The differences have to do with constructing the result in a string instead of an int. (Also, it's not taking care of quite everything yet; we'll get to one or two more improvements later.)

char *integer_binary(int n, char *binary, int sz)
{
    int rem;
    int j = sz - 2;
    do {
        if(j < 0) return NULL;
        rem = n % 2;
        n = n / 2;
        binary[j] = '0' + rem;
        j--;
    } while(n != 0);

    binary[sz-1] = '\0';

    return &binary[j+1];
}

You can try that, and it will probably work for you right out of the box, but let's explain the possibly-confusing parts.

The new variable j keeps track of where in the array result we're going to place the next bit value we compute. And since the algorithm generates bits in right-to-left order, we're going to move j backwards through the array, so that we stuff new bits in starting at the end, and move to the left. That way, when we take the final string and print it out, we'll get the bits in the correct, left-to-right order.

But why does j start out as sz - 2? Partly because arrays in C are 0-based, partly to leave room for the null character '\0' that terminates arrays in C. Here's a picture that should make things clearer. This will be the situation after we've completely converted the number eleven:

          0   1   2          31  32  33  34  35  36  37  38  39
        +---+---+---+-- ~ --+---+---+---+---+---+---+---+---+---+
result: |   |   |   |  ...  |   |   |   |   | 1 | 0 | 1 | 1 |\0 |
        +---+---+---+-- ~ --+---+---+---+---+---+---+---+---+---+
          ^                               ^   ^           ^
          |                               |   |           |
        binary                          final return    initial
                                          j  value        j

The result array in the caller is declared as char result[40];, so it has 40 elements, from 0 to 39. And sz is passed in as 40. But if we want j to start out "at the right edge" of the array, we can't initialize j to sz, because the leftmost element is 39, not 40. And we can't initialize j as sz - 1, either, because we have to leave room for the terminating '\0'. That's why we initialize j to sz - 2, or 38.

The next possibly-confusing aspect of the integer_binary function is the line

binary[j] = '0' + rem;

Here, rem is either 0 or 1, the next bit of our binary conversion we've converted. But since we're creating a string representation of the binary number, we want to fill the binary result in with one of the characters '0' or '1'. But characters in C are represented by tiny integers, and you can do arithmetic on them. The constant '0' is the value of the character 0 in the machine's character set (typically 48 in ASCII). And the bottom line is that '0' + 1 turns into the character '1'. So '0' + rem turns into '0' if rem is 0, or '1' if rem is 1.

Next to talk about is the loop I used. The original decimal_binary function used while(n != 0) {...}, but I'm using do { ... } while(n != 0). What's the difference? It's precisely that the do/while loop always runs once, even if the controlling expression is false. And that's what we want here, so that the number 0 will be converted to the string "0", not the empty string "". (That wasn't an issue for integer_binary, because it returned the integer 0 in that case, but that was a side effect of its otherwise-poor choice of int as its return value.)

Next we have the line

binary[sz-1] = '\0';

We've touched on this already: it simply fills in the necessary null character which terminates the string.

Finally, there's the last line,

return &binary[j+1];

What's going on there? The integer_binary function is supposed to return a string, or in this case, a pointer to the first character of a null-terminated array of characters. Here we're returning a pointer (generated by the & operator) to the element binary[j+1] in the result array. We have to add one to j because we always subtract 1 from it in the loop, so it always indicates the next cell in the array where we'd store the next character. But we exited the loop because there was no next character to generate, so the last character we did generate was at j's previous value, which is j+1.

(This integer_binary function is therefore mildly unusual in one respect. The caller passes in an empty array, and the function builds its result string in the empty array, but the pointer it returns, which points to the constructed string, does not usually point to the beginning of the passed-in array. It will work fine as long as the caller uses the returned pointer, as expected. But it's unusual, and the caller would get confused if accidentally using its own original result array as if it would contain the result.)

One more thing: that line if(j < 0) return NULL; at the top of the loop is a double check that the caller gave us a big enough array for the result we're generating. If we run out of room for the digits we're generating, we can't generate a correct result, so we return a null pointer instead. (That's likely to cause problems in the caller unless explicitly checked for, but that's a story for another day.)

So integer_binary as discussed so far will work, although I'd like to make three improvements to address some remaining deficiencies:

1. The decimal_binary function as shown won't handle negative numbers correctly.

2. The way the decimal_binary function uses the j variable is a bit clumsy. (Evidence of the clumsiness is the fact that I had to expend so many words explaining the j = sz-2 and return &binary[j+1] parts.)

3. The decimal_binary functions as shown only handles, obviously, binary, but what I really want (although you didn't ask for it) is a function that can convert to any base.

So here's an improved version. Based on the integer_binary function we've already seen, there are just a few small steps to achieve the desired improvements. I'm calling the new function integer_base, because it converts to any base (well, any base up to 10, anyway). Here it is:

char *integer_base(int n, int base, char *result, int sz)
{
    int rem;
    int j = sz - 1;
    int negflag = 0;

    if(n < 0) {
        n = -n;
    negflag = 1;
    }

    result[j] = '\0';

    do {
        j--;
        if(j < 0) return NULL;
        rem = n % base;
        n = n / base;
        result[j] = '0' + rem;
    } while(n != 0);

    if(negflag) {
        j--;
        result[j] = '-';
    }

    return &result[j];
}

As mentioned, this is just like integer_binary, except:

• I've changed the way j is used. Before, it was always the index of the next element of the result array we were about to fill in. Now, it's always one to the right of the next element we're going to fill in. This is a less obvious choice, but it ends up being more convenient. Now, we initialize j to sz-1, not sz-2. Now, we do the decrement j-- before we fill in the next character of the result, not after. And now, we can return &binary[j], without having to remember to subtract 1 at that spot.

• I've moved the insertion of the terminating null character '\0' up to the top. Since we're building the whole string right-to-left, it makes sense to put the terminator in first.

• I've handled negative numbers, in a kind of brute-force but expedient way. If we receive a negative number, we turn it into a positive number (n = -n) and use our regular algorithm on it, but we set a flag negflag to remind us that we've done so and, when we're all done, we tack a '-' character onto the beginning of the string.

• Finally, and this is the biggie, the new function works in any base. It can create representations in base 2, or base 3, or base 5, or base 7, or any base up to 10. And what's really neat is how few modifications were required in order to achieve this. In fact, there were just two: In two places where I had been dividing by 2, now I'm dividing by base. That's it! This is the realization of something I said back at the very beginning of this too-long answer: "The basic idea is to repeatedly divide by b."

• (Actually, I lied: There was a fourth change, in that I renamed the result parameter from "binary" to "result".)

Although you might be thinking that this integer_base function looks pretty good, I have to admit that it still has at least three problems:

1. It won't work for bases greater than 10.

2. It can occasionally overflow its result buffer.

3. It has an obscure problem when trying to convert the largest negative number.

The reason it only works for bases up to 10 is the line

result[j] = '0' + rem;

This line only knows how to create ordinary digits in the result. For (say) base 16, it would also have to be able to create hexadecimal digits A - F. One quick but obfuscated way to achieve this is to replace that line with

result[j] = "0123456789ABCDEF"[rem];

This answer is too long already, so I'm not going to get into a side discussion on how this trick works.

The second problem is hiding in the lines I added to handle negative numbers:

if(negflag) {
    j--;
    result[j] = '-';
}

There's no check here that there's enough room in the result array for the minus sign. If the array was just barely big enough for the converted number without the minus sign, we'll hit this part of the code with j being 0, and we'll subtract 1 from it, and fill the minus sign in to result[-1], which of course doesn't exist.

Finally, on a two's complement machine, if you pass the most negative integer, INT_MIN, in to this function, it won't work. On a 16-bit 2's complement machine, the problem number is -32768. On a 32-bit machine, it's -2147483648. The problem is that +32768 can't be represented as a signed integer on a 16-bit machine, nor will +2147483648 fit in 32 signed bits. So a rewrite of some kind will be necessary in order to achieve a perfectly general function that can also handle INT_MIN.

Answer 2

getchar() stops your program in console. Maths behind function looks like this:

n=7:
7%2=1; //rem=1
7/2=3; //n=3
binary=1;
next loop
n=3:
3%2=1;
3/2=1; //n=1;
binary=11 //1 + 1* 10
final loop
n=1:
1%2=1;
1/2=0; //n=0;
binary=111 //11+1*100

Answer 3

In order to convert a decimal number to a binary number, there is a simple recursive algorithm to apply to that number (recursive = something that is repeated until something happen):

1. take that number and divide by 2
2. take the reminder
3. than repeat using as current number, the original number divided by 2 (take in account that this is a integer division, so 2,5 becomes 2) until that number is different to 0
4. take all the reminders and read from the last to the first, and that's the binary form of that number

What that function does is exactly this

1. take the number and divide it by 2
2. takes the reminder and add it in into the variable binary multiplied by and i that each time is multiplied by 10, in order to have the first reminder as the less important digit, and the last one as the most significant digit, that is the same of take all the reminders and read them from the last to the first
3. save as n the n/2
4. and than repeat it until the current number n is different to 0

Also getch() is sometimes used in Windows in order to hold the command prompt open, but is not that recommended