CODEWITHSUNDEEP
javaalgorithmmath
ggrr
ggrr

Reputation: 7867

How to check if a number < 1 is power of 2?

for example: 0.5 and 0.25 is power of 2 but 0.3 is not, also I know checking if integer is power of 2 is easy, but how to find if number is power of 2 if the number < 1?

public bool isPowerOf2(float number){
    if(number>1){
        //easy to write
    }else if(number==1){
        return true;
    }else{
        //hard to write
    }
}

Upvotes: 7

Views: 980

Answers (4)

Dave
Dave

Reputation: 9085

Java uses IEEE 754 to encode floats. The portion from bits 22 to 0 in the binary encoding represent the mantissa (m). If m has exactly one 1 then the float is a power of 2.

http://introcs.cs.princeton.edu/java/91float/

(-1)^s × m × 2^(e - 127)

Sign bit (s) (bit 31). The most significant bit represents the sign of the number (1 for negative, 0 for positive).

Exponent field (e) (bits 30 - 23). The next 8 bits represent the exponent. By convention the exponent is biased by 127. This means that to represent the binary exponent 5, we encode 127 + 5 = 132 in binary (10000100). To represent the binary exponent -5 we encode 127 - 5 = 122 in binary (01111010). This convention is alternative to two's complement notation for representing negative integers.

Mantissa (m) (bits 22 - 0). The remaining 23 bits represent the mantissa, normalized to be between 0.5 and 1. This normalization is always possible by adjusting the binary exponent accordingly. Binary fractions work like decimal fractions: 0.1101 represents 1/2 + 1/4 + 1/16 = 13/16 = 0.8125. Not every decimal number can be represented as a binary fraction. For example 1/10 = 1/16 + 1/32 + 1/256 + 1/512 + 1/4096 + 1/8192 + ... In this case, the number 0.1 is approximated by the closest 23 bit binary fraction 0.000110011001100110011... One further optimization is employed. Since the mantissa always begins with a 1, there is no need to explicitly store this hidden bit.

Upvotes: 0

user949300
user949300

Reputation: 15729

Though using 1/x will likely work fine, one might be worried about roundoff errors.

Use Float.floatToRawIntBits(float). You probably want to check that bit 22 is on but bits 21-0 are off (also the sign bit should be 0). This works for both positive and negative powers of 2. The actual power is in bits 30-23.

Addendum: if bit 21 is off, but exactly one of bits 20-0 are on, it is a power of 2, as mentioned by @anonymous. There is a well know trick to quickly test if exactly one bit is set, which you can surely find somewhere on Stack Overflow.

Upvotes: 3

Tagir Valeev
Tagir Valeev

Reputation: 100349

Try this solution:

public boolean isPowerOf2(float number){
    if(number>1){
        //easy to write
    }else if(number==1){
        return true;
    }else if(number>0){
        return isPowerOf2(1.0f/number);
    }else
        return false;
}

By the way you can solve this simply by checking the bits of float binary representation:

public static boolean isPowerOfTwo(float i) {
    int bits = Float.floatToIntBits(i);
    if((bits & ((1 << 23)-1)) != 0)
        return ((bits & (bits-1)) == 0); // denormalized number
    int power = bits >>> 23;
    return power > 0 && power < 255; // 255 = Infinity; higher values = negative numbers
}

Upvotes: 7

Abhishek
Abhishek

Reputation: 7045

Just call isPowerOf2(1.0/number); in else block. It should resolve your problem.

Upvotes: 0

Related Questions