78 lines
1.7 KiB
C
78 lines
1.7 KiB
C
#ifndef INCLUDE_GUARD_INT_UTILS_H
|
|
#define INCLUDE_GUARD_INT_UTILS_H
|
|
|
|
#include <stdint.h> // uint32_t, uint64_t
|
|
|
|
|
|
// /**
|
|
// * Integer logarithm, the biggest power `p` such that `2^p <= x`.
|
|
// */
|
|
// static int ilog2(uint64_t x) {
|
|
// int log = 0;
|
|
// while (x >>= 1) {
|
|
// log++;
|
|
// }
|
|
// return log;
|
|
// }
|
|
|
|
|
|
/**
|
|
* Integer Square root of `y`, that is `ceiling(sqrt(y))`
|
|
*/
|
|
static uint64_t isqrt(uint64_t x) {
|
|
// implements a binary search
|
|
uint64_t root = 0;
|
|
uint64_t left = 0; // left boundary
|
|
uint64_t right = x + 1; // right boundary
|
|
|
|
while(left + 1UL < right) {
|
|
root = (left + right) / 2UL;
|
|
if (root * root <= x) {
|
|
left = root;
|
|
} else {
|
|
right = root;
|
|
}
|
|
}
|
|
return left;
|
|
}
|
|
|
|
|
|
/**
|
|
* Inverse to the triangular numbers
|
|
*
|
|
* Given a positive number `x = p (p + 1) / 2` it computes `p` if possible.
|
|
* In case there is no positive integer solution `0` is returned.
|
|
*
|
|
* Note: this follows immediately from the quadratic equation.
|
|
*/
|
|
static uint32_t invTriag(uint32_t x) {
|
|
uint64_t root = isqrt(8UL * (uint64_t)x + 1UL);
|
|
if (root * root != 8UL * x + 1UL) {
|
|
return 0;
|
|
}
|
|
return (root - 1) / 2;
|
|
}
|
|
|
|
|
|
// /**
|
|
// * Number of sub-sets (including empty set) of max-size
|
|
// *
|
|
// * It computes, with `binom` beeing the binomial coefficient, the following sum
|
|
// *
|
|
// * sum_{i = 0}^k binom(n, i)
|
|
// */
|
|
// static uint64_t nrSubSets(uint64_t n, uint64_t k) {
|
|
// uint64_t sum = 1, binom = 1;
|
|
|
|
// for (uint64_t i = 1; i <= k; ++i) {
|
|
// binom *= n--;
|
|
// binom /= i;
|
|
// sum += binom;
|
|
// }
|
|
|
|
// return sum;
|
|
// }
|
|
|
|
|
|
#endif /* INCLUDE_GUARD_INT_UTILS_H */
|