-
-
Notifications
You must be signed in to change notification settings - Fork 2.6k
Expand file tree
/
Copy pathhamming_distance.rs
More file actions
136 lines (127 loc) · 3.43 KB
/
hamming_distance.rs
File metadata and controls
136 lines (127 loc) · 3.43 KB
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
//! Hamming Distance
//!
//! This module implements the [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance)
//! algorithm for both integers and strings.
//!
//! The Hamming distance between two values is the number of positions at which
//! the corresponding symbols differ.
/// Counts the number of set bits (1s) in a 64-bit unsigned integer.
///
/// # Arguments
///
/// * `value` - The number to count set bits in
///
/// # Returns
///
/// The number of set bits in the value
///
/// # Example
///
/// ```
/// // This is a private helper function
/// let value: u64 = 11; // 1011 in binary has 3 set bits
/// ```
fn bit_count(mut value: u64) -> u64 {
let mut count = 0;
while value != 0 {
if value & 1 == 1 {
count += 1;
}
value >>= 1;
}
count
}
/// Calculates the Hamming distance between two unsigned 64-bit integers.
///
/// The Hamming distance is the number of bit positions at which the
/// corresponding bits differ. This is computed by taking the XOR of the
/// two numbers and counting the set bits.
///
/// # Arguments
///
/// * `a` - The first integer
/// * `b` - The second integer
///
/// # Returns
///
/// The number of differing bits between `a` and `b`
///
/// # Example
///
/// ```
/// use the_algorithms_rust::bit_manipulation::hamming_distance;
///
/// let distance = hamming_distance(11, 2);
/// assert_eq!(distance, 2);
/// ```
pub fn hamming_distance(a: u64, b: u64) -> u64 {
bit_count(a ^ b)
}
/// Calculates the Hamming distance between two strings of equal length.
///
/// The Hamming distance is the number of positions at which the
/// corresponding characters differ.
///
/// # Arguments
///
/// * `a` - The first string
/// * `b` - The second string
///
/// # Returns
///
/// The number of differing characters between `a` and `b`
///
/// # Panics
///
/// Panics if the strings have different lengths
///
/// # Example
///
/// ```
/// use the_algorithms_rust::bit_manipulation::hamming_distance_str;
///
/// let distance = hamming_distance_str("1101", "1111");
/// assert_eq!(distance, 1);
/// ```
pub fn hamming_distance_str(a: &str, b: &str) -> u64 {
assert_eq!(
a.len(),
b.len(),
"Strings must have the same length for Hamming distance calculation"
);
a.chars()
.zip(b.chars())
.filter(|(ch_a, ch_b)| ch_a != ch_b)
.count() as u64
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_bit_count() {
assert_eq!(bit_count(0), 0);
assert_eq!(bit_count(11), 3); // 1011 in binary
assert_eq!(bit_count(15), 4); // 1111 in binary
}
#[test]
fn test_hamming_distance_integers() {
assert_eq!(hamming_distance(11, 2), 2);
assert_eq!(hamming_distance(2, 0), 1);
assert_eq!(hamming_distance(11, 0), 3);
assert_eq!(hamming_distance(0, 0), 0);
}
#[test]
fn test_hamming_distance_strings() {
assert_eq!(hamming_distance_str("1101", "1111"), 1);
assert_eq!(hamming_distance_str("1111", "1111"), 0);
assert_eq!(hamming_distance_str("0000", "1111"), 4);
assert_eq!(hamming_distance_str("alpha", "alphb"), 1);
assert_eq!(hamming_distance_str("abcd", "abcd"), 0);
assert_eq!(hamming_distance_str("dcba", "abcd"), 4);
}
#[test]
#[should_panic(expected = "Strings must have the same length")]
fn test_hamming_distance_strings_different_lengths() {
hamming_distance_str("abc", "abcd");
}
}