Rust/src/bit_manipulation/binary_count_trailing_zeros.rs at 74f036248b7c583281a0ae2a15aafadb87d912e5 · vil02/Rust · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
/// Counts the number of trailing zeros in the binary representation of a number
///
/// # Arguments
///
/// * `num` - The input number
///
/// # Returns
///
/// The number of trailing zeros in the binary representation
///
/// # Examples
///
/// ```
/// use the_algorithms_rust::bit_manipulation::binary_count_trailing_zeros;
///
/// assert_eq!(binary_count_trailing_zeros(25), 0);
/// assert_eq!(binary_count_trailing_zeros(36), 2);
/// assert_eq!(binary_count_trailing_zeros(16), 4);
/// assert_eq!(binary_count_trailing_zeros(58), 1);
/// ```
pub fn binary_count_trailing_zeros(num: u64) -> u32 {
    if num == 0 {
        return 0;
    }
    num.trailing_zeros()
}

/// Alternative implementation using bit manipulation
///
/// Uses the bit manipulation trick: log2(num & -num)
///
/// # Examples
///
/// ```
/// // This function uses bit manipulation: log2(num & -num)
/// // where num & -num isolates the rightmost set bit
/// # fn binary_count_trailing_zeros_bitwise(num: u64) -> u32 {
/// #     if num == 0 { return 0; }
/// #     let rightmost_set_bit = num & (num.wrapping_neg());
/// #     63 - rightmost_set_bit.leading_zeros()
/// # }
/// assert_eq!(binary_count_trailing_zeros_bitwise(25), 0);
/// assert_eq!(binary_count_trailing_zeros_bitwise(36), 2);
/// assert_eq!(binary_count_trailing_zeros_bitwise(16), 4);
/// ```
#[allow(dead_code)]
pub fn binary_count_trailing_zeros_bitwise(num: u64) -> u32 {
    if num == 0 {
        return 0;
    }

    let rightmost_set_bit = num & (num.wrapping_neg());
    rightmost_set_bit.ilog2()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_basic_cases() {
        assert_eq!(binary_count_trailing_zeros(25), 0);
        assert_eq!(binary_count_trailing_zeros(36), 2);
        assert_eq!(binary_count_trailing_zeros(16), 4);
        assert_eq!(binary_count_trailing_zeros(58), 1);
        assert_eq!(binary_count_trailing_zeros(4294967296), 32);
    }

    #[test]
    fn test_zero() {
        assert_eq!(binary_count_trailing_zeros(0), 0);
    }

    #[test]
    fn test_powers_of_two() {
        assert_eq!(binary_count_trailing_zeros(1), 0);
        assert_eq!(binary_count_trailing_zeros(2), 1);
        assert_eq!(binary_count_trailing_zeros(4), 2);
        assert_eq!(binary_count_trailing_zeros(8), 3);
        assert_eq!(binary_count_trailing_zeros(1024), 10);
    }

    #[test]
    fn test_bitwise_vs_builtin() {
        // Test that bitwise implementation matches built-in trailing_zeros()
        let test_cases = vec![
            0,
            1,
            2,
            3,
            4,
            5,
            6,
            7,
            8,
            16,
            25,
            36,
            58,
            64,
            100,
            128,
            256,
            512,
            1024,
            4294967296,
            u64::MAX - 1,
            u64::MAX,
        ];

        for num in test_cases {
            assert_eq!(
                binary_count_trailing_zeros(num),
                binary_count_trailing_zeros_bitwise(num),
                "Mismatch for input: {num}"
            );
        }
    }
}