[#4 - Int to char]

Numbers between 0 and 9

return (n + '0'); 

The snippet above illustrates a situation where it is still perfectly acceptable to convert an (unsigned) integer to a single character.

If we assume n is a digit between 0 and 9, we can simply add the character 0 to immediately retrieve the char value.

While this approach is ideal for maximum performance, the caller must guarantee that the input is indeed a valid single-digit number.

Numbers between 00 and 99

Unfortunately, integers cannot be easily translated or tricked into a conversion like a char to an int. However, this is where a LUT (lookup table) comes in handy. Why bother performing expensive calculations when we can pre-compute the results ourselves?

Consider the following LUT table:

const char dec_lut[100][2] = {
    {'0','0'}, {'0','1'}, {'0','2'}, {'0','3'}, {'0','4'}, {'0','5'}, {'0','6'}, {'0','7'}, {'0','8'}, {'0','9'},
    {'1','0'}, {'1','1'}, {'1','2'}, {'1','3'}, {'1','4'}, {'1','5'}, {'1','6'}, {'1','7'}, {'1','8'}, {'1','9'},
    {'2','0'}, {'2','1'}, {'2','2'}, {'2','3'}, {'2','4'}, {'2','5'}, {'2','6'}, {'2','7'}, {'2','8'}, {'2','9'},
    {'3','0'}, {'3','1'}, {'3','2'}, {'3','3'}, {'3','4'}, {'3','5'}, {'3','6'}, {'3','7'}, {'3','8'}, {'3','9'},
    {'4','0'}, {'4','1'}, {'4','2'}, {'4','3'}, {'4','4'}, {'4','5'}, {'4','6'}, {'4','7'}, {'4','8'}, {'4','9'},
    {'5','0'}, {'5','1'}, {'5','2'}, {'5','3'}, {'5','4'}, {'5','5'}, {'5','6'}, {'5','7'}, {'5','8'}, {'5','9'},
    {'6','0'}, {'6','1'}, {'6','2'}, {'6','3'}, {'6','4'}, {'6','5'}, {'6','6'}, {'6','7'}, {'6','8'}, {'6','9'},
    {'7','0'}, {'7','1'}, {'7','2'}, {'7','3'}, {'7','4'}, {'7','5'}, {'7','6'}, {'7','7'}, {'7','8'}, {'7','9'},
    {'8','0'}, {'8','1'}, {'8','2'}, {'8','3'}, {'8','4'}, {'8','5'}, {'8','6'}, {'8','7'}, {'8','8'}, {'8','9'},
    {'9','0'}, {'9','1'}, {'9','2'}, {'9','3'}, {'9','4'}, {'9','5'}, {'9','6'}, {'9','7'}, {'9','8'}, {'9','9'}
};

Then a resulting algorithm to convert the integer is:

cb[0] = dec_lut[n][0];
cb[1] = dec_lut[n][1];

Where n is a number between 00 and 99. All it takes is a simple look up!

Numbers between 0000 and 9999

Okay, if this is so easy to do, why not create a LUT that grows exponentially? Well, the CPU cache has a very limited size, and consuming it entirely with a huge LUT essentially kills all the performance gains. To tackle this, we can treat any number equal to or greater than 100 as 0100. Why? Because by treating the integer as a 4-digit number with leading zeros, we can split it, which allows us to make use of the small LUT.

However, there are a few more tricks that can be used to avoid an expensive division and a modulo operation to split the number into two chunks.

uint32_t left_chunk = ((uint64_t)n * (uint64_t)1374389535) >> 37;
uint32_t right_chunk = n - ((left_chunk << 6) + (left_chunk << 5) + (left_chunk << 2));

cb[0] = dec_lut[left_chunk][0];
cb[1] = dec_lut[left_chunk][1];
cb[2] = dec_lut[right_chunk][0];
cb[3] = dec_lut[right_chunk][1];

The snippet above illustrates how this is achieved. By using the Granlund-Montgomery algorithm to mimic division by 100 in the left_chunk, we can extract the numbers safely for our limited range of up to 9999. The right_chunk is essentially a modulo by 100, attempting to get the lower remainder of the division. The number 100 is (64 + 32 + 4), so we shift by 6, 5, and 2.

Numbers between 00000000 and 99999999

uint32_t left_chunk = ((uint64_t)n * (uint64_t)3518437209) >> 45;
uint32_t right_chunk = n - ((left_chunk << 13) + (left_chunk << 10) + (left_chunk << 9) + (left_chunk << 8) + (left_chunk << 4)); 
//================ The logic for 0000 to 9999 is exactly the same for each chunk past this point ===================================================
uint32_t left_chunk_upper = ((uint64_t)left_chunk * (uint64_t)1374389535) >> 37;
uint32_t left_chunk_lower = left_chunk - ((left_chunk_upper << 6) + (left_chunk_upper << 5) + (left_chunk_upper << 2));
uint32_t right_chunk_upper = ((uint64_t)right_chunk * (uint64_t)1374389535) >> 37;
uint32_t right_chunk_lower = right_chunk - ((right_chunk_upper << 6) + (right_chunk_upper << 5) + (right_chunk_upper << 2));
cb[0] = dec_lut[left_chunk_upper][0];
cb[1] = dec_lut[left_chunk_upper][1];
cb[2] = dec_lut[left_chunk_lower][0];
cb[3] = dec_lut[left_chunk_lower][1];
cb[4] = dec_lut[right_chunk_upper][0];
cb[5] = dec_lut[right_chunk_upper][1];
cb[6] = dec_lut[right_chunk_lower][0];
cb[7] = dec_lut[right_chunk_lower][1];

The snippet above illustrates that the same principle will apply even to 8-digit numbers. However, the number needs to be split into two 4-digit chunks, followed by four 2-digit chunks. The magic division and modulo operations here need to handle operations by 10,000 to allow the inital split. Afterwards, the usual business of 0000 to 9999 conversion logic applies.