An unusual way to print integers

[oPossum 1,083]

A common method of printing integers uses a divide (/) and modulus (%) operation to calculate each digit. This is portable and supports any number base. The string is created in reverse order and the digit generation can easily be terminated when all significant digits have been printed, so additional logic for leading zero suppression is not needed.

 

A much faster method uses BCD math to generate a BCD value that can then be easily convered to a string. This requires assembly or intrinsic C functions for the most efficient BCD math, so it isn't portable.

 

The method shown here creates a fixed point binary fraction using a single division operation and then extracts the digits using bit shifts and an add. The division is unrolled and crafted to generate a result with the binary point between words to allow for efficient digit extraction. After division, the upper word contains the first digit and the lower word contains a binary fraction with all other digits. The digits are generated from the fraction by multiplying by 10. This is done with 2 shifts and an add. The result will be in the upper word. Preparation for the next digit is just a matter of clearing the upper word.

This certainly seems like an awkward method, but it requires far less math than doing division for each digit.

 

// Print unsigned 16 bit integer with leading zero suppression
static void spu16(char * s, uint16_t n)
{
	uint16_t d = 10000 << 2;
	uint32_t r = 0;
	if (n >= d) n -= d, r |= (1 << 18); d >>= 1;
	if (n >= d) n -= d, r |= (1 << 17); n <<= 1;
	if (n >= d) n -= d, r |= (1 << 16); n <<= 1;
	if (n >= d) n -= d, r |= (1 << 15); n <<= 1;
	if (n >= d) n -= d, r |= (1 << 14); n <<= 1;
	if (n >= d) n -= d, r |= (1 << 13); n <<= 1;
	if (n >= d) n -= d, r |= (1 << 12); n <<= 1;
	if (n >= d) n -= d, r |= (1 << 11); n <<= 1;
	if (n >= d) n -= d, r |= (1 << 10); n <<= 1;
	if (n >= d) n -= d, r |= (1 <<  9); n <<= 1;
	if (n >= d) n -= d, r |= (1 <<  8); n <<= 1;
	if (n >= d) n -= d, r |= (1 <<  7); n <<= 1;
	if (n >= d) n -= d, r |= (1 <<  6); n <<= 1;
	if (n >= d) n -= d, r |= (1 <<  5); n <<= 1;
	if (n >= d) n -= d, r |= (1 <<  4); n <<= 1;
	if (n >= d) n -= d, r |= (1 <<  3); n <<= 1;
	if (n >= d) n -= d, r |= (1 <<  2);
	r += (1 << 2);

	unsigned c, z;
	c = z = (r >> 16);
	unsigned i = 4;
	do {
		if (z || c) *s++ = z = ('0' + c);
		r &= 0xFFFF;
		r <<= 1;
		r += (r << 2);
		c = (r >> 16);
	} while (--i);
	*s++ = '0' + c;
	*s = 0;
}

When a 32 bit hardware multiplier is available, the code can be modified to multiply by the reciprocal rather than divide. The multiplication by 10 is now explicit to also take advantage of the hardware multiplier.

static void spu16(char * s, uint16_t n)
{
	uint32_t r = ((53687UL * n) >> 13) + (1 << 2);

	unsigned c, z;
	c = z = (r >> 16);
	unsigned i = 4;
	do {
		if (z || c) *s++ = z = ('0' + c);
		r = (r & 0xFFFF) * 10;
		c = (r >> 16);
	} while (--i);
	*s++ = '0' + c;
	*s = 0;
}