6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The function you need here is, $$f(x)=2^k\mid 2^k\leq x\lt 2^{k+1}\textrm{ for some }k\in\Bbb Z$$ $\endgroup$ – Prasun Biswas May 21 '15 at 16:46
  • $\begingroup$ Do you have a floor(float x) function or a log_2(float x) function that we can use? If you do then this isn't too hard (as per user SMF's answer). Otherwise this could be much harder. (also, what language are you using to write this program? this may be important for how people choose to answer.) $\endgroup$ – Mike Pierce May 21 '15 at 16:53
  • $\begingroup$ Do you know binary $\endgroup$ – Ilaya Raja S May 21 '15 at 17:10
  • $\begingroup$ @mapierce271: it's not very hard without any library functions: see my answer. $\endgroup$ – Rob Arthan May 21 '15 at 17:11
  • $\begingroup$ @mapierce271 : Yes, I do. It's objective-c. Thanks for your info and for editing my questions :) You guys are all smart. $\endgroup$ – Mustofa May 21 '15 at 17:21
5
$\begingroup$

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} $$

$\endgroup$
  • $\begingroup$ Haha, thanks! I confirmed that this method works in my program (objective-c). $\endgroup$ – Mustofa May 21 '15 at 17:14
2
$\begingroup$

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.)

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The C language doesn't require floating point numbers to be represented using the IEEE formats (and your bit manipulations rely on that) . You can't be bothered to find out whether 16-digit hexadecimal literals are valid in C. How does anyone make use of your answer? $\endgroup$ – Rob Arthan May 21 '15 at 20:54
-1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.