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(value: u128) -> bool {
    value.count_zeros() == value.trailing_zeros()
}