#include <algorithm>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <chrono>

static int log10_1(unsigned int num)
{
	int ret;
	static_assert(sizeof(num) == 4, "expected 32-bit long");
	if (num >= 10000)
	{
		if (num >= 1000000)
		{
			if (num >= 100000000)
				ret = (num >= 1000000000) ? 10 : 9;
			else
				ret = (num >= 10000000) ? 8 : 7;
		}
		else
			ret = (num >= 100000) ? 6 : 5;
	}
	else
	{
		if (num >= 100)
			ret = num >= 1000 ? 4 : 3;
		else
			ret = num >= 10 ? 2 : 1;
	}
	return ret;
}

// write string representation of number `n` into buf and return pointer to terminating null
char* to_str(char* buf, unsigned int n)
{
	static const char dig_[] = "0001020304050607080910111213141516171819"
		"20212223242526272829303132333435363738394041424344454647484950515253545556575859"
		"60616263646566676869707172737475767778798081828384858687888990919293949596979899";
	int len = log10_1(n);
	char *p = buf + len;
	*p-- = 0;
	while (n >= 100)
	{
		unsigned int x = (n % 100) * 2;
		n /= 100;
		*p-- = dig_[x + 1];
		*p-- = dig_[x];
	}
	if (n >= 10)
	{
		unsigned int x = n * 2;
		*p-- = dig_[x + 1];
		*p-- = dig_[x];
	}
	else
		*p-- = (char)('0' + n);
	return buf + len;
}

// write string representation of number `n` into buf and return pointer to terminating null
char* to_str(char* buf, long n)
{
	unsigned int l;
	if (n < 0)
	{
		*buf++ = '-';
		l = (unsigned int)(-n);
	}
	else
		l = (unsigned int)n;
	return to_str(buf, l);
}


template <typename T>
void foo(char *buffer, T value)
{
	static_assert(std::is_integral<T>::value, "Type of value must be an integral type");

	if (value < 0) {
		*(buffer++) = '-';
	}

	char *start = buffer;

	while (value != 0) {
		*(buffer++) = '0' + std::abs(value % 10);
		value /= 10;
	}

	if (buffer == start) {
		*(buffer++) = '0';
	}
	else {
		std::reverse(start, buffer);
	}

	*buffer = '\0';
}

int main()
{
	long ll[3000];
	for (int i = 0; i < sizeof(ll) / sizeof(ll[0]); ++i)
		ll[i] = (rand() << 16) | rand() * (rand() > 10000 ? -1 : 1);

	char buf1[32], buf2[32], buf3[32];

	for (int i = 0; i < sizeof(ll) / sizeof(ll[0]); ++i)
	{
		foo(buf1, ll[i]);
		to_str(buf2, ll[i]);
		sprintf(buf3, "%d", ll[i]);
		if (strcmp(buf1, buf2) || strcmp(buf1, buf3))
			printf("error!\n");
	}

	auto start1 = std::chrono::high_resolution_clock::now();
	for (int i = 0; i < 10000; ++i)
	{
		for (int i = 0; i < sizeof(ll) / sizeof(ll[0]); ++i)
			foo(buf1, ll[i]);
	}	auto finish1 = std::chrono::high_resolution_clock::now();
	auto start2 = std::chrono::high_resolution_clock::now();
	for (int i = 0; i < 10000; ++i)
	{
		for (int i = 0; i < sizeof(ll) / sizeof(ll[0]); ++i)
			to_str(buf2, ll[i]);
	}
	auto finish2 = std::chrono::high_resolution_clock::now();
	auto start3 = std::chrono::high_resolution_clock::now();
	for (int i = 0; i < 10000; ++i)
	{
		for (int i = 0; i < sizeof(ll) / sizeof(ll[0]); ++i)
			sprintf(buf3, "%d", ll[i]);
	}
	auto finish3 = std::chrono::high_resolution_clock::now();

	long long micro1 = std::chrono::duration_cast<std::chrono::milliseconds>(finish1 - start1).count();
	long long micro2 = std::chrono::duration_cast<std::chrono::milliseconds>(finish2 - start2).count();
	long long micro3 = std::chrono::duration_cast<std::chrono::milliseconds>(finish3 - start3).count();

	printf("foo time: %lld ms\n", micro1);
	printf("to_str time: %lld ms\n", micro2);
	printf("sprintf time: %lld ms\n", micro3);
}