Open okaneco opened 2 weeks ago
bit_width
can be used to calculate the index of the most significant set bit withnum.bit_width() - 1
(if nonzero).
This is just num.ilog2()
.
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()
}
}
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 |
Some musings, which may or may not want to actually change anything here:
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.prev_power_of_two
is 1 << x.ilog2()
, is that enough?one_less_than_next_power_of_two
. And that has the nice behaviour that it's well-defined for everything; no overflow cases.I think
prev_power_of_two
makes sense but likenext_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.
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.
Proposal
Problem statement
next_power_of_two
is implemented for unsigned integers but no correspondingprev_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 ofprev_power_of_two
can also be used to clear the most significant set bit. Some other languages call this operationbit_floor
.bit_width
is a helpful building block for calculating the number of bits required to represent a value and is used to calculate theprev_power_of_two
. The compiler has several handwritten implementations ofbit_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 butbit_floor
,bit_width
, andendian
. C23 includes the<stdbit.h>
header offering similar functionality to the C++20 header.bit_ceil
stdc_bit_ceil
next_power_of_two
bit_floor
stdc_bit_floor
bit_width
stdc_bit_width
This ACP seeks to add
bit_floor
andbit_width
equivalent functions, and stabilize the currently privateone_less_than_next_power_of_two
helper function used to calculatenext_power_of_two
.Solution sketch
Summary
For unsigned integers and
NonZero<uN>
:prev_power_of_two
,checked_prev_power_of_two
,wrapping_prev_power_of_two
bit_width
one_less_than_next_power_of_two
Since
0_usize.is_power_of_two() == false
, the result of0_usize.prev_power_of_two()
is undefined.Credit to @kennytm for the following results table:
wrapping (release)
Alternatives
fn prev_power_of_two(self) -> Self
onNonZero<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 likeNonZero::new().map_or()
.wrapping_prev_power_of_two
because it's unclear what the behavior should be for 0.panic
on 0 inprev_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.pdfC23 \<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):
Second, if there's a concrete solution: