Bit wise operators in Python

BitsMagic.py

'''
Bitwise Operators in Python and some of the famous problems solved using bits operations.

Operator    Description             Syntax
------------------------------------------
&           Bitwise AND             x & y
|           Bitwise OR              x | y
^           Bitwise XOR             x ^ y
~           Bitwise NOT             ~x
>>          Bitwise right shift     x>>
<<          Bitwise left shift      x<<

Examples: 

(&)         (|)         (^)         (~)
10011100    10011100    10011100    10011100
00110100    00110100    00110100   
---------------------------------------------
00010100    10111100    10101000    01100011

5 >> 1 => [101 -> 010] => 2
5 << 2 => [101 -> 1010] => 10 

'''

def is_kth_bit_set(num, k):
  '''
  Problem: Check if k th bit of given number num is 1 or not. 
  Example: (13, 2) => False [for 13(1101) 2nd bit is not set]

  Solution: Shifting number right to k times would bring the k-th bit at right most place. then we can check it is set or not simply by & operation with 1.

  is_kth_bit_set(16, 4)
  '''
  return True if num and 1 & (num >> k) else False


def is_power_of_2(num):
  '''
  Problem: Check if given number num is a power of 2 or not.
  Example: (8) => True | (6) => False

  Solution: Number with power of 2 in binary, has a special feature that it has only bit set (left most) and the number less then 1 to it has all bits set right side to this except this one. 
  Example: (8, 7) => (1000, 0111)

  is_power_of_2(8)
  '''
  return True if num and not (num & (num-1)) else False


def count_set_bits(num):
  '''
  Problem: Count the set bit in given number num.
  Example: (3) => 2 |  (7) => 3 

  Solution: Brian Kernighan's Algorithm
  we see a pattern when we substract 1 from any number i.e. right most bit is unset and all bits after it are set. 
  Examples:
      8(1000) - 1 = 7(0111)
      20(10100) - 1 = 19(10011)   
      26(11010) - 1 = 25(11001)
  
  So [num & (num-1)] would unset the right most set bit.
  Example:
      20(10100) & 19(10011) = 10000

  So we keep removing right most bit and return the counter once arrived to 0.

  count_set_bits(3)
  '''
  count = 0
  while num:
    num = num & (num-1)
    count += 1
  return count


def find_odd_occurring(arr):
  '''
  Problem: Given array has all numbers occurring even number of times in the array except one number. find that one odd number of times occurring number.
  Example: [3,3,3,4,5,4,5] => 3

  Solution: We can use XOR Operator to solve this problem. let's look some of the properties associated with Xor Operator.
  x^y = y^x
  x^(y^z) = (x^y)^z
  x^0 = x
  we'll take XOR of all array elements.
  Example: 3^3^3^4^5^4^5 = 3

  find_odd_occurring([3,3,4,4,5,4,5])
  ''' 
  result = 0
  for item in arr:
    result ^= item
  return result


def longest_1s_binary(num):
  '''
  Problem: Find length of the longest consecutive 1s in its binary representation of given number num.
  Example: 222 => 4(11011110) | 14 => 3(1110)
  
  Solution: Shift the binary number to any of left/right side and take bitwise or(&) with num. This would reduce one 1 from each consecutive 1's in number.
  Example:
  11011110 >> 1 => 01101111 then (11011110 & 01101111) => 01001110
  This is how, we'll keep repeating it till we get 0.

  longest_1s_binary(2048)
  '''
  count = 0
  while num:
    num = num & (num >> 1)
    count += 1
  return count

def is_sparse(num):
  '''
  Problem: The task is to check whether it is sparse or not. A number is said to be a sparse number if no two or more consecutive bits are set in the binary representation.
  Example: 2 => True | 3 => False

  Solution: we can solve this by taking bitwise and of given number and the number generated by shifting 1 to it.

  is_sparse(3)
  '''
  return False if num&(num<<1) else True
  

'''
TODOs

Find 2 numbers occurring odd number of times in the array. Extension to problem statement for find_odd_occurring.

Given an integer an N. The task is to return the position of first set bit found from the right side in the binary representation of the number.

Given two numbers M and N. The task is to find the position of the rightmost different bit in the binary representation of numbers.

You are given two numbers A and B. The task is to count the number of bits needed to be flipped to convert A to B.

The task is to check whether it is sparse or not. A number is said to be a sparse number if no two or more consecutive bits are set in the binary representation.


'''