Add gcd bit (keon#609)

* [ADD] Added trailing_zero and gcd_bit. * [ADD] Added test case for trailing_zero and gcd_bit * [EDIT] Added spaces to code to easier to read.
vdsmitnov52 · Dec 6, 2019 · 9b1a497 · 9b1a497
1 parent a9aad22
commit 9b1a497
Show file tree

Hide file tree

Showing 2 changed files with 48 additions and 1 deletion.
diff --git a/algorithms/maths/gcd.py b/algorithms/maths/gcd.py
@@ -10,3 +10,42 @@ def gcd(a, b):
 def lcm(a, b):
     """Computes the lowest common multiple of integers a and b."""
     return a * b / gcd(a, b)
+
+
+"""
+Given a positive integer x, computes the number of trailing zero of x.
+Example
+Input : 34(100010)
+           ~~~~~^
+Output : 1
+
+Input : 40(101000)
+           ~~~^^^
+Output : 3
+"""
+
+def trailing_zero(x):
+    cnt = 0
+    while x and not x & 1:
+        cnt += 1
+        x >>= 1
+    return cnt
+
+"""
+Given two non-negative integer a and b, 
+computes the greatest common divisor of a and b using bitwise operator.
+"""
+
+def gcd_bit(a, b):
+    tza = trailing_zero(a)
+    tzb = trailing_zero(b)
+    a >>= tza
+    b >>= tzb
+    while b:
+        if a < b: 
+            a, b = b, a
+        a -= b
+        a >>= trailing_zero(a)
+    return a << min(tza, tzb)
+
+
diff --git a/tests/test_maths.py b/tests/test_maths.py
@@ -4,7 +4,7 @@
     euler_totient,
     extended_gcd,
     factorial, factorial_recur,
-    gcd, lcm,
+    gcd, lcm, trailing_zero, gcd_bit,
     gen_strobogrammatic, strobogrammatic_in_range,
     is_strobogrammatic, is_strobogrammatic2,
     modular_exponential,
@@ -101,6 +101,13 @@ def test_gcd(self):
     def test_lcm(self):
         self.assertEqual(24, lcm(8, 12))
 
+    def test_trailing_zero(self):
+        self.assertEqual(1, trailing_zero(34))
+        self.assertEqual(3, trailing_zero(40))
+
+    def test_gcd_bit(self):
+        self.assertEqual(4, gcd_bit(8, 12))
+        self.assertEqual(1, gcd(13, 17))
 
 class TestGenerateStroboGrammatic(unittest.TestCase):
     """[summary]
@@ -320,3 +327,4 @@ def test_cosine_similarity(self):
 
 if __name__ == "__main__":
     unittest.main()
+