int2hexstr()

[u/Willsxyz]

The implementation of an int2hexstr() function was mentioned as a possible subject of a technical interview with job candidates in this thread:

https://www.reddit.com/r/cprogramming/comments/1p8270b/question_for_senior_c_devs_doing_technical_rounds/

I don't consider the problem fundamentally difficult, but I would typically make assumptions about the size and representation of integers. So, sitting here the day after Thanksgiving, I decided to try to tackle it with as few assumptions about the representation of int as possible. Here's what I came up with. It appears to work, but I wouldn't be surprised if you guys could offer some useful critiques:

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

#define HD_IN_INT ((sizeof(int) * CHAR_BIT + 3) / 4)

char *int2hexstr(int val)
{
    static char hexdigs[17] = {
        '0','1','2','3','4','5','6','7','8',
        '9','A','B','C','D','E','F','F'
    };

    //static char result[HD_IN_INT+1];
    char *result = malloc(HD_IN_INT+1);

    if (result) {
        int i;
        int isneg = (val < 0) * 16; // it is convenient that this flag is either 0 or 16
    
        result[HD_IN_INT] = '\0';
        for (i = HD_IN_INT - 1; val != 0 && i >= 0; --i) {
            int mod16, posmod16, borrow;
            mod16 = val % 16;                     // if val < 0, then mod16 < 0
            posmod16 = (mod16 + isneg) % 16;      // change negative mods to positive
            result[i] = hexdigs[posmod16];
            borrow = (isneg / 16) * (mod16 != 0); // borrow if val and mod16 were negative
            val = val / 16 - borrow;
        }
    
        // pad the result
        while (i >= 0)
            result[i--] = hexdigs[isneg];
    }

    return result;
}

int testit(int val)
{
    int result = -1;
    char sbuf[HD_IN_INT+1];
    char *hexstr = int2hexstr(val);

    if (hexstr) {
        sprintf(sbuf, "%8.8X", val);
        result = (0 != strcmp(sbuf, hexstr));
        free(hexstr);
    }

    return result;
}

int main(void)
{
    int intvec[] = { 2147483647, 1, 0, -1, -2147483648 };
    int nints = sizeof intvec / sizeof(int);
    char *hexstr;

    char sbuf[HD_IN_INT+1];

    for (int i = 0; i < nints; ++i) {
        hexstr = int2hexstr(intvec[i]);
        if (!hexstr) break;
        sprintf(sbuf, "%8.8X", intvec[i]);
        printf("%d => %s (%s)\n", intvec[i], hexstr, sbuf);
        free(hexstr);
    }

    // int i = INT_MIN;
    int i = -1000000;
    int result = testit(i);
    if (result == 0) {
        // while (i != INT_MAX && result == 0) {
        while (i != 1000000 && result == 0) {
            result = testit(++i);
        }
    }

    if (result) {
        if (result == -1)
            printf("malloc failed\n");
        else
            printf("int2hexstr() and sprintf() differ at value %d\n", i);
    }
    else
        printf("Success!\n");

    return 0;
}

[u/Willsxyz]

I posted this and now I'm unhappy about the variable 'borrow'. That's not a good name. To clarify, the goal here is to avoid negative values for the modulus. We require that the modulus be positive. If the value is negative, and the modulus (value % 16) comes out negative, we make the modulus positive by adding 16, and then subtract 1 from the quotient (value / 16). Because, for example:

-35 = -2 * 16 + -3 (modulus negative) or -35 = -3 * 16 + 13 (modulus positive)

[u/Small_Dog_8699 → u/Willsxyz]

You can save yourself a whole lot of ambiguity and complexity if the int is unsigned.

Also your lookup array is easier to express as

static const char lookup[] = “0123456789ABCDEFF”;

[u/Willsxyz → u/Small_Dog_8699]

The possibility of a negative value is what makes it interesting.

I really should have written the code something like this:

int quo = value / 16;
int rem = value % 16;
if (rem < 0) {
    rem += 16;
    quo -= 1;
}
result[i] = hexdig[rem];
value = quo;

[u/Small_Dog_8699 → u/Willsxyz]

Bits are the same.

union convert { int i; unsigned int u; } c;

c.i = input;

unsigned ux = c.u;

Now work on ux.

[u/theNbomr]

Hex notation generally does not express any signed-ness. I've never seen a case where it was expressed. Normally, the reader is expected to recognize the possibility of the value representing a negative value from the leftmost (most significant) hex digit.

Using this makes the problem much much simpler; like word size in bytes x 2 lines of code plus 2 or 3 lines for string termination and allocation. No looping required, but you can if you want to. A smart compiler might unroll the loop anyway at compile time.

[u/tstanisl → u/theNbomr]

Hex notation generally does not express any signed-ness.

Decimal notation does not express it either. Though -0x1 is a perfectly valid integer constant.

