look for python in the PATH

[rust-101.git] / solutions / src / bigint.rs

diff --git a/solutions/src/bigint.rs b/solutions/src/bigint.rs
index 0abb6b34fb0ba44b7e2a9a8b9fd1e571aabc18ce..91e3ccf9308df5e3952e8762bb30653a972e86cd 100644 (file)
--- a/solutions/src/bigint.rs
+++ b/solutions/src/bigint.rs
@@ -55,15 +55,35 @@ 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<u64>) -> 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.
+    pub fn inc1(&mut self) {
+        let mut idx = 0;
+        // This loop adds "(1 << idx)". If there is no more carry, we leave.
+        while idx < self.data.len() {
+            let cur = self.data[idx];
+            let sum = u64::wrapping_add(cur, 1);
+            self.data[idx] = sum;
+            if sum >= cur {
+                // No overflow, we are done.
+                return;
+            } else {
+                // We need to go on.
+                idx += 1;
+            }
+        }
+        // If we came here, there is a last carry to add
+        self.data.push(1);
+    }
+
     /// Increments the number by "by".
     pub fn inc(&mut self, mut by: u64) {
         let mut idx = 0;
@@ -111,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() {
@@ -191,6 +212,7 @@ impl ops::Add<BigInt> for BigInt {
 
 #[cfg(test)]
 mod tests {
+    use std::u64;
     use super::overflowing_add;
     use super::BigInt;
 
@@ -203,6 +225,21 @@ mod tests {
         assert_eq!(overflowing_add(1 << 63, (1 << 63) -1 , true), (0, true));
     }
 
+    #[test]
+    fn test_inc1() {
+        let mut b = BigInt::new(0);
+        b.inc1();
+        assert_eq!(b, BigInt::new(1));
+        b.inc1();
+        assert_eq!(b, BigInt::new(2));
+
+        b = BigInt::new(u64::MAX);
+        b.inc1();
+        assert_eq!(b, BigInt::from_vec(vec![0, 1]));
+        b.inc1();
+        assert_eq!(b, BigInt::from_vec(vec![1, 1]));
+    }
+
     #[test]
     fn test_power_of_2() {
         assert_eq!(BigInt::power_of_2(0), BigInt::new(1));