Add mention that `ilog2` and `checked_ilog2` can be used to get the number of bits in an integer

[sorairolake]

Location

• {integer}::ilog2
• {integer}::checked_ilog2
• NonZero::ilog2

Summary

The standard library of some programming languages has a method to get the number of bits in an integer:

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

The number of bits in binary representation of a positive integer $n$ is the integer part of $1 + \log_2 n$, i.e.

$\lfloor \log_2 n \rfloor + 1$

Rust doesn't have a method like the above, but it does have ilog2 and checked_ilog2. Therefore, we can get the number of bits in an integer by using ilog2 or checked_ilog2 as follows:

// n > 0
assert_eq!(42_u8.ilog2() + 1, 6);

// supports `n == 0`
assert_eq!(u8::MIN.checked_ilog2().map_or(0, |n| n + 1), 0);

// similar to Python's `int.bit_length()`
assert_eq!((-42_i8).unsigned_abs().ilog2() + 1, 6);

I don't think everyone knows that we can get the number of bits in an integer by this way.

Personally, I don't think there's any need to add a method like bits.Len() and int.bit_length() to integer types, since we can get the number of bits in an integer using $\lfloor \log_2 n \rfloor + 1$. However, since the standard library of some programming languages has a method to get the number of bits in an integer, I think this is a feature that is in some demand.

Therefore, I think it would be helpful to mention in the explanation of ilog2 and checked_ilog2 that the number of bits in an integer can be obtained by using $\lfloor \log_2 n \rfloor + 1$.

See also: Rust Internals

[ericlagergren]

Personally, I don't think there's any need to add a method like bits.Len() and int.bit_length() to integer types

I disagree. I've had to write this by hand numerous times, each time wondering why Rust doesn't just have 'uint::bitlen() -> u32`. (I've been meaning to file an ACP or whatever, I just haven't had time to figure out what the process is. It seems complex.)

[sorairolake]

@ericlagergren As far as I know, other programming languages ​​have a method similar to {float}::log2, but I don't think there is a method similar to {integer}::ilog2 in most cases. The only similar method I know is BitOperations.Log2 in .NET.

I think the way to get the number of bits in an integer when using {float}::log2 is as follows:

assert_eq!((42_u8 as f64).log2().floor() as u32 + 1, 6);

This is a bit complicated, but since Rust has {integer}::ilog2, this can be rewritten as:

assert_eq!(42_u8.ilog2() + 1, 6);

This is simple. Also, I think it is known to some extent that the number of bits in an integer can be obtained using $\lfloor \log_2 n \rfloor + 1$. I think adding uint::bitlen() -> u32 would be useful if there was no {integer}::ilog2, but in reality it isn't. Therefore, I don't think there is much benefit to adding uint::bitlen() -> u32 to reduce + 1.

assert_eq!(42_u8.bitlen(), 6);

[ericlagergren]

It's useful for code clarity. bitlen tells me exactly what it's doing.

ilog2() + 1 is pretty straight forward, but it's not correct since typically bitlen(0) == 0

The checked version you posted correctly handles 0, but is fairly obtuse.

[hkBst]

I've used ilog10 + 1 to get the number of decimal digits in a number, but not needed ilog2 for bits yet...

Using leading_zeros seems like a simpler solution to bit_len though:

fn bit_len(n: u64) -> u32 {
    u64::BITS - n.leading_zeros()
}