ACP: Add prev_power_of_two and bit_width methods for unsigned integers and NonZero<uN> · Issue #397 · rust-lang/libs-team (original) (raw)

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 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.

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:

/// 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 { 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 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.