Snippets
Created by
lion 137
last modified
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 | #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;
}
|
Comments (0)
You can clone a snippet to your computer for local editing. Learn more.