Consider introducing BitOperations.IsPow2 or Math.IsPow2

[john-h-k]

Introduce methods

Rationale and Usage

Checking if a number is a power of 2 is a relatively common operation. There's always the

(value & (value - 1)) == 0 && value != 0

bit twiddle hack, but it is verbose, clunky, not immediately clear, not ideal performance wise, and requires remembering.
Introducing a simple API that is equivalent would be useful.

Proposed API

namespace System.Numerics
{
    public static class BitOperations
    {
        public static bool IsPow2(int value);
        public static bool IsPow2(uint value);
        public static bool IsPow2(long value);
        public static bool IsPow2(ulong value);
    }
}

Details

It uses a popcount operation where possible, else uses the bit twiddle hack.

Open Questions

• Should we consider 0 a power of 2?

  • The classic bit twiddle doesn't

• Should we have methods for float/double (or even decimal)?

  • With float/double you can compare the mantissa to 0.5 I believe, but it isn't really
    "in character" with the rest of BitOperations (which generally only supports integral types)

Pull Request

#36163

[EgorBo]

What about other types: signed integers and even floats (e.g. 0.5f is technically a power of two)?
Also, JIT can be taught to recognize (value & (value - 1)) == 0 && value != 0 as popcnt (see https://godbolt.org/z/rZ5U39)

[tannergooding]

Even if the JIT can be "taught" that (value & (value - 1)) == 0 && value != 0 is Popcnt, I think this falls into the same spirit as some of the other BitOperations functions (such as RotateLeft).

People shouldn't necessarily be expected to remember every "bit-twiddling hack" (although http://graphics.stanford.edu/~seander/bithacks.html is a good reference for them). There are also a lot of patterns and which are easiest to recognize by the JIT vs which actually perform the best is a constantly moving target.

So, exposing a "helper" method on BitOperations is, I think, a reasonable alternative for this functionality. It gives a single centralized place people can reference the most common functionality and one we can special-case and optimize as things progress (without risking breaking peoples existing recognized patterns).

[john-h-k]

What about other types: signed integers and even floats (e.g. 0.5f is technically a power of two)?

signed integers can be done simply by adding a check the number isn't <type>.MinValue alongside (the only negative value where popcnt == 1).

floating points can be done by extracting exponent (preserving sign) and comparing it to 0.5, i think

[NickStrupat]

In addition to an expansion of per-primitive BitOperations methods, I would love to see a BitSpan type with all the bit operations available to a vector of bits backed by a Span<T> where T : byte | ushort | uint | ulong. The operations could be happy-pathed with whatever intrinsics are available given the CPU and BitSpan length.

I have part of a prototype I can show if there's interest.

[tannergooding]

@john-h-k, could you clean up the initial proposal just a bit and then I can mark this ready-for-review?

Ideally this would loosely follow the "good example" listed under step 1 of our API Review Process. Not all sections are needed, but providing the rationale and proposed API sections help ensure the review proocess flows more smoothly and the request is immediately obvious.

I believe the proposed location should be System.Numerics.BitOperations.

[john-h-k]

👍 Done

[tannergooding]

Thanks! As to the pending questions.

Should we have methods for float/double (or even decimal)?

I think this would be fine for float/double as it is essentially a bit twiddling operation as well and the check is very cheap. I'm unsure about decimal as the check wouldn't necessarily be cheap and its use-case (being a base-10 number) seems more limited.

Should we consider 0 a power of 2?

No for integrals. For floating-point the question is a bit more complicated as 2^(-∞) == 0

[terrajobst]

Video

Looks good as proposed

namespace System.Numerics
{
    public static class BitOperations
    {
        public static bool IsPow2(int value);
        public static bool IsPow2(uint value);
        public static bool IsPow2(long value);
        public static bool IsPow2(ulong value);
    }
}

[AntonLapounov]

@terrajobst Note that a similar method on the BigInteger class is named IsPowerOfTwo.

[tannergooding]

That was also noted in API review. IsPow2 is consistent with the other members on BitOperations and in Math/MathF. Overall, BigInteger.IsPowerOfTwo is the inconsistent API