Repository: keon/algorithms
Pull request #253 (2018-04-23 12:43:45)

Add some bit manipulation
PR for adding some bit manipulation. 
Relate to #241 

goswami-rahul: @danghai check out another method I added.
danghai: @goswami-rahul Oh it is better my solution with O(1)
danghai: It is good to merge now.

Patch:
diff --git a/README.md b/README.md
index 9635856..d659d56 100644
--- a/README.md
+++ b/README.md
@@ -73,6 +73,12 @@ For running all tests write down:
     - [single_number](bit/single_number.py)
     - [subsets](bit/subsets.py)
     - [add_bitwise_operator](bit/add_bitwise_operator.py)
+    - [bit_operation](bit/bit_operation.py)
+    - [swap_pair](bit/swap_pair.py)
+    - [find_difference](bit/find_difference.py)
+    - [has_alternative_bit](bit/has_alternative_bit.py)
+    - [insert_bit](bit/insert_bit.py)
+    - [remove_bit](bit/remove_bit.py)
 - [calculator](calculator)
     - [math_parser](calculator/math_parser.py)
 - [dfs](dfs)
diff --git a/bit/bit_operation.py b/bit/bit_operation.py
new file mode 100644
index 0000000..58f7d75
--- /dev/null
+++ b/bit/bit_operation.py
@@ -0,0 +1,37 @@
+"""
+Fundamental bit operation:
+    get_bit(num, i): get an exact bit at specific index
+    set_bit(num, i): set a bit at specific index
+    clear_bit(num, i): clear a bit at specific index
+    update_bit(num, i, bit): update a bit at specific index
+"""
+
+"""
+This function shifts 1 over by i bits, creating a value being like 0001000. By
+performing an AND with num, we clear all bits other than the bit at bit i.
+Finally we compare that to 0
+"""
+def get_bit(num, i):
+    return (num & (1 << i)) != 0
+
+"""
+This function shifts 1 over by i bits, creating a value being like 0001000. By
+performing an OR with num, only value at bit i will change.
+"""
+def set_bit(num, i):
+    return num | (1 << i)
+
+"""
+This method operates in almost the reverse of set_bit
+"""
+def clear_bit(num, i):
+    mask = ~(1 << i)
+    return num & mask
+
+"""
+To set the ith bit to value, we first clear the bit at position i by using a
+mask. Then, we shift the intended value. Finally we OR these two numbers
+"""
+def update_bit(num, i, bit):
+    mask = ~(1 << i)
+    return (num & mask) | (bit << i)
diff --git a/bit/find_difference.py b/bit/find_difference.py
new file mode 100644
index 0000000..67f2f06
--- /dev/null
+++ b/bit/find_difference.py
@@ -0,0 +1,28 @@
+"""
+Given two strings s and t which consist of only lowercase letters.
+String t is generated by random shuffling string s and then add one more letter
+at a random position. Find the letter that was added in t.
+
+For example:
+Input:
+s = "abcd"
+t = "abecd"
+Output: 'e'
+
+Explanation:
+'e' is the letter that was added.
+"""
+
+"""
+We use the characteristic equation of XOR.
+A xor B xor C = A xor C xor B
+If A == C, then A xor C = 0
+and then, B xor 0 =  B
+"""
+def find_difference(s, t):
+    ret = 0
+    for ch in s + t:
+        # ord(ch) return an integer representing the Unicode code point of that character
+        ret = ret ^ ord(ch)
+    # chr(i) Return the string representing a character whose Unicode code point is the integer i
+    return chr(ret)
diff --git a/bit/has_alternative_bit.py b/bit/has_alternative_bit.py
new file mode 100644
index 0000000..ade2f56
--- /dev/null
+++ b/bit/has_alternative_bit.py
@@ -0,0 +1,38 @@
+"""
+Given a positive integer, check whether it has alternating bits: namely,
+if two adjacent bits will always have different values.
+
+For example:
+Input: 5
+Output: True because the binary representation of 5 is: 101.
+
+Input: 7
+Output: False because the binary representation of 7 is: 111.
+
+Input: 11
+Output: False because the binary representation of 11 is: 1011.
+
+Input: 10
+Output: True because The binary representation of 10 is: 1010.
+"""
+
+# Time Complexity - O(number of bits in n)
+def has_alternative_bit(n):
+    first_bit = 0
+    second_bit = 0
+    while n:
+        first_bit = n & 1
+        if n >> 1:
+            second_bit = (n >> 1) & 1
+            if not first_bit ^ second_bit:
+                return False
+        else:
+            return True
+        n = n >> 1
+    return True    
+
+# Time Complexity - O(1)
+def has_alternative_bit_fast(n):
+    mask1 = int('aaaaaaaa', 16)  # for bits ending with zero (...1010)
+    mask2 = int('55555555', 16)  # for bits ending with one  (...0101)
+    return mask1 == (n + (n ^ mask1)) or mask2 == (n + (n ^ mask2))
diff --git a/bit/insert_bit.py b/bit/insert_bit.py
new file mode 100644
index 0000000..f799489
--- /dev/null
+++ b/bit/insert_bit.py
@@ -0,0 +1,44 @@
+"""
+Insertion:
+
+insert_one_bit(num, bit, i): insert exact one bit at specific position
+For example:
+
+Input: num = 10101 (21)
+insert_one_bit(num, 1, 2): 101101 (45)
+insert_one_bit(num, 0 ,2): 101001 (41)
+insert_one_bit(num, 1, 5): 110101 (53)
+insert_one_bit(num, 1, 0): 101011 (43)
+
+insert_mult_bits(num, bits, len, i): insert multiple bits with len at specific position
+For example:
+
+Input: num = 101 (5)
+insert_mult_bits(num, 7, 3, 1): 101111 (47)
+insert_mult_bits(num, 7, 3, 0): 101111 (47)
+insert_mult_bits(num, 7, 3, 3): 111101 (61)
+"""
+
+"""
+Insert exact one bit at specific position
+
+Algorithm:
+1. Create a mask having bit from i to the most significant bit, and append the new bit at 0 position
+2. Keep the bit from 0 position to i position ( like 000...001111)
+3) Merge mask and num
+"""
+def insert_one_bit(num, bit, i):
+    # Create mask
+    mask = num >> i
+    mask = (mask << 1) | bit
+    mask = mask << i
+    # Keep the bit from 0 position to i position
+    right = ((1 << i) - 1) & num
+    return right | mask
+
+def insert_mult_bits(num, bits, len, i):
+    mask = num >> i
+    mask = (mask << len) | bits
+    mask = mask << i
+    right = ((1 << i) - 1) & num
+    return right | mask
diff --git a/bit/remove_bit.py b/bit/remove_bit.py
new file mode 100644
index 0000000..b302cf9
--- /dev/null
+++ b/bit/remove_bit.py
@@ -0,0 +1,15 @@
+"""
+Remove_bit(num, i): remove a bit at specific position.
+For example:
+
+Input: num = 10101 (21)
+remove_bit(num, 2): output = 1001 (9)
+remove_bit(num, 4): output = 101 (5)
+remove_bit(num, 0): output = 1010 (10)
+"""
+
+def remove_bit(num, i):
+    mask = num >> (i + 1)
+    mask = mask << i
+    right = ((1 << i) - 1) & num
+    return mask | right
diff --git a/bit/swap_pair.py b/bit/swap_pair.py
new file mode 100644
index 0000000..c1bf758
--- /dev/null
+++ b/bit/swap_pair.py
@@ -0,0 +1,21 @@
+"""
+Swap_pair: A function swap odd and even bits in an integer with as few instructions
+as possible (Ex bit and bit 1 are swapped, bit 2 and bit 3 are swapped)
+
+For example:
+22: 010110  --> 41: 101001
+10: 1010    --> 5 : 0101
+"""
+
+"""
+We can approach this as operating on the odds bit first, and then the even bits.
+We can mask all odd bits with 10101010 in binary ('AA') then shift them right by 1
+Similarly, we mask all even bit with 01010101 in binary ('55') then shift them left
+by 1. Finally, we merge these two values by OR operation.
+"""
+def swap_pair(num):
+    # odd bit arithmetic right shift 1 bit
+    odd = (num & int('AAAAAAAA', 16)) >> 1
+    # even bit left shift 1 bit
+    even = (num & int('55555555', 16)) << 1
+    return odd | even


