ACP: Add {u8,u16,u32,u64,u128,usize}::bit_len

[sorairolake]

Proposal

Problem statement

Currently, Rust does not have a method that return the minimum number of bits required to represent an integer. I think it would be useful to have a method that can do this easily and directly.

I think the bit length of unsigned integers is always clear, since these are never negative integers. I don't think it should be implemented for signed integers, because the bit length of negative integers is not clear (include the sign bit or not).

Methods for this purpose appear to exist in the standard library of several languages:

• int.bit_length() in Python
• bits.Len() in Go
• Integer.bit_length in Ruby
• stdc_bit_width in C23

Note

int.bit_length() in Python and Integer.bit_length in Ruby have the same purpose as this proposal, but for arbitrary-sized integers (not just for unsigned integers).

There may be a better name for this method.

Motivating examples or use cases

The following code calculates the coded dictionary size of the lzip compressed format from the dictionary size of LZMA:

const MIN_DICT_SIZE: u32 = 1 << 12;

fn coded_dict_size(dict_size: u32) -> u8 {
    let mut ds = (dict_size - 1).bit_len();

    if dict_size > MIN_DICT_SIZE {
        let base = 1_u32.checked_shl(dict_size).unwrap_or_default();
        let frac = base / 16;

        for i in (1..=7).rev() {
            if (base - (i * frac)) >= ds {
                ds |= i << 5;
            }
        }
    }
    ds as u8
}

Solution sketch

impl {u8,u16,u32,u64,u128,usize} {
    /// Returns the minimum number of bits required to represent `self`.
    ///
    /// This method returns zero if `self` is zero.
    ///
    /// # Examples
    ///
    /// Basic usage:
    ///
    /// ```
    /// assert_eq!(0u32.bit_len(), 0);
    /// assert_eq!(7u32.bit_len(), 3);
    /// assert_eq!(u32::MAX.bit_len(), 32);
    /// ```
    pub const fn bit_len(self) -> u32 {
        Self::BITS - self.leading_zeros()
    }
}

Alternatives

If you use existing APIs, you can calculate the bit length in the following:

{u8,u16,u32,u64,u128,usize}::BITS - n.leading_zeros()

n.checked_ilog2().map_or(0, |n| n + 1)

I think these are simple enough, but it would be easier to understand if there is a method that can be calculated directly.

In particular, for people who often use other languages ​​rather than Rust, I think it would be useful to have a method to directly calculate the bit length. Because, as I have already mentioned, other languages ​​have methods to directly calculate the bit length.

Links and related work

• https://internals.rust-lang.org/t/add-methods-that-return-the-number-of-bits-necessary-to-represent-an-integer-in-binary-to-the-standard-library/21870
• https://internals.rust-lang.org/t/add-bit-len-function/23031
• Add mention that ilog2 and checked_ilog2 can be used to get the number of bits in an integer rust#133101

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.

[okaneco]

Related ACP for bit_width and seeks to add it for NonZero unsigned types filed almost a year ago.
#397

Another ACP was filed and accepted since then which supersedes the bit_floor section of that ACP.
#467

[cuviper]

• int.bit_length() in Python
• Integer.bit_length in Ruby

Note that these two are arbitrary-sized integers, more like BigInt which does have a bits method.

[Amanieu]

We discussed this in the @rust-lang/libs-api meeting. We're happy to add this under the name bit_width which is more consistent with C (which uses fixed-width integers).

Please open a tracking issue and open a PR to rust-lang/rust to add it as an unstable feature. You can close this ACP once the tracking issue has been created.

[sorairolake]

Thanks. I've opened the tracking issue rust-lang/rust#142326.