Floor function to the base 2

Question

I'm not a math guy, so I'm kinda confused about this. I have a program that needs to calculate the floor base $2$ number of a float.

Let say a number $4$, that base $2$ floor would be $4$. Other examples :

• $5 \to 4$
• $6 \to 4$
• $8 \to 8$
• $12 \to 8$
• $16 \to 16$
• $0.5 \to 0.5$
• $0.6 \to 0.5$
• $0.13 \to 0.125$

How would I do this and what is the name of this problem?

Answer 1

Let the number whose base 2 floor you want to find be $N$. We want to find the greatest $k\in \mathbb{Z}$ such that $2^k \leq N$. Take the base 2 log of both sides to get $k \leq \log_2{N}$. Since we want the maximum value of $k$ that still fulfills this inequality and that is an integer, we pick $k = \lfloor \log_2{N} \rfloor$. Then you just need to compute $2^k$, which is the actual value of your base 2 floor of $N$.

EDIT: So simply put, your wanted base 2 floor function $f_2$ looks like this:

$$ f_2(N) = 2^{\lfloor \log_2{N} \rfloor} $$

And for a floor in base $b$ (using the above logic), $f_b$ would be

$$ f_b(N) = b^{\lfloor \log_b{N} \rfloor} $$

Answer 2

Here's a description of an imperative algorithm to do the job. I am being naughty about numeric analysis and just testing real numbers for equality. I will leave you to worry about that.

Let $x$ be the input and put $r = 1$. Now there are three cases:

1. If $x < 1$, then divide $r$ by $2$ until $r \le x$, $r$ is now the result;
2. If $x = 1$ then $r$ is already the result;
3. If $x > 1$ then multiply $r$ by $2$ while $2r \le x$, $r$ is now the result.

(I don't believe this function has a standard name. As SMF says the formula for it $2^{\lfloor \log_2 x \rfloor}$, which is short enough not to need a name.)

Answer 3

Practical insight
Floor of base two is nothing but the floor of a binary number. Floor of base 10 gives floor of decimals .
let's see examples $$ floor_{10} 15.3=15$$ In binary- $ floor_2 110$(decimal equivalent 6)$=100$ (decimal equivalent 4) so to do this function first convert it into binary then take only the left most 1 and put the rest as 0's

For values like 0.625 it can be broken down to binary form which is 0.101 then $floor_2 0.101 = 0.1$ in binary converting to decimal form we get 0.5

Answer 4

If you want to round a single-precision floating point value down to the next power of 2, you can do this (as long as the number is "normalized", which it always is unless it's infinity, NaN, or extremely small) by making all the significand bits zero. Something like this would probably work:

float truncateSgand(float value) {
    return (float) ((uint32_t) value & 0xFF800000);
}

(You might have to worry about endianness.)

For a double-precision floating point, the equivalent code would be this. (I've never seen a 16-digit hexadecimal literal in C; I don't know if they're actually valid.)

double truncateSgand(double value) {
    return (double) ((uint64_t) value & 0xFFF0000000000000;
}

I haven't tested either of these functions.