Check whether an integer's leftmost bits are ones in Rust

Question

I'm trying to validate if an integer represents a valid IPv6 mask, which boils down to checking if all the left-most bits of an u128 are 1s, and all the right-most bits are 0s. For instance:

• 0 is valid
• 0xffff_ffff_ffff_ffff_ffff_ffff_ffff_ffff is valid
• 0xffff_ffff_ffff_ffff_0000_0000_0000_0000 is valid
• 0xffff_ffff_fff8_0000_0000_0000_0000_0000 is valid
• 0xffff_ffff_fffe_0000_0000_0000_0000_0000 is valid

but:

• 1 is invalid (its representation is 0x0000_0000_0000_0000_0000_0000_0000_0001)
• 0x0fff_ffff_ffff_ffff_ffff_ffff_ffff_ffff is invalid
• 0xffff_ffff_fff1_0000_0000_0000_0000_0000 is invalid

Here is the function:

/// Check whether the given integer represents a valid IPv6 mask.
/// A valid IP mask is an integer which left-most bits are 1s, and right-most bits are 0s.
fn is_valid_ipv6_mask(value: u128) -> bool {
 // flag to check if we're currently processing 1s or 0s
 let mut count_ones = true;
 // check each byte starting from the left.
 for byte_index in (0..=15).rev() {
 let x = (value >> (byte_index * 8)) & 0xff;
 match x {
 // We're processing 1s and this byte is 0b1111_1111
 0xff if count_ones => continue,
 // We're processing 0s and this byte is 0b0000_0000
 0x00 if !count_ones => continue,
 // We're processing 1s and this byte is 0b0000_0000.
 // That means all the remaining bytes should be 0 for this integer
 // to be a valid mask
 0x00 if count_ones => {
 count_ones = false;
 continue;
 }
 // We're processsing 1s and this byte has at least a 1, so we have
 // to check bit by bit that the left-most bits are 1s and the
 // right-most bits are 0s
 byte if byte > 0 && count_ones => {
 let mut bit_index = 7;
 while (byte >> bit_index) & 1 == 1 {
 // This does not overflow, because we now this byte has at
 // least a 0 somewhere
 bit_index -= 1
 }
 // At this point, all the bits should be 0s
 count_ones = false;
 for i in 0..bit_index {
 if (byte >> i) & 1 == 1 {
 return false;
 }
 }
 }
 // Any other case is an error
 _ => return false,
 }
 }
 true
}

And to test it:

fn main() {
 assert!(is_valid_ipv6_mask(0));
 assert!(is_valid_ipv6_mask(
 0xffff_ffff_ffff_ffff_ffff_ffff_ffff_ffff
 ));
 assert!(is_valid_ipv6_mask(
 0xffff_0000_0000_0000_0000_0000_0000_0000
 ));
 assert!(is_valid_ipv6_mask(
 0xff80_0000_0000_0000_0000_0000_0000_0000
 ));
 assert!(!is_valid_ipv6_mask(
 0xff01_0000_0000_0000_0000_0000_0000_0000
 ));
 assert!(!is_valid_ipv6_mask(
 0xffff_0000_ffff_ffff_ffff_ffff_ffff_ffff
 ));
}

Link to playground.

The problem is that have the feeling that there must be a much simple solution to this problem. After all, bit operations are what computers do, I can't believe there's not more concise and more efficient way to check if an integer is all 1s then all 0s.

Answer 1

The problem is that have the feeling that there must be a much simple solution to this problem.

You're right! Integers in Rust have many useful bitwise operations (as well as other useful ones like wrapping and saturating arithmetic), most of which are exposed as methods on the type. To see the full list, look at the generated documentation for the type, e.g. u128.

Here's a simple way to write is_valid_ipv6_mask:

fn is_valid_ipv6_mask_simple(value: u128) -> bool {
 value.count_zeros() == value.trailing_zeros()
}

You may be able to think of other ones based on bitwise functions. Ways of checking "trailing bits" are often based on adding (or subtracting) 1, since that inverts all the trailing 1 (or 0) bits and the rightmost 0 (or 1) bit while leaving the rest of the value untouched. Here's what I came up with:

fn is_valid_ipv6_mask_bitwise(value: u128) -> bool {
 !value & (!value + 1) == 0
}

This is more difficult to read, but can be implemented very efficiently. Interestingly, I found that the compiler rewrote it under optimization to the equivalent form value | (value - 1) == ~0.