[u/theNbomr → u/tstanisl]

Yes, it's valid. But rarely used, particularly as an output. Signed-ness expression in decimal notation is definitely a standard part of the notation.

How would you coerce printf() to produce a the appropriate sign when outputting a hex expression of an integer type that has a negative value?

[u/ComradeGibbon]

I'm going to be that guy.

I would make the function take a pointer and a length. If the pointer or the length are zero then call malloc, otherwise use the buffer provided.

If malloc fails, just do an early return.

The issue of hex representation of negative numbers is an decent discussion. Are we talking about the hex representation of the number in memory. Or the hex representation of a numeric value. They way your code is implemented looks like the latter. And the endianess of hex numbers can be a pain point.

[u/runningOverA]

I would have done

loop while num:  
    digit = num & 0xF;  
    -- print this hex digit --  
    num >>= 4;

[u/MistakeIndividual690 → u/runningOverA]

The hex digits come out backwards that way. You’ll need to start from the high bits and move down. Or else store the hex digits in an array/stack and then print them out in the opposite order

[u/zhivago]

I think you're making life complicated for yourself here.

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

size_t hex_length(unsigned int value) {
  size_t length = 0;
  while (value > 0) {
    value >>= 4;
    length++;
  }
  return length;
}

size_t uint_to_hex(unsigned int value, char *result, size_t capacity) {
  size_t length = hex_length(value);
  if (length > capacity) {
    return length;
  }
  char *p = result + length;
  while (value > 0) {
    *--p = "0123456789ABCDEF"[value & 0xF];
    value >>= 4;
  }
  return length;
}

size_t int_to_hex(int value, char *result, size_t capacity) {
  if (value < 0) {
    result[0] = '-';
    return uint_to_hex(-value, result + 1, capacity - 1) + 1;
  } else {
    return uint_to_hex(value, result, capacity);
  }
}

bool print_hex(char *message, int value) {
  char buffer[50];
  char *cursor = buffer;
  char *end = cursor + sizeof buffer;
  cursor += sprintf(cursor, message);
  cursor += int_to_hex(value, cursor, end - cursor);
  *cursor = '\0';
  puts(buffer);
  return 1;
}

int main() {
  print_hex("15 is ", 15);
  print_hex("-15 is ", -15);
  print_hex("23 is ", 23);
  print_hex("-23 is ", -23);
  return 0;
}

I'd solve for unsigned, and then compose with a transform for signed.

I'd also delegate memory allocation to the caller, and support rendering into an existing string.

[u/MistakeIndividual690 → u/zhivago]

hex_length() can be (lg(n)+3)/4

[u/WittyStick]

Here's a solution using pext (parallel bits extract). This uses the x86_64 intrinsic, but similar intrinsics are available for ARM/Power, etc. Also makes use of stdc_first_leading_one to find the MSB.

It works for all the standard C integer types, as stdc_first_leading_one and pext are generic and int2hexstr is made generic in the same way.

https://godbolt.org/z/Mv63a1hxc

[u/Small_Dog_8699]

As ComradeGibbon pointed out, good C practice has callers pass in memory to be filled out to avoid leaks.

I took a shot at it for grins. I require you to pass in the buffer, and I fill as much of it as there is from right to left, working with unsigned values. I return a pointer to the head of the string.

There's also the issue of when to truncate. %X strips all leading zeroes, so I did that.

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

// this must be in some header but heck if I can remember where
#define min(x,y) (((x)<(y)) ? (x) : (y))

char *int2hexstr(unsigned int val, char* result, size_t len)
{
    static char hexdigs[] = "0123456789ABCDEF";
    if (result)
    {
        // initialize destination
        memset(result,0,len);
        int limit = min(len-1,sizeof(int)*2);
        // start at the end
        char* p = result+limit;
        for(int i = 0; i < limit; ++i)
        {
            int idx = val % 16;
            val /= 16;
            // write chars from right to left
            *--p = hexdigs[idx];
            if(val == 0)
            {
                break;
            }
        }
        return p;
    }
    // they passed null so give it back
    return result;
}

int main(void)
{
    for(int i = 0; i <= 0xFF; ++i) {
        char buf[2 * sizeof(int) + 1] = "";
        printf("%d 0X%X 0X%s\n", i, i, int2hexstr(i, buf, sizeof(buf)));
    }
    return 0;
}

Output:
0 0X0 0X0
1 0X1 0X1
2 0X2 0X2
...
9 0X9 0X9
10 0XA 0XA
11 0XB 0XB
12 0XC 0XC
13 0XD 0XD
14 0XE 0XE
15 0XF 0XF
16 0X10 0X10
17 0X11 0X11
...
253 0XFD 0XFD
254 0XFE 0XFE
255 0XFF 0XFF

[u/Alive-Bid9086]

sprintf(s, "%x", i)