7
\$\begingroup\$

This program converts a decimal number to a binary number. This is one of my first C programs and I am wondering if I have used the elements of this language properly. Suggestions for improvement are welcome.

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

void print_out_reversed(char string[])
{
    int index = strlen(string);

    while (string[index] != '\0')
        index--;

    for (int i = index; i >= 0; i--)
        putchar(string[i]);
    putchar('\n');
}

void print_decimal_number_binary(int number)
{
    if (number == 0)
    {
        printf("0\n");
        return;
    }

    char bits[sizeof(int) * 8 + 1] = {0};
    int index = 0;

    while (number > 0)
    {
        if (number % 2 == 0)
        {
            bits[index] = '0';
        }
        else
        {
            bits[index] = '1';
        }
        number = number / 2;
        index++;
    }

    print_out_reversed(bits);
}

int main()
{
    printf("enter number: ");
    int number;
    scanf("%i", &number);
    print_decimal_number_binary(number);
}
\$\endgroup\$
8
\$\begingroup\$

Terminology

It's important to be able to understand (and describe) what's actually going on. Your program

  1. converts from an integer decimal string representation to an integer using scanf. This integer is then represented as a binary number in the processor.
  2. converts from that integer back into a string representation, but rather than it being decimal, it's binary.

So yes - it technically converts from "decimal to binary", but really it's "decimal string to integer to binary string".

Use const

void print_out_reversed(char string[])

doesn't modify string, so write const char string[].

Simplify your strlen usage

This:

int index = strlen(string);

while (string[index] != '\0')
    index--;

for (int i = index; i >= 0; i--)
    putchar(string[i]);

can be

for (int i = strlen(string)-1; i >= 0; i--)
    putchar(string[i]);

It seems that you don't trust what strlen is doing, which is why you have that intermediate while loop. But that loop won't have any effect, because the null terminator will always be where strlen says it is.

Use math instead of if

This:

    if (number % 2 == 0)
    {
        bits[index] = '0';
    }
    else
    {
        bits[index] = '1';
    }

can be

bits[index] = '0' + (number & 1);

Use combined operation and assignment

This:

number = number / 2;

should be

number /= 2;

or, for speed (which the compiler will do for you anyway)

number >>= 1;
\$\endgroup\$
  • 2
    \$\begingroup\$ int number ... number /= 2; is not the same code as number >>= 1; The first is well defined. The 2nd number >>= 1;, when number < 0 the resulting value is implementation-defined. number /= 2; is preferred for unambiguity. Note: (number & 1) is incorrect code for the now rare ones' complement platforms. OP's code functions correctly on all - even if it is ponderous. \$\endgroup\$ – chux Jan 6 at 22:32
3
\$\begingroup\$
#include <stdio.h>

void get_bits(unsigned long long* num, char * out, int bytes);

int main(void)
{
    long long x = 0;

    printf("Enter a number: ");
    scanf("%lli", &x);

    char bits[sizeof(unsigned long long)+1] = {0};
    get_bits(&x, bits, 4);

    printf("%d in binary %s\n", x, bits);

    return 0;
}

//assumes char array of length 1 greater than 
//number of bits
//EDIT: VERSION WITHOUT MEMCPY AS REMINDED BY @REINDERIEN
//REMOVED aliasing issue
void get_bits(unsigned long long * num, char *out, int bytes)
{
    unsigned long long filter = 0x8000000000000000;
   // unsigned long long *temp = num;

    if(bytes <= 0) return;
    if(bytes > 8) bytes = 8;

    filter = filter >> (8*(sizeof(unsigned long long)-bytes));
    //memcpy(&temp, num, bytes);
    int bits = 8*bytes;
    for(int i=0;i<bits;i++) {
        //if(filter & temp)
        //if((filter >> i) & *temp)
        if((filter >> i) & *num)
            out[i] = '1';
        else
            out[i] = '0';

        //temp = temp << 1;
    }
    out[bits] = '\0';
}

EDIT

Void* removed

Improvements

The posted code requires several loops, divisions, and modulus calculations. While it does solve the problem of representing an integer in binary, the utility may be limited by additional clock cycles.

The code may be optimized and extended to use with other integer representations, including char, short, or long long (or long depending on the size of long).

One drawback of the posted code is the need to reverse bits. Utilizing a mask to filter which bits are set in the number is more efficient.

Alternative Solution

The function get_bits will accept any integer representation.

It will "return," really populate, a character array with up to a 64-bit bit representation of the number.

It NO LONGER relies on memcpy from string.h.

Inputs for get_bits

unsigned long long* *num : a pointer to the memory address of the number to be represented in binary

