Lint suggestion: `manual_bit_width`

[sorairolake]

What it does

Checks for manual implementations of calculating the minimum number of bits required to represent an unsigned integer, and suggests using uint::bit_width instead.

Common manual implementation patterns for this calculation include uint::BITS - n.leading_zeros() or the mathematical expression $\lfloor \log _{2}n\rfloor +1$, where $n > 0$.

The bit_width method will be stabilized in Rust 1.97.0 and will be available for all unsigned primitive integer types and NonZero<T> where T is any unsigned primitive integer type.

Advantage

• Improve readability and clarity compared to manual implementations.
• Eliminate off-by-one errors for $n = 0$ inherent in the mathematical expression $\lfloor \log _{2}n\rfloor +1$.
• Preserve non-zero type information by returning NonZero<u32> instead of u32 for NonZero<T>.

Drawbacks

Requires MSRV 1.97.0.

Example

let n: u32 = 0b1110;

// `u32::BITS` or `32`
let width = u32::BITS - n.leading_zeros();
// or `floor(log2(n)) + 1`
let width = n.checked_ilog2().map_or(0, |n| n + 1);

let n = NonZeroU32::new(0b1110).unwrap();

// `NonZeroU32::BITS` or `32`
let width = NonZeroU32::new(NonZeroU32::BITS - n.leading_zeros()).unwrap();
// or `floor(log2(n)) + 1`
let width = NonZeroU32::new(n.ilog2() + 1).unwrap();

Could be written as:

let n: u32 = 0b1110;
let width = n.bit_width();

let n = NonZeroU32::new(0b1110).unwrap();
let width = n.bit_width();

Comparison with existing lints

No response

Additional Context

• u32::bit_width
• NonZero::bit_width

[alv-around]

@rustbot claim

I will be back with a PR soon :)

[alv-around]

@sorairolake I implement the lint for T::BITS - x.leading_zeros(). However, I have my doubts whether adding ilog2(n) + 1 would be very useful. $$\lfloor \log_2 ⁡ n \rfloor + 1$$ is equivalent to $$$\lceil \log_2 ⁡ n \rceil$$. The mathematical formula can be use in context where no bit manipulation is involved. In those cases, triggering the lint would add confusion instead of clarity.

But happy to extend the lint to x.ilog2() + 1 / x.checked_ilog2().map_or(0, |x| x + 1) ... case,if it gets more support.

[sorairolake]

However, I have my doubts whether adding ilog2(n) + 1 would be very useful.

@alv-around I agree. x.ilog2() + 1 is impractical because it panics when x is zero. x.checked_ilog2().map_or(0, |x| x + 1) is more complex than T::BITS - x.leading_zeros(). Therefore, I also think $\lfloor \log _{2}n\rfloor +1$ is unnecessary.