/* potencia2.cpp: indica si un número es o no una potencia de 2
 * Se pueden generar dos tipos de ejecutables a partir de este código fuente:
 *
 * [1] Si la macro BENCHMARK no está definida, genera una aplicación interactiva que permite
 * al usuario ingresar números y saber si son o no potencias de 2.
 *
 * [2] Si la macro BENCHMARK está definida, genera una aplciación en lote que ejecuta dos
 * formas distintas de calcular si un número es o no potencia de 2: con divisiones enteras
 * o con operadores de bits. Cada versión es ejecutada ITERACIONES veces y se mide la
 * duración de cada una de ellas para determinar cuál es la más eficiente
*/

#include <iostream>
#include <ctime>

// La cantidad de veces que se va a invocar cada versión de la función para hacer el benchmark
const size_t ITERACIONES = 50000000;

// Crea un tipo de datos nuevo: entero_t que equivale a unsinged long int
typedef unsigned long int entero_t;


// Retorna true si valor es una potencia de 2. El cálculo se hace con divisiones enteras
bool es_potencia_de_2_v1(entero_t valor)
{
	// Divide el valor original sucesivamente por 2 y si todos los módulos fueron 0 es porque
	// el número era una potencia de 2. Apenas no sea divisible por 2 retorna false
	for ( ; valor > 1; valor /= 2 )
		if ( valor %2 != 0 )
			return false;

	return true;
}

// Retorna true si valor es una potencia de 2. El cálculo se hace con operadores de bits
bool es_potencia_de_2_v2(entero_t valor)
{
	// Si el resultado de un AND binario de un número y su predecesor es 0, es una potencia
	// de 2: http://www.cprogramming.com/tutorial/bitwise_operators.html
	return !(valor & (valor - 1));
}


// Defínase esta macro al invocar el compilador para generar un ejecutable con benchmark. Ej:
//     g++ -DBENCHMARK potencia2.cpp -o potencia2_benchmark
#if defined(BENCHMARK)

// Invoca ITERACIONES veces cada una de las dos versiones de la función es_potencia_de_2 y
// cronometriza cuanto tarda cada una y finalmente imprime sus duraciones en segundos; con
// el fin de determinar cuál de las dos versiones es más eficiente
int main()
{
	// [1] Primera versión de es_potencia_de_2: con divisiones enteras
	// Se registra el tick del reloj del procesador en que la primera versión inició su ejecución
	clock_t inicio = clock();

	// Se invoca es_potencia_de_2_v1() ITERACIONES veces y se cuenta cuántas potencias encuentra
	// entre 1 e ITERACIONES, sólo con fines ilustrativos, lo que importa es correr la función
	// muchas veces y cronometrizarla
	size_t conteo_potencias_2 = 0;
	for ( size_t i = 0; i < ITERACIONES; ++i )
		if ( es_potencia_de_2_v1(i) )
			++conteo_potencias_2;

	// Imprimir lo que tardó la versión 1 de la función es_potencia_de_2 con divisiones
	// la diferencia 'clock() - inicio' indica la cantidad de ticks del reloj que transcurrieron
	// mientras se hicieron las ITERACIONES invocaciones. Para convertirlas a segundos se debe
	// hacer división flotante entre la macro CLOCKS_PER_SEC
	std::cout << conteo_potencias_2 << " potencias encontradas con divisiones en "
		<< (static_cast<double>(clock() - inicio) / CLOCKS_PER_SEC) << " segundos" << std::endl;


	// [2] Se repite el proceso anterior con la segunda versión de es_potencia_de_2: con
	// operadores de bits
	inicio = clock();
	conteo_potencias_2 = 0;
	for ( size_t i = 0; i < ITERACIONES; ++i )
		if ( es_potencia_de_2_v2(i) )
			++conteo_potencias_2;

	std::cout << conteo_potencias_2 << " potencias encontradas con operadores de bits "
		<< (static_cast<double>(clock() - inicio) / CLOCKS_PER_SEC) << " segundos" << std::endl;

	return 0;
}

#else // defined(BENCHMARK)

// Permite al usuario ingresar números interactivamente, y muestra cuáles de ellos son
// potencias de 2
int main()
{
	while ( true )
	{
		// Lee un entero de la entrada estándar (usualmente el teclado)
		entero_t valor = 0;
		std::cout << "Número: ";
		std::cin >> valor;

		// Si se ingresó 0, se termina la invocación de main() retornando 0 al sistema operativo
		if ( valor == 0 ) return 0;

		// Si es otro valor, se indica en la salida estándar si es o no potencia de 2
		// Los paréntesis redondos aquí son obligatorios, dado que el operador << tiene
		// precedencia sobre el operador ternario ?:
		std::cout << valor << (es_potencia_de_2_v2(valor) ? " " : " no ") << "es potencia de dos"
			<< std::endl << std::endl;
	}

	return 0;
}

#endif // defined(BENCHMARK)