char *out : the address of a character array to store the bit representation.
NOTE: This should be of length 1 longer than the number of bits to be represented

int bytes : number of bytes containing the number to represent in binary

Implementation

Based on the size of the data type of the number to be represented, a mask is established with the highest bit set. This is the variable, filter, of type unsigned long long contained in 64-bits. The input number passed as an unsigned long long*. Using bit shifting, the filter is shifted to the right to align it with the highest bit of the number.

Ex. In hexadecimal, a 16-bit filter would be 0x8000, which in binary is 100000000000000.

Only a single for loop is performed to populate the output string. In each iteration of the loop, a bit-wise AND is performed with filter and *temp. The result of this expression is either 0 or non-zero. The result is 0 only, when the highest order bit of temp is 0. The position in the output string is set to 1 if non-zero or 0 otherwise.

At the end of each iteration the filter is shifted incrementally by 1 more bit to the right.

Ex. In binary, if temp is 1010, then temp << 1 is 0100. (a suitable filter would be 1000 in binary).

\$\endgroup\$
  • \$\begingroup\$ Why would you make bits a 64-character string if you're only scanning a 32-bit integer? \$\endgroup\$ – Reinderien Jan 5 at 21:09
  • \$\begingroup\$ "One drawback of the posted code is the need to reverse bits. Utilizing a mask to filter which bits are set in the number is more efficient." You think so? Have you measured it? There's a third solution that uses your void* method, but can process input of an unlimited length (not restricted to 64 bits). Populating something in reverse is not slow. \$\endgroup\$ – Reinderien Jan 5 at 22:37
  • \$\begingroup\$ Read through your own solution again. You aren't using one loop; you have a memcpy that isn't necessary. \$\endgroup\$ – Reinderien Jan 5 at 22:40
  • 2
    \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$ – Reinderien Jan 6 at 0:13
  • \$\begingroup\$ Code assumes 8/byte. Reasonable, yet code could use CHAR_BIT instead of the magic number 8. \$\endgroup\$ – chux Jan 6 at 23:14
3
\$\begingroup\$

if I have used the elements of this language properly. Suggestions for improvement are welcome.

  • Good use of sizeof(int) to form a right size buffer rather than assuming some magic number.

Improvements ideas

Negative numbers

Code only prints a '\n' (and no visible text) when the int is negative.

Unnecessary code

The special test for 0 can be deleted ...

if (number == 0) {
    printf("0\n");
    return;
}

... by using a following

do  {
  ...
} while (number > 0);

instead of

while (number > 0) {
  ...
}

Assumed char size

Code assumes 8 bits/char with sizeof(int) * 8. This is very common yet not specified in C. Instead use CHAR_BIT for maximum portability.

#include <limits.h>

// char bits[sizeof(int) * 8 + 1] = {0};
char bits[sizeof(int) * CHAR_BIT + 1] = {0};

Simplified code

To well print negative numbers takes a little work to properly handle all negative values including INT_MIN.

Remember that -number is undefined behavior (UB) when number == INT_MIN.

Simplified code that forms the string right-to-left to skip the reverse step.

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

void print_decimal_number_binary_alt(int number) {
  int n = number;
  char bits[sizeof(int) * CHAR_BIT + 2];  // + 2 for '-' and '\0';

  char *s = &bits[sizeof bits - 1];  // Point to last array element;
  *s = '\0';

  do {
    s--;
    *s = '0' + (n % 2 != 0);
    n /= 2;
  } while (n);

  if (number < 0) {
    *(--s) = '-';
  }

  puts(s);
}

Sample

int main(void) {
  print_decimal_number_binary_alt(0);
  print_decimal_number_binary_alt(1);
  print_decimal_number_binary_alt(-1);
  print_decimal_number_binary_alt(42);
  print_decimal_number_binary_alt(INT_MAX);
  print_decimal_number_binary_alt(INT_MIN);
}

Output

