Ceil function: how can we implement it ourselves?

You can take apart the ingredients of an IEEE754 floating point number and implement the logic yourself:

#include <cstring>

float my_ceil(float f)
{
    unsigned input;
    memcpy(&input, &f, 4);
    int exponent = ((input >> 23) & 255) - 127;
    if (exponent < 0) return (f > 0);
    // small numbers get rounded to 0 or 1, depending on their sign

    int fractional_bits = 23 - exponent;
    if (fractional_bits <= 0) return f;
    // numbers without fractional bits are mapped to themselves

    unsigned integral_mask = 0xffffffff << fractional_bits;
    unsigned output = input & integral_mask;
    // round the number down by masking out the fractional bits

    memcpy(&f, &output, 4);
    if (f > 0 && output != input) ++f;
    // positive numbers need to be rounded up, not down

    return f;
}

(Insert the usual "not portable" disclaimer here.)


Here is a naive implementation for positive numbers (this uses the fact that casting to (int) truncates toward zero):

int ceil(float num) {
    int inum = (int)num;
    if (num == (float)inum) {
        return inum;
    }
    return inum + 1;
}

It is easy to extend this to work with negative numbers too.

Your question asked for a function returning int, but normally the ceil() function returns the same type as its argument so there are no problems with the range (that is, float ceil(float num)). For example, the above function will fail if num is 1e20.


My 5 cents:

template <typename F>
inline auto ceil(F const f) noexcept
{
  auto const t(std::trunc(f));

  return t + (t < f);
}

That is essentially what you have to do, but without converting to string.

A floating-point number is represented as (+/-) M * 2^E. The exponent, E, tells you how far away you are from the binary point*. If E is big enough, there is no fractional part, so there's nothing to do. If E is small enough, there is no integer part, so the answer is 1 (assuming M is non-zero, and the number is positive). Otherwise, E tells you where the binary point appears within your mantissa, which you can use to do a check, and then perform rounding.


* Not decimal point, because we're in base-2, not base-10.

Tags:

C++

Ceil