X-Git-Url: https://git.ralfj.de/rust-101.git/blobdiff_plain/369875f931d841112dd2b6651fc968bb6c569cdb..74a318b63dab5abd344f17bf71932f87f8e349ab:/solutions/src/bigint.rs?ds=inline diff --git a/solutions/src/bigint.rs b/solutions/src/bigint.rs index 80ac63d..120ae6c 100644 --- a/solutions/src/bigint.rs +++ b/solutions/src/bigint.rs @@ -55,16 +55,16 @@ impl BigInt { } } - /// Construct a BigInt from a vector of 64-bit "digits", with the last significant digit being first + /// Construct a BigInt from a vector of 64-bit "digits", with the last significant digit being first. Solution to 05.1. pub fn from_vec(mut v: Vec) -> Self { - // remove trailing zeroes + // remove trailing zeros while v.len() > 0 && v[v.len()-1] == 0 { v.pop(); } BigInt { data: v } } - /// Increments the number by 1. Solution to 05.1. + /// Increments the number by 1. pub fn inc1(&mut self) { let mut idx = 0; // This loop adds "(1 << idx)". If there is no more carry, we leave. @@ -131,6 +131,7 @@ impl PartialEq for BigInt { } impl Minimum for BigInt { + // This is essentially the solution to 06.1. fn min<'a>(&'a self, other: &'a Self) -> &'a Self { debug_assert!(self.test_invariant() && other.test_invariant()); if self.data.len() < other.data.len() { @@ -165,12 +166,14 @@ impl fmt::Debug for BigInt { impl<'a, 'b> ops::Add<&'a BigInt> for &'b BigInt { type Output = BigInt; fn add(self, rhs: &'a BigInt) -> Self::Output { - let mut result_vec:Vec = Vec::with_capacity(cmp::max(self.data.len(), rhs.data.len())); + let max_len = cmp::max(self.data.len(), rhs.data.len()); + let mut result_vec:Vec = Vec::with_capacity(max_len); let mut carry:bool = false; // the carry bit - for (i, val) in (&self.data).into_iter().enumerate() { + for i in 0..max_len { // compute next digit and carry + let lhs_val = if i < self.data.len() { self.data[i] } else { 0 }; let rhs_val = if i < rhs.data.len() { rhs.data[i] } else { 0 }; - let (sum, new_carry) = overflowing_add(*val, rhs_val, carry); + let (sum, new_carry) = overflowing_add(lhs_val, rhs_val, carry); // store them result_vec.push(sum); carry = new_carry; @@ -179,8 +182,8 @@ impl<'a, 'b> ops::Add<&'a BigInt> for &'b BigInt { result_vec.push(1); } // We know that the invariant holds: overflowing_add would only return (0, false) if - // the arguments are (0, 0, false), but we know that in the last iteration, `val` is the - // last digit of `self` and hence not 0. + // the arguments are (0, 0, false), but we know that in the last iteration, one od the two digits + // is the last of its number and hence not 0. BigInt { data: result_vec } } } @@ -224,6 +227,14 @@ mod tests { assert_eq!(overflowing_add(1 << 63, (1 << 63) -1 , true), (0, true)); } + #[test] + fn test_add() { + let b1 = BigInt::new(1 << 32); + let b2 = BigInt::from_vec(vec![0, 1]); + + assert_eq!(&b1 + &b2, BigInt::from_vec(vec![1 << 32, 1])); + } + #[test] fn test_inc1() { let mut b = BigInt::new(0);