0
1
-1
101010
1111111111111111111111111111111
-10000000000000000000000000000000
\$\endgroup\$
  • \$\begingroup\$ This will work fine but some cache memory guru will probably whine. It might actually be faster to loop from MSB and downwards in search of the first 1, then write to the array from index 0 to n. As a bonus, the code gets far less cryptic. \$\endgroup\$ – Lundin Jan 7 at 16:12
  • \$\begingroup\$ @Lundin Such sub-optimizations are selectively better or worse. This code does less work for small values, unlike your suggestion. What part do you find cryptic? Without UB, it does show it handles the entire int range. \$\endgroup\$ – chux Jan 7 at 18:01
  • \$\begingroup\$ A line such as *(--s) = '0' + (n % 2 != 0); is not easy to digest even for veterans. Down-counting iterators in general make the code harder to read. \$\endgroup\$ – Lundin Jan 8 at 7:26
  • \$\begingroup\$ @Lundin Curious: How would you code *(--s) = '0' + (n % 2 != 0); to achieve similar functionality? \$\endgroup\$ – chux Jan 8 at 15:03
  • \$\begingroup\$ To begin with, separate iteration from assignment. Then I would prefer something like (n & 1) ? '1' : '0', given that this doesn't result in more branches in the machine code. And overall, I think the method I cooked up in a separate answer will have superior performance. Though it doesn't use the definition of "signed binary" as you do here, but assumes that there's raw data that may or may not be represented as signed though 2's complement. \$\endgroup\$ – Lundin Jan 8 at 15:10
1
\$\begingroup\$

I'm adding another answer in a different direction from my previous one, both to show the OP some alternative techniques, and to illustrate an adaptation of @RJM's method.

Here's the code; it's quite simple:

#include <stdint.h>
#include <stdio.h>

static void printBinary(const uint8_t *restrict num, int bytes) {
    for (int p = bytes - 1; p >= 0; p--) {
        uint8_t x = num[p];
        for (int i = 0; i < 8; i++) {
            putchar('0' | (x >> 7));
            x <<= 1;
        }
    }
}

int main() {
    int64_t x;
    for (;;) {
        puts("Enter an integer: ");
        if (scanf("%lld", &x) == 1)
            break;
        while (getchar() != '\n');
    }

    printBinary((uint8_t*)&x, sizeof(x));
    putchar('\n');

    return 0;
}

Things to observe as compared to the OP's code (and RJM's code):

  • There are no calls to malloc or memcpy.
  • The result is not stored in memory; it's output directly to stdout.
  • The input integer has a primitive form of validation. The program will loop until scanf succeeds.
  • The input integer supports 64 bits instead of 32.
  • The output routine supports integers of any length, with the assumption that the integer is little-endian.
  • The bit sequence reversal is done directly in the decoding loop, rather than as a separate step.
  • There is no need for a "filter" (mask) variable.
  • The main loop does not need an if.

A brief word on computers

This code assumes a few things that are true in the vast (vast) majority of cases:

  • The processor is little-endian
  • There are 8 bits per byte
  • The caller cares about the "real" binary representation of data in the processor, rather than the "logical" binary translation of variables

The last point applies to both signed and floating-point data. This code does not care to write "-10", because that's not how the processor stores the data. This code will show either one's-complement (never seen these days) or two's-complement (always seen these days) machine representations of the data.

Similarly, this code does not show "-0.5" as "-0.1" in binary. To do so would make the code more complicated.

A brief word on restrict

For the dirty details, do some reading here.

restrict is a promise that no aliasing is done; i.e. that this pointer is the only way to access the data it points to, to enable some optimizations that wouldn't otherwise be possible. In the context of this program, if it's self-contained, the keyword won't have any effect. restrict enables some optimizations that would make it invalid for other code to modify the same data. Even in a context where there is only one pointer argument to the function, restrict has meaning. A multi-threaded program could alias the data, or (though not the case here) this function could call out to another function that already holds an alias. These aliases and restrict cannot coexist.

I'm happy to explain any aspect of this approach for the purposes of education.