Test patch:
diff --git a/tests/test_bit.py b/tests/test_bit.py
index fc5f2b5..c9bafea 100644
--- a/tests/test_bit.py
+++ b/tests/test_bit.py
@@ -6,6 +6,12 @@ from bit.reverse_bits import reverse_bits
 from bit.single_number import single_number
 from bit.single_number2 import single_number2
 from bit.subsets import subsets
+from bit.bit_operation import get_bit, set_bit, clear_bit, update_bit
+from bit.swap_pair import swap_pair
+from bit.find_difference import find_difference
+from bit.has_alternative_bit import has_alternative_bit, has_alternative_bit_fast
+from bit.insert_bit import insert_one_bit, insert_mult_bits
+from bit.remove_bit import remove_bit
 
 import unittest
 import random
@@ -125,5 +131,80 @@ class TestSuite(unittest.TestCase):
                              (10, 30, 40), (30,), (20, 30), (30, 40), (10,), (),
                              (10, 20), (20, 40), (20, 30, 40), (10, 20, 30), (20,)})
 
+    def test_get_bit(self):
+        # 22 = 10110
+        self.assertEqual(1, get_bit(22, 2))
+        self.assertEqual(0, get_bit(22, 3))
+
+    def test_set_bit(self):
+        # 22 = 10110  --> after set bit at 3th position: 30 = 11110
+        self.assertEqual(30, set_bit(22, 3))
+
+    def test_clear_bit(self):
+        # 22 = 10110 --> after clear bit at 2nd position: 20 = 10010
+        self.assertEqual(18, clear_bit(22, 2))
+
+    def test_update_bit(self):
+        # 22 = 10110 --> after update bit at 3th position with value 1: 30 = 11110
+        self.assertEqual(30, update_bit(22, 3, 1))
+        # 22 = 10110 --> after update bit at 2nd position with value 0: 20 = 10010
+        self.assertEqual(18, update_bit(22, 2, 0))
+
+    def test_swap_pair(self):
+        # 22: 10110  --> 41: 101001
+        self.assertEqual(41, swap_pair(22))
+        # 10: 1010   --> 5 : 0101
+        self.assertEqual(5, swap_pair(10))
+
+    def test_find_difference(self):
+        self.assertEqual('e', find_difference("abcd", "abecd"))
+
+    def test_has_alternative_bit(self):
+        self.assertTrue(has_alternative_bit(5))
+        self.assertFalse(has_alternative_bit(7))
+        self.assertFalse(has_alternative_bit(11))
+        self.assertTrue(has_alternative_bit(10))
+
+    def test_has_alternative_bit_fast(self):
+        self.assertTrue(has_alternative_bit_fast(5))
+        self.assertFalse(has_alternative_bit_fast(7))
+        self.assertFalse(has_alternative_bit_fast(11))
+        self.assertTrue(has_alternative_bit_fast(10))
+
+    def test_insert_one_bit(self):
+        """
+        Input: num = 10101 (21)
+        insert_one_bit(num, 1, 2): 101101 (45)
+        insert_one_bit(num, 0 ,2): 101001 (41)
+        insert_one_bit(num, 1, 5): 110101 (53)
+        insert_one_bit(num, 1, 0): 101010 (42)
+        """
+        self.assertEqual(45, insert_one_bit(21, 1, 2))
+        self.assertEqual(41, insert_one_bit(21, 0, 2))
+        self.assertEqual(53, insert_one_bit(21, 1, 5))
+        self.assertEqual(43, insert_one_bit(21, 1, 0))
+
+    def test_insert_mult_bits(self):
+        """
+        Input: num = 101 (5)
+        insert_mult_bits(num, 7, 3, 1): 101111 (47)
+        insert_mult_bits(num, 7, 3, 0): 101111 (47)
+        insert_mult_bits(num, 7, 3, 3): 111101 (61)
+        """
+        self.assertEqual(47, insert_mult_bits(5, 7, 3, 1))
+        self.assertEqual(47, insert_mult_bits(5, 7, 3, 0))
+        self.assertEqual(61, insert_mult_bits(5, 7, 3, 3))
+
+    def test_remove_bit(self):
+        """
+        Input: num = 10101 (21)
+        remove_bit(num, 2): output = 1001 (9)
+        remove_bit(num, 4): output = 101 (5)
+        remove_bit(num, 0): output = 1010 (10)
+        """
+        self.assertEqual(9, remove_bit(21, 2))
+        self.assertEqual(5, remove_bit(21, 4))
+        self.assertEqual(10, remove_bit(21, 0))
+
 if __name__ == '__main__':
     unittest.main()