Function compiler_builtins::int::specialized_div_rem::u64_normalization_shift

fn u64_normalization_shift(
    duo: u64,
    div: u64,
    full_normalization: bool
) -> usize

Finds the shift left that the divisor div would need to be normalized for a binary long division step with the dividend duo. NOTE: This function assumes that these edge cases have been handled before reaching it: if div == 0 { panic!("attempt to divide by zero") } if duo < div { return (0, duo) }

Normalization is defined as (where shl is the output of this function): if duo.leading_zeros() != (div << shl).leading_zeros() { // If the most significant bits ofduoanddiv << shlare not in the same place, // thendiv << shlhas one more leading zero thanduo. assert_eq!(duo.leading_zeros() + 1, (div << shl).leading_zeros()); // Also, 2*(div << shl)is not more thanduo(otherwise the first division step // would not be able to clear the msb ofduo) assert!(duo < (div << (shl + 1))); } if full_normalization { // Some algorithms do not need "full" normalization, which means that duois // larger thandiv << shlwhen the most significant bits are aligned. assert!((div << shl) <= duo); }

Note: If the software bisection algorithm is being used in this function, it happens that full normalization always occurs, so be careful that new algorithms are not invisibly depending on this invariant when full_normalization is set to false.