Program doesn't output anything using a dynamic array

Question

I just started with C and I am trying to create a program which takes a number and converts it to binary using this method (from indepth.dev):

To convert integer to binary, start with the integer in question and divide it by 2 keeping notice of the quotient and the remainder. Continue dividing the quotient by 2 until you get a quotient of zero. Then just write out the remainders in the reverse order. (...) Now, we simply need to write out the remainder in the reverse order —1100. So, 12 in decimal system is represented as 1100 in binary.

I am trying to make the array dynamic in size. Coming from Python this is a bit confusing, because in Python you can just append to a list.

Here is my code so far:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main() 
{
    int *ptr, n, i;
    ptr = (int*)malloc(1 * sizeof(int));
    printf("Enter a number to convert: ");
    scanf("%d", &n);
    for (i = 0; n>0; i++)
    {   
        ptr = realloc(ptr, i * sizeof(int));
        ptr[i] = n % 2;
        n = n/2;

    }

    for(i=i-1; i>= 0; i--)
    {
        printf("%d", ptr[i]);
    }
    free(ptr);
    return 0;
}

When I run the program and enter a number it doesn't output anything. If I do the same with a fixed array size it works. Why is this happening?

What is the size given to realloc at the first loop step? And the next? — Sami Kuhmonen
– Sami Kuhmonen, Commented Jan 14, 2020 at 21:26
In the for loop ptr will always have size i, however, you are writing to ptr[i] which is out of bounds. Also, the first time through the 2nd loop you read ptr[i] which is also out of bounds. — jmq
– jmq, Commented Jan 14, 2020 at 21:30
You don't need dynamic allocation here. Your input is an int, so just declare your array to have as many elements as the bits in an int (probably 32, maybe 64). — Lee Daniel Crocker
– Lee Daniel Crocker, Commented Jan 14, 2020 at 21:31
You're already including math (for no sensible reason it seems), why not take advantage of log10() to calculate the number of needed array elements and allocate it only once? — Marco Bonelli
– Marco Bonelli, Commented Jan 14, 2020 at 21:34

Marco Bonelli · Accepted Answer · 2020-01-15 14:09:56Z

The problem lies in these few lines:

for (i = 0; n>0; i++)
{   
    ptr = realloc(ptr, i * sizeof(int));
    ptr[i] = n % 2;
    n = n/2;
}

You are reallocating an array capable of holding i integers each time, however you end up writing at index i. An array holding i integers has indexes from 0 to i - 1, and you are therefore writing past the end of the array. This results in undefined behavior.

The easiest fix for this is to just start with i = 1 and write to ptr[i - 1]:

for (i = 1; n > 0; i++)
{   
    ptr = realloc(ptr, i * sizeof(int));
    ptr[i - 1] = n % 2;
    n = n/2;
}

A simpler approach would be to use a fixed size array. You already know that an int is 8*sizeof(int) bits long, so that's the maximum you'll need. Also, you probably don't need to work with signed integers since those can cause problems with negative values (therefore you can use unsigned).

EDIT: I am saying 8 * sizeof(int) because the sizeof operator returns the size of the type (in this case int) in bytes. A byte is 8 bits, so I multiply that by 8 to get the size in bits. I said 8 here, but using CHAR_BIT (from limits.h) would be better, because a "byte" in C could be expressed using more than 8 bits and in that case CHAR_BIT holds the right number of bits per byte. I'm not aware of any C implementation that has a value different than 8 for CHAR_BIT, but it's nonetheless the correct way to go. I updated the code below to use CHAR_BIT instead of 8.

#include <stdio.h>
#include <limits.h>
#define N_BITS CHAR_BIT * sizeof(unsigned)

int main(void) {
    unsigned digits[N_BITS] = {0}; // Start with an array filled with zeroes.
    unsigned n;
    int i;

    printf("Enter a number to convert: ");
    scanf("%u", &n);

    // Calculate binary digits.
    for (i = 0; n > 0; i++) {
        digits[i] = n % 2;
        n /= 2;
    }

    // Skip leading zeroes.
    while (digits[i] == 0)
        i--;

    // Print binary digits in reverse order.
    for(; i >= 0; i--)
        printf("%u", digits[i]);

    // Final newline.
    putchar('\n');

    return 0;
}

Bonus:

#include <stdio.h>

int main(void) {
    int i = 8 * sizeof(unsigned);
    unsigned n;

    printf("Enter a number to convert: ");
    scanf("%u", &n);

    while (i--)
        putchar('0' + ((n >> i) & 1));
    putchar('\n');

    return 0;
}

Thanks for your answer. Could you just explain why you define N_BITS as 8 * sizeof(unsigned)? What would be the max size for the input?
@Shadow I've edited my answer adding an explanation for that.

Vlad from Moscow · Accepted Answer · 2020-01-14 22:00:14Z

You allocated not enough memory. If sizeof( int ) is equal to 4 then the number of binary digits can be equal to 32 ( sizeof( int ) * CHAR_BIT).

And there is no need to use realloc.

Moreover this statement

ptr = realloc(ptr, i * sizeof(int));

allocates memory of zero size when i in the loop is equal to 0. You may not write to such a memory.

Also you should use an object of the type unsigned int.

Here is a demonstrative program.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int main(void) 
{
    unsigned int Base = 2;

    int *ptr = malloc( CHAR_BIT * sizeof( unsigned int ) );

    printf( "Enter a number to convert: " );

    unsigned int x = 0;

    scanf( "%u", &x );

    size_t n = 0;

    do
    {
        ptr[n++] = x % Base; 
    } while ( x /= Base );

    while ( n-- )
    {
        printf( "%u", ptr[n] );
    }
    putchar( '\n' );

    free( ptr );

    return 0;
}

Its output might look like

Enter a number to convert: 12
1100

If you want to use realloc then the code can look like

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int main(void) 
{
    unsigned int Base = 2;

    int *ptr = NULL;

    printf( "Enter a number to convert: " );

    unsigned int x = 0;

    scanf( "%u", &x );

    size_t n = 0;

    do
    {
        ptr = realloc( ptr, ( n + 1 ) * sizeof( unsigned int ) );
        ptr[n++] = x % Base; 
    } while ( x /= Base );

    while ( n-- )
    {
        printf( "%u", ptr[n] );
    }
    putchar( '\n' );

    free( ptr );

    return 0;
}

In general such a call

ptr = realloc( ptr, ( n + 1 ) * sizeof( unsigned int ) );

is unsafe because the function can return NULL. So in general you should use an intermediate variable like

unsigned int *tmp = realloc( ptr, ( n + 1 ) * sizeof( unsigned int ) );
if ( tmp ) ptr = tmp;

Collectives™ on Stack Overflow

Program doesn't output anything using a dynamic array

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related