ACP: Add prev_power_of_two and bit_width methods for unsigned integers and NonZero<uN>

[okaneco]

Proposal

Problem statement

next_power_of_two is implemented for unsigned integers but no corresponding prev_power_of_two is available.
Some other common integral bit and power-of-2 operations would be convenient library features to have available for users.

Motivating examples or use cases

Calculating a power-of-2 is important for data structures such as circular queues/circular buffers whose indexing operations benefit from the buffer length being a power-of-2. It is useful in some computer graphics applications where textures must be a power-of-2. Algorithms like bitwise binary search can make use of prev_power_of_two. The result of prev_power_of_two can also be used to clear the most significant set bit. Some other languages call this operation bit_floor.

bit_width is a helpful building block for calculating the number of bits required to represent a value and is used to calculate the prev_power_of_two.
The compiler has several handwritten implementations of bit_width throughout the codebase.

C++20 added the <bit> header which includes functions to interact with and process bits. Rust has equivalent functions to all but bit_floor, bit_width, and endian. C23 includes the <stdbit.h> header offering similar functionality to the C++20 header.

C++20	C23	Rust
bit_ceil	stdc_bit_ceil	next_power_of_two
bit_floor	stdc_bit_floor	None
bit_width	stdc_bit_width	None

This ACP seeks to add bit_floor and bit_width equivalent functions, and stabilize the currently private one_less_than_next_power_of_two helper function used to calculate next_power_of_two.

Solution sketch

Summary

For unsigned integers and NonZero<uN>:

1. Add prev_power_of_two, checked_prev_power_of_two, wrapping_prev_power_of_two
2. Add bit_width
3. Stabilize one_less_than_next_power_of_two

---

Since 0_usize.is_power_of_two() == false, the result of 0_usize.prev_power_of_two() is undefined.

Credit to @kennytm for the following results table:

u64	prev_power_of_two	checked_prev_power_of_two	wrapping_prev_power_of_two
264 - 1	263	Some(263)	263
20	16	Some(16)	16
1	1	Some(1)	1
0	panic (debug) wrapping (release)	None	263 or 1 or 0

/// Returns the smallest number of bits required to store this value, or `0` if `self == 0`.
pub const fn bit_width(self) -> u32 {
    if self == 0 {
        0
    } else {
        Self::BITS - self.leading_zeros()
    }
}

/// Returns the largest power-of-2 less than or equal to the input, or `None` if `self == 0`.
pub const fn checked_prev_power_of_two(self) -> Option<Self> {
    if self == 0 {
        None
    } else {
       Some(1 << (self.bit_width() - 1))
    }
}

Alternatives

1. Only implement fn prev_power_of_two(self) -> Self on NonZero<uN> to avoid handling of special cases. This may be worse for discoverability of the function and more cumbersome for users to write as they'll have to use a construct like NonZero::new().map_or().
2. Don't implement wrapping_prev_power_of_two because it's unclear what the behavior should be for 0. panic on 0 in prev_power_of_two in release.

Links and related work

Internals thread
https://internals.rust-lang.org/t/add-prev-power-of-two/14281

C++20 <bit> header

C++ std::bit_floor documentation
https://en.cppreference.com/w/cpp/numeric/bit_floor
Unaccepted proposal, "N3864: A constexpr bitwise operations library for C++"
https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3864.html
"Integral power-of-2 operations"
https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0556r0.html
"On the names of low-level bit manipulation functions" (renaming floor2 ⇒ bit_floor, log2p1 ⇒ bit_width)
https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p1956r1.pdf

C23 <stdbit.h> header

"N3022 - Modern Bit Utilities"
https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3022.htm#design-bit-stdc_bit_ceil

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[kennytm]

bit_width can be used to calculate the index of the most significant set bit with num.bit_width() - 1 (if nonzero).

This is just num.ilog2().

[okaneco]

Correct. I can remove that line since it's not as motivating of an example. I had a different example before I rewrote that as num.bit_width().saturating_sub(1) which can be used in a const fn and doesn't have to check that num is nonzero.

highest_one can be implemented as

pub const fn highest_one(self) -> Self {
    if self == 0 {
        0
    } else {
       1 << self.ilog2()
    }
}

[kennytm]

I think prev_power_of_two makes sense but like next_power_of_two there should be checked/wrapping variants regarding 0.

u64	prev_power_of_two	checked_prev_power_of_two	wrapping_prev_power_of_two
264 - 1	263	Some(263)	263
20	16	Some(16)	16
1	1	Some(1)	1
0	panic (debug) wrapping (release)	None	263 or 1 or 0

[scottmcm]

Some musings, which may or may not want to actually change anything here:

• For everything with special cases for zero, we could consider defining them just on NonZero, if the NonZero::new().map_or() implementation is just as good.
• ptr::Alignment is the "usize but always a power of two" type. I wonder if it'd be useful to have a type like that for other widths too, since I expect a & b.next_power_of_two() optimizes poorly today.
• Alternatively, how often is the power needed vs the shift? If prev_power_of_two is 1 << x.ilog2(), is that enough?
• A related thing I've sometimes wanted is the "fill the low bits" version, aka one_less_than_next_power_of_two. And that has the nice behaviour that it's well-defined for everything; no overflow cases.

[okaneco]

I think prev_power_of_two makes sense but like next_power_of_two there should be checked/wrapping variants regarding 0.

I can rewrite the proposal to have all 3 for completeness but I'd prefer to include only what has the best chance of being accepted or stabilized. wrapping_next_power_of_two still isn't stabilized today.

I agree with adding prev_power_of_two and checked_prev_power_of_two.
Users can handle the None from checked_prev_power_of_two to get the behavior they want for 0. Thus, the wrapping variant seems unnecessary to me with how controversial deciding on the output of 0 will be.

• A related thing I've sometimes wanted is the "fill the low bits" version, aka one_less_than_next_power_of_two. And that has the nice behaviour that it's well-defined for everything; no overflow cases.

I also find this function useful and will consider adding it to the proposal.

[okaneco]

I've updated the original proposal to add prev_power_of_two, checked_prev_power_of_two, wrapping_prev_power_of_two, and stabilize one_less_than_next_power_of_two.

Thanks for all the feedback.

[orlp]

I think defining prev_power_of_two(0) == 0 is significantly more useful, and faster to boot. I don't think the checked and wrapping versions are necessary.

Similarly I think the name highest_bit_set or most_significant_one is a much better name for this function. Because let's be real, that's what someone really wants 99% of the time they're looking for this function.

But perhaps my concerns are best fulfilled with an alternative ACP that proposes least_significant_one and most_significant_one.