Add prev_power_of_two

libs
1

We have next_power_of_two for the unsigned integer types in Rust. The definition (ignoring overflow):

Returns the smallest power of two greater than or equal to self .

I propose we add prev_power_of_two with the following definition:

Returns the greatest power of two less than or equal to self.

In C++20 this pair of functions exists as bit_ceil and bit_floor respectively.

The only small uncertainty I have with this function is what to do in case it gets called on 0. I believe that simply returning 0 is the sanest option - this is also what C++20 does.

I propose the following implementation (and similar for other sizes):

/// Returns the greatest power of two less than or equal to `self`, or 0 otherwise.
pub const fn prev_power_of_two(n: u64) -> u64 {
    // n = 0 gives highest_bit_set_idx = 0.
    let highest_bit_set_idx = 63 - (n|1).leading_zeros();
    // Binary AND of highest bit with n is a no-op, except zero gets wiped.
    (1 << highest_bit_set_idx) & n
}
10 Likes
2

Note I am not on any team but I think for things like this a direct impl PR is the current expected method for these sorts of things.

Sidenote: I like this API

1 Like
3

Note that 0_usize.is_power_of_two() is false, which is one of the things blocking stabilization of wrapping_next_power_of_two.

Another alternative would be to punt on the problem by defining these on NonZeroU# instead -- leading_zeros and is_power_of_two and such are already implemented there. That way the postcondition is simple, and the implementation might be tighter.

3 Likes
5

Note that 0_usize.is_power_of_two() is false.

I am aware, and that's correct.

Another alternative would be to punt on the problem by defining these on NonZeroU# instead -- leading_zeros and is_power_of_two and such are already implemented there.

I think adding an implementation there as well would make sense (that wouldn't have to specify some behavior for 0). But only defining it there I think would ultimately shove the (incredibly minor for us, but possibly significant for them) problem to the user in two ways:

  1. They're unlikely to look for the function in NonZeroU# to begin with, making them probably hand-roll this somewhat error-prone function (or worse, skip the intrinsic altogether and write a loop).
  2. They're unlikely to have their data in a NonZeroU# type, meaning they'll have to convert, even if they don't care about the behavior on zero, or the current behavior is what they want. And this conversion is likely to be more inefficient (and introducing unnecessary branches) than the carefully tuned solution I proposes which only uses one extra OR and one AND operation.
2 Likes
6

I think prev_power_of_two(0) == 0 is the sanest solution. I could see an argument for maybe panicking in debug and returning 0 in release, similar to how next_power_of_two handles overflow, in which case I'd like to have a non-panicking version available too (wrapping_prev_power_of_two? there's not really any wrapping involved but if I were looking for a no-panic version the first thing I'd search for is a variant with that name).

1 Like
7

Would having the signature be fn prev_power_of_two(src: T) -> Option<T> and the a other unsafe fn unchecked_prev_power_of_two(src: T) -> T?

8

Would having the signature be fn prev_power_of_two(src: T) -> Option<T> and the a other unsafe fn unchecked_prev_power_of_two(src: T) -> T ?

Just defining the behavior at zero will be faster than either of those solutions, and there's nothing unsafe about it.

The Option<T> behavior if desired could be achieved by the user by calling NonZeroU#(src).map(|x| x.prev_power_of_two()).

1 Like
9

While that's true, note that next_power_of_two is intentionally careful to trigger overflow behaviour:

even though it also wouldn't be unsafe to wrap for that one either, so I think a prev_power_of_two should also have that "panics on debug if overflows" behaviour.

10

So I think a prev_power_of_two should also have that "panics on debug if overflows" behaviour.

And I think the operation would be more useful if we simply define it for 0. I would posture that there's almost no one that wants the panicking version, and if they do they can get it from NonZeroU#::new(x).unwrap().prev_power_of_two(). It's much harder to go the other way around - to get the non-panicking version from the panicking version in an efficient manner.

Note that there isn't really a good sensible answer for the next case, but the prev case in my opinion there is. In C++ the operation is called bit_floor which even removes any sort of unclarity. I only proposed this function under this name because next_power_of_two already exists. In a vacuum I would call it highest_bit_set, in which case the 0 -> 0 behavior is even less controversial, perhaps that name would be better despite the existence of next_power_of_two?

3 Likes
11

It might be useful to see some concrete use cases for this function, to help judge which edge-case behavior is most useful in practice.

I think that would still be equally weird:

let i = highest_bit_set(n);
// Can I now assume that bit `i` is set to 1?
2 Likes
12 
let i = highest_bit_set(n);
// Can I now assume that bit `i` is set to 1?

Eh for the record, i would be an integer with the same highest bit set as n (or none if n has no bits set), so saying "bit i" doesn't make sense. It's not an index. It's a mask, if you will. Or clear_all_but_highest_bit.

13

Ah, right. Sorry, I got confused.

14

One thing I've used stuff like this for is for popping off the high bit. Some formats/encodings signal the length of the integer via the high bit (kinda like UTF-8, but the inverse). The one I'm most familiar with is EBML/Matroska, in which the number of leading zeros tells you how many bytes the integer is. But the first bit set doesn't participate in the value.

For example, a two-byte value is encoded as 01xx xxxx xxxx xxxx. You can use leading_zeros() to know how many bytes to read. But you still have to clear that top bit. The OP's prev_power_of_two() is a nice and convenient way to do that (via XOR).

All-bits-zero isn't a valid size prefix in EBML, so unfortunately I can't use this as an example to justify what prev_power_of_two(0) should evaluate to. Personally I think evaluating to zero in that situation is easiest, because when I'm bit-banging I pretty much always want "dumb" bit operations that don't try to do clever things like panic or return an option (in other words: bits in, bits out; don't give me some different data type or behavior). But like I said, I can't really use the EBML example to justify that, unfortunately.

2 Likes
15

Should prev_power_of_two(1) == 1?

16

Yes. I think that's another reason not to call it prev, because if you pass it a power of two it returns the same value.

I think something involving highest_bit would be more evocative. That then makes the behavior on zero more reasonable as well: if there are no bits set, it returns no bits.

17

Note that next_power_of_two already has the same issue, since 1.next_power_of_two() == 1.

2 Likes
18

I realize. And consistency has value as well. But I think between that and the behavior on zero, a highest_bit name seems clearer.

I also think there isn't a lot of value in bikeshedding the name here. I'd suggest picking a name, filing a PR, providing a rationale for the behavior on 0, and providing rationale and alternatives for the name. I think the method itself is likely to be accepted, and the naming bikeshed might as well happen just once rather than two or more times.

3 Likes
19

Sorry for bikeshedding more, but I prefer highest_one to highest_bit, and it is also more consistent with the naming of count_ones, leading_ones and trailing_ones.

1 Like
20

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.