Added bit insertion

tim-harding · Sep 2, 2023 · ca4d1c2 · ca4d1c2
1 parent 1fa64bf
commit ca4d1c2
Show file tree

Hide file tree

Showing 6 changed files with 51 additions and 0 deletions.
diff --git a/src/problems/_05_bit_manipulation/_01_insertion.rs b/src/problems/_05_bit_manipulation/_01_insertion.rs
@@ -0,0 +1,34 @@
+pub trait Insertion {
+    /// Write a method to insert M into N such that M starts at bit j and ends
+    /// at bit i. For example,
+    /// INPUT:  N = 10000000000, M = 10011, i = 2, j = 6
+    /// OUTPUT:     10001001100
+    fn insertion(n: u32, m: u32, i: usize, j: usize) -> u32;
+}
+
+struct Solution;
+
+impl Insertion for Solution {
+    fn insertion(n: u32, m: u32, i: usize, j: usize) -> u32 {
+        // Your solution here
+        use crate::solutions::_05_bit_manipulation::_01_insertion as solutions;
+        solutions::Solution::insertion(n, m, i, j)
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn inserts_correctly() {
+        assert_eq!(
+            Solution::insertion(0b10000000000, 0b10011, 2, 6),
+            0b10001001100
+        );
+        assert_eq!(
+            Solution::insertion(0b11111111111, 0b0101010, 2, 8),
+            0b11010101011
+        );
+    }
+}
diff --git a/src/problems/_05_bit_manipulation/mod.rs b/src/problems/_05_bit_manipulation/mod.rs
@@ -0,0 +1 @@
+pub mod _01_insertion;
diff --git a/src/problems/mod.rs b/src/problems/mod.rs
@@ -1 +1,2 @@
 pub mod _01_arrays_and_strings;
+pub mod _05_bit_manipulation;
diff --git a/src/solutions/_05_bit_manipulation/_01_insertion.rs b/src/solutions/_05_bit_manipulation/_01_insertion.rs
@@ -0,0 +1,13 @@
+use crate::problems::_05_bit_manipulation::_01_insertion::Insertion;
+
+pub struct Solution;
+
+impl Insertion for Solution {
+    fn insertion(n: u32, m: u32, i: usize, j: usize) -> u32 {
+        let m_mask = u32::MAX << (j - i + 1);
+        let m = (m & !m_mask) << i;
+        let n_mask = m_mask << i | !(u32::MAX << i);
+        let n = n & n_mask;
+        m | n
+    }
+}
diff --git a/src/solutions/_05_bit_manipulation/mod.rs b/src/solutions/_05_bit_manipulation/mod.rs
@@ -0,0 +1 @@
+pub mod _01_insertion;
diff --git a/src/solutions/mod.rs b/src/solutions/mod.rs
@@ -1 +1,2 @@
 pub mod _01_arrays_and_strings;
+pub mod _05_bit_manipulation;