#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 */