Checking if a double is a power 2

Question

I'm not sure how to check if a double is a power of 2. This is my code so far:

double x = Double.longBitsToDouble(
    Double.doubleToRawLongBits(n) & Double.doubleToRawLongBits(n - 1)
);

I used the following formula to find if the number is a power of 2:

n & (n - 1) == 0

But its not working.

see also http://stackoverflow.com/questions/600293/how-to-check-if-a-number-is-a-power-of-2 — , Mar 25 '17 at 17:36
Aren't all Java `double` values powers of 2? Since `double` is an IEEE-754 **binary** double-precision value? Or do you mean a whole number power of 2? — T.J. Crowder, Mar 25 '17 at 17:37
You should understand why the trick is supposed to work, and what the bits in a `double` represent in order to understand why that trick **won't work with `double`**. — RealSkeptic, Mar 25 '17 at 17:47
@T.J.Crowder Obviously he means a whole-number power. I mean, any positive number could be expressed as some irrational power of 2. — D M, Mar 25 '17 at 17:48
@DM: I don't think it's obvious. If you have to invoke irrational numbers to make it obvious, I don't think it's obvious at all. — T.J. Crowder, Mar 25 '17 at 17:59
@T.J.Crowder Irrational numbers are exactly why it is obvious. But if you can tell me what (rational) power of two 3 is, I might consider conceding the point. — D M, Mar 25 '17 at 18:07
Since all `double` values are only coincidentally accurate, obviously the assertion that "every `double` is a power of `2`" implies "to within one ULP". So the question of irrational numbers is irrelevant. — Lew Bloch, Mar 25 '17 at 19:08

score 4 · Answer 1 · edited Feb 11 '18 at 16:04

If the problem is working with very large numbers, then Oleksandr's answer is better, but if you really want to check whether a double is an even power of two, you can just check if the mantissa is zero:

(Double.doubleToLongBits(n) & 0x000fffffffffffffL) == 0

To be more robust, you'll want to handle the edge cases for non-normalized numbers (infinities, NaNs, denormals, and perhaps decide on whether zeroes should return true), but those are normally edge cases.

Oleksandr Pyrohov · Accepted Answer · 2018-02-11T15:58:22.283

2

To deal with big numbers you can use the BigInteger class:

public boolean isPowerOfTwo(BigInteger n) {
    if (n.compareTo(BigInteger.ZERO) <= 0) {
        return false;
    }
    return (n.and(n.subtract(BigInteger.ONE))).equals(BigInteger.ZERO);
}

edited Feb 11 '18 at 15:58

answered Mar 25 '17 at 17:35

Oleksandr Pyrohov

14,685
6
61
90

Doesn't work for 0.5, which is an integer power of 2. – Toby Speight Mar 06 '21 at 14:46

Ames · Answer 3 · 2021-03-07T17:24:05.680

This should work for all cases, though whether infinity is considered a power of 2 may be application specific.

public static boolean isPowerOfTwo(double val) {
    if (val <= 0.0 || Double.isNaN(val))
        return false; // You can't raise 2 to a power and get a negative number or zero.
    if (Double.isInfinite(val))
        return false; // Arguable assumption. val is bigger than MAX_VALUE but we don't really know if it's a power of 2 or not.
    long significand = Double.doubleToLongBits(val) & 0x000f_ffff_ffff_ffffL;
    if (val >= Double.MIN_NORMAL)
        return significand==0; // only the hidden 1 remains
    else
        return (Long.bitCount(significand) == 1); // denormalized, no hidden one, power of two only if exactly one bit in significand is set
}

Checking if a double is a power 2

3 Answers3