Friday, August 20, 2010

Checking if a Float is a Power of 2

Last article I showed bitwise ways to check if integers are powers of 2, for completeness I'll show bitwise ways to check if floats are powers of 2.

For floating point numbers, remember that they're represented in the form |S*1|E*8|M*23|.
S = Sign Bit (1-bit)
E = Exponent (8-bits)
M = Mantissa (23-bits)

Check out the IEEE-754 standard for more info:
http://en.wikipedia.org/wiki/IEEE_754-1985

The exponent is actually used to compute powers of 2, which is then multiplied by the mantissa, which has an implicitly hidden '1.' in front of it.

So when we're checking if a float is a power of two, all we have to do is check if the mantissa is 0, and the exponent is non-zero (when the exponent is zero, the result is zero when the mantissa is also zero, or a denormal value when the mantissa is non-zero, so we don't want to consider these as powers of two).

The code ends up looking like this:

typedef unsigned __int32 u32;

bool isPow2(float f) {
u32& i = (u32&)f;
u32 e = (i>>23) & 0xff;
u32 m = i & 0x7fffff;
return !m && e;
}


This however will end up counting negative-exponent powers of 2 (such as 2^-1 = 0.5), if this is not desirable, then we can modify the code to only count non-negative exponents (2^0 = 1, 2^1 = 2,...)

The modified code looks like this:

bool isPow2(float f) {
u32& i = (u32&)f;
u32 e = (i>>23) & 0xff;
u32 m = i & 0x7fffff;
return !m && e >= 127;
}


One last thing, both these versions will also consider negative powers of two (such as -4, -2, -1) to be powers of two.
If this is also undesirable, then we just need to check the Sign-bit of the float to determine if its negative, and if it is, then we will return false.

This last function returns true if the float is a positive power of two with a positive exponent (1, 2, 4, 8, 16...).

bool isPow2(float f) {
u32& i = (u32&)f;
u32 s = i>>31;
u32 e = (i>>23) & 0xff;
u32 m = i & 0x7fffff;
return !s && !m && e >= 127;
}

3 comments:

  1. Hi, I'm working on a C# library which I'm eventually going to release under the BSD license, and I'd like to use an adaptation of this for double-precision floats. Is it all right if I do that? How should I credit you?

    ReplyDelete
  2. The Best Bet of the Day | No Deposit Bonuses and Free Spins 2021
    If you want 점심 메뉴 룰렛 to start betting and win, you 해외 라이브 스코어 can 안전한 사이트 play all your favourite games at 포커사이트 a Bet365 Casino. We are open to giving you our best bets e스포츠 and welcome

    ReplyDelete
  3. Harrah's Casino, San Diego (MapYRO)
    Welcome to M life Rewards. Casino 창원 출장샵 Rewards 김천 출장샵 is a loyalty program that's available to you to earn 부천 출장안마 rewards 부천 출장안마 points, 삼척 출장안마 redeem them to earn real cash,

    ReplyDelete