\$\endgroup\$
  • \$\begingroup\$ Cool. Would that '0' | (x >> 7) be encoded as a '1'? \$\endgroup\$ – RJM Jan 6 at 1:21
  • \$\begingroup\$ @RJM Yep! Assuming that the MSB is 1. \$\endgroup\$ – Reinderien Jan 6 at 1:21
  • 1
    \$\begingroup\$ Thanks. Good discussion. Nice to meet you. \$\endgroup\$ – RJM Jan 6 at 1:24
  • \$\begingroup\$ Note this code prints out -2 decimal as a positive binary "1111111111111111111111111111111111111111111111111111111111111110\n". A reasonable expectation for a negative value in binary is "-10\n". \$\endgroup\$ – chux Jan 6 at 23:10
  • \$\begingroup\$ Code requires 8/byte. Reasonable, yet code could use unsigned char and CHAR_BIT to remove requiring the optional type uint8_t and `the magic number 8. \$\endgroup\$ – chux Jan 6 at 23:12
1
\$\begingroup\$

A decent compromise between readability and execution speed is this:

#include <stdint.h>
#include <string.h>

char* i32tostr (int32_t n, char str[32+1])
{
  const char NIBBLE_LOOKUP[16][4] = 
  {
    "0000", "0001", "0010", "0011",
    "0100", "0101", "0110", "0111",
    "1000", "1001", "1010", "1011",
    "1100", "1101", "1110", "1111",
  };

  char* ptr = str;
  for(uint32_t bit=32; bit>0; bit-=4)
  {
    uint32_t shift = bit - 4;
    uint32_t mask = 0xFu << shift;
    size_t index = (n & mask) >> shift;
    memcpy(ptr, NIBBLE_LOOKUP[index], 4); 
    ptr+=4;
  }
  *ptr = '\0';

  return str;
}

This reads the number 4 bits (a nibble) at a time from MSB to LSB. It masks out a nibble, then does a table look-up to get the pre-calculated string.

As it happens, a 4 byte string can be copied in a single instruction on 32 bit computers. Note the intentional subtle detail: const char NIBBLE_LOOKUP[16][4] instead of const char* NIBBLE_LOOKUP[16]. This means that the null terminator in the string literals is not stored and we can't use strcpy. Instead we use the significantly faster memcpy.

The local variables in the for loop are there for readability and don't affect performance. I could as well have written it as

for(uint32_t shift=28; shift>0; shift-=4)
{
  memcpy(ptr, NIBBLE_LOOKUP[(n & 0xFu<<shift) >> shift], 4); 
  ptr+=4;
}

But that's much harder to read and yields exactly the same machine code anyway.

In terms of execution speed, this should be much faster than parsing bit by bit and building up a string that way. The x86 disassembly looks pretty good; branch-free and cache-friendly: https://godbolt.org/z/DgJcVC.


Complete example:

#include <stdint.h>
#include <string.h>

char* i32tostr (int32_t n, char str[32+1])
{
  const char NIBBLE_LOOKUP[16][4] = 
  {
    "0000", "0001", "0010", "0011",
    "0100", "0101", "0110", "0111",
    "1000", "1001", "1010", "1011",
    "1100", "1101", "1110", "1111",
  };

  char* ptr = str;
  for(uint32_t bit=32; bit>0; bit-=4)
  {
    uint32_t shift = bit - 4;
    uint32_t mask = 0xFu << shift;
    size_t index = (n & mask) >> shift;
    memcpy(ptr, NIBBLE_LOOKUP[index], 4); 
    ptr+=4;
  }
  *ptr = '\0';

  return str;
}

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

int main (void)
{
  char str[32+1];

  puts(i32tostr(0,str));
  puts(i32tostr(1,str));
  puts(i32tostr(-1,str));
  puts(i32tostr(INT_MIN,str));
  puts(i32tostr(INT_MAX,str));
}

Output:

00000000000000000000000000000000
00000000000000000000000000000001
11111111111111111111111111111111
10000000000000000000000000000000
01111111111111111111111111111111
\$\endgroup\$
  • 1
    \$\begingroup\$ OP's goal involves int. Many attributes here focus on a 32-bit int. Not that that is bad, but not highly portable. In 2019 int is often 16-bit on many embedded processors and sometimes 64-bit on graphic ones. With that in mind, 0xFu << shift should be more like (uint32_t)0xFu << shift to insure correct operation a 16-bit machine. Code uses uint32_t for bit and shift. Instead, code could well use unsigned here as forcing a type width could be counter productive. It wound be interesting how this code would be as char* itostr (int n, char str[]) without assuming 32-bit int. \$\endgroup\$ – chux Jan 8 at 15:30
  • \$\begingroup\$ @chux You could use INT32_C(0xF) if you prefer. But this version isn't really feasible on small microcontrollers, as 32 bit copies will be heavy lifting there, and they won't have cache memory nor branch prediction. This code is intended for modern mainstream CPUs such as x86, ARM or PowerPC. Also, using smaller legacy architectures for new system design in the year 2019 is simply bad engineering in the vast majority of cases. \$\endgroup\$ – Lundin Jan 8 at 15:55
  • \$\begingroup\$ Agree with most aside from implying designing for 16-bit int/unsigned is bad as such processors are made in the 100s of millions per year these days. \$\endgroup\$ – chux Jan 8 at 15:59
  • \$\begingroup\$ @chux Yeah but that's mostly because of the combination of skilled marketeers and incompetent engineers. For example, people still believe that 8-bitters are easy to use, because of some 20+ year old market hype. While the truth is that it's a pain to write C code for such legacy cores. I've been pretty much exclusively been coding for small, cramped, exotic MCU systems over the past 15 years. Nowadays, just use Cortex M, use uint32_t and relax. Hidden crappiness not included. \$\endgroup\$ – Lundin Jan 8 at 16:14

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.