Calculate floor value without FPU/SSE instruction

Author:	Wojciech Muła
Added on:	2013-12-29

Presented algorithm works properly for any normalized floating point value, examples are given for double precision numbers (64-bit).

The layout of value 8192.625:

 S  exp + bias  fraction
+-+-----------+----------------------------------------------------+
|0|10000001100|0000000000000101000000000000000000000000000000000000|
+-+-----------+----------------------------------------------------+
63 62       52 51                                                  0

The exponent value is 13, thus fraction bits spans range 0 .. 52 - 13:

+-+-----------+----------------------------------------------------+
|0|10000001100|0000000000000101000000000000000000000000000000000000|
+-+-----------+----------------------------------------------------+
                           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                           bits after decimal dot

To calculate the floor of value, the bits after decimal dot have to be clear. This operation doesn't alter the exponent, so only single bit-and is required, and no extra calculations are needed.

To be precise, value of dot_position := 52 - exponent decides what have to be done:

1. If dot_position > 52 then the value is less than 1.0, i.e. floor(x) = 0.
2. If dot_position <= 0 then the value have no fraction part (it is larger than 2⁵²), i.e. floor(x) = x.
3. If 0 < dot_position <= 52 then the value have fraction part and bits after dot_position bits have to be cleared.

The number of operations:

• Extracting exponent value requires: 1 shift, 1 bit-and, 1 subtract.
• Determining which case have to be selected requires up to 4 comparisons.
• When clearing bits is needed, then building bit-mask require: 1 shift, 1 subtract, 1 bit negation, 1 bit-and.

Sample program is available:

$ ./demo 123.75 0.012 120000000000000 0.99999999 99.999
floor(123.75000000) = 123.00000000
floor(0.01200000) = 0.00000000
floor(120000000000000.00000000) = 120000000000000.00000000
floor(0.99999999) = 0.00000000
floor(99.99900000) = 99.00000000