#include <stdio.h>

/* Checking odd/even and computing an absolute value */
int is_odd(int x){
	return x & 1;
}
int is_even(int x){
	return !(x & 1) ;
}
int my_abs(int x){
	int y = x >> 31;
	return (x ^ y) - y;
}



/* Returns int average without overflow */
int average(int x, int y){  
	return (x & y) +((x ^ y)>>1);
}




/* Returns shift right signed */
int signed_shift_right(int x, int n){
	int m = 1 << 31 - n;
	return ((x >> n) ^ m) - m;
}




 /* function sign: returns 1 -> x > 0, -1 -> x < 0 and 0 if x = 0  */
int sign(int x){ 
	return -(x >> 31) | (-x >> 31);
}




/* Three valued binary comparison, returns -1 -> x < y, 0-> x = y, 1 -> x >y*/
int cmp(int x, int y){
	return (x > y) - (x < y);
}





void swap(int *x, int *y){ /* XOR swap (swap without temp variable)*/
	/* With a little loss of speed (about 15 - 20 % on my machine) you can add a branch here:
	if (x == y) return;
	to make it working correctly when typing: swap(&a, &a),
	without it function (instread of doing nothing) zeores it's argument
	(because it operates on one address - so first XOR zeroes left operand - at the same
	time zeroes y too, because this is the same thing!)*/
	*x = *x ^ *y;
	*y = *y ^ *x;
	*x = *x ^ *y;
}




/* Checks if x is within bound, provided, that b >= a, returns 1 if is and 0 otherwise.  */
int bound(int a, int x, int b){
	
	return (unsigned) (x - a) <= b - a;		
}




/* Exponentiation by binary decomposition of n , much faster than by squaring, 
 speed similar to pow from math.h (which works on floats though)*/
int iexp(int x, unsigned n) {
	if (n == 0) return 1;
	int p, y;
	y = 1;
	p = x;
	while(1) {
		if (n & 1) y = p*y;
			n = n >> 1;
			if (n == 0) return y;
		p = p*p;
	}
 }





/* Exponentiation by squaring iterative version of classical O(log(n)) algorithm*/
int exp_squaring_iter(int x, unsigned int n){
	if (n == 0) return 1;
	int y = 1;
	while (n > 1){
		if (is_even(n)){
			x *= x;
			n >>= 1;
		}
		else{
			y *= x;
			x *= x;
			n = (n - 1) >> 1;
		}
	}
	return x * y;
}

 
int main(int argc, char ** argv){
	
	return 0;
}