Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit7a261d7

Browse files
feat: add binary count trailing zeros algorithm (#972)
1 parent5c4593c commit7a261d7

File tree

3 files changed

+122
-0
lines changed

3 files changed

+122
-0
lines changed

‎DIRECTORY.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,7 @@
2626
*[Reverse Bits](https://github.com/TheAlgorithms/Rust/blob/master/src/bit_manipulation/reverse_bits.rs)
2727
*[Sum of Two Integers](https://github.com/TheAlgorithms/Rust/blob/master/src/bit_manipulation/sum_of_two_integers.rs)
2828
*[Swap Odd and Even Bits](https://github.com/TheAlgorithms/Rust/blob/master/src/bit_manipulation/swap_odd_even_bits.rs)
29+
*[Trailing Zeros](https://github.com/TheAlgorithms/Rust/blob/master/src/bit_manipulation/binary_count_trailing_zeros.rs)
2930
*[Two's Complement](https://github.com/TheAlgorithms/Rust/blob/master/src/bit_manipulation/twos_complement.rs)
3031
* Ciphers
3132
*[AES](https://github.com/TheAlgorithms/Rust/blob/master/src/ciphers/aes.rs)
Lines changed: 119 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,119 @@
1+
/// Counts the number of trailing zeros in the binary representation of a number
2+
///
3+
/// # Arguments
4+
///
5+
/// * `num` - The input number
6+
///
7+
/// # Returns
8+
///
9+
/// The number of trailing zeros in the binary representation
10+
///
11+
/// # Examples
12+
///
13+
/// ```
14+
/// use the_algorithms_rust::bit_manipulation::binary_count_trailing_zeros;
15+
///
16+
/// assert_eq!(binary_count_trailing_zeros(25), 0);
17+
/// assert_eq!(binary_count_trailing_zeros(36), 2);
18+
/// assert_eq!(binary_count_trailing_zeros(16), 4);
19+
/// assert_eq!(binary_count_trailing_zeros(58), 1);
20+
/// ```
21+
pubfnbinary_count_trailing_zeros(num:u64) ->u32{
22+
if num ==0{
23+
return0;
24+
}
25+
num.trailing_zeros()
26+
}
27+
28+
/// Alternative implementation using bit manipulation
29+
///
30+
/// Uses the bit manipulation trick: log2(num & -num)
31+
///
32+
/// # Examples
33+
///
34+
/// ```
35+
/// // This function uses bit manipulation: log2(num & -num)
36+
/// // where num & -num isolates the rightmost set bit
37+
/// # fn binary_count_trailing_zeros_bitwise(num: u64) -> u32 {
38+
/// # if num == 0 { return 0; }
39+
/// # let rightmost_set_bit = num & (num.wrapping_neg());
40+
/// # 63 - rightmost_set_bit.leading_zeros()
41+
/// # }
42+
/// assert_eq!(binary_count_trailing_zeros_bitwise(25), 0);
43+
/// assert_eq!(binary_count_trailing_zeros_bitwise(36), 2);
44+
/// assert_eq!(binary_count_trailing_zeros_bitwise(16), 4);
45+
/// ```
46+
#[allow(dead_code)]
47+
pubfnbinary_count_trailing_zeros_bitwise(num:u64) ->u32{
48+
if num ==0{
49+
return0;
50+
}
51+
52+
let rightmost_set_bit = num&(num.wrapping_neg());
53+
63 - rightmost_set_bit.leading_zeros()
54+
}
55+
56+
#[cfg(test)]
57+
mod tests{
58+
usesuper::*;
59+
60+
#[test]
61+
fntest_basic_cases(){
62+
assert_eq!(binary_count_trailing_zeros(25),0);
63+
assert_eq!(binary_count_trailing_zeros(36),2);
64+
assert_eq!(binary_count_trailing_zeros(16),4);
65+
assert_eq!(binary_count_trailing_zeros(58),1);
66+
assert_eq!(binary_count_trailing_zeros(4294967296),32);
67+
}
68+
69+
#[test]
70+
fntest_zero(){
71+
assert_eq!(binary_count_trailing_zeros(0),0);
72+
}
73+
74+
#[test]
75+
fntest_powers_of_two(){
76+
assert_eq!(binary_count_trailing_zeros(1),0);
77+
assert_eq!(binary_count_trailing_zeros(2),1);
78+
assert_eq!(binary_count_trailing_zeros(4),2);
79+
assert_eq!(binary_count_trailing_zeros(8),3);
80+
assert_eq!(binary_count_trailing_zeros(1024),10);
81+
}
82+
83+
#[test]
84+
fntest_bitwise_vs_builtin(){
85+
// Test that bitwise implementation matches built-in trailing_zeros()
86+
let test_cases =vec![
87+
0,
88+
1,
89+
2,
90+
3,
91+
4,
92+
5,
93+
6,
94+
7,
95+
8,
96+
16,
97+
25,
98+
36,
99+
58,
100+
64,
101+
100,
102+
128,
103+
256,
104+
512,
105+
1024,
106+
4294967296,
107+
u64::MAX -1,
108+
u64::MAX,
109+
];
110+
111+
for numin test_cases{
112+
assert_eq!(
113+
binary_count_trailing_zeros(num),
114+
binary_count_trailing_zeros_bitwise(num),
115+
"Mismatch for input: {num}"
116+
);
117+
}
118+
}
119+
}

‎src/bit_manipulation/mod.rs‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,5 @@
11
mod binary_coded_decimal;
2+
mod binary_count_trailing_zeros;
23
mod counting_bits;
34
mod find_previous_power_of_two;
45
mod highest_set_bit;
@@ -10,6 +11,7 @@ mod swap_odd_even_bits;
1011
mod twos_complement;
1112

1213
pubuseself::binary_coded_decimal::binary_coded_decimal;
14+
pubuseself::binary_count_trailing_zeros::binary_count_trailing_zeros;
1315
pubuseself::counting_bits::count_set_bits;
1416
pubuseself::find_previous_power_of_two::find_previous_power_of_two;
1517
pubuseself::highest_set_bit::find_highest_set_bit;

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp