1 month

Bit Manipulation




Computers represent all data internally as sequences of bits. Each bit can assume the value 0 or the value 1. The bitwise operators are used to manipulate the bits of integral operands both signed and unsigned.  Unsigned integers are normally used with the bitwise operators. Bitwise manipulations are machine-dependent.

binary number system is one of the four types of number systems, and it is used to define a number in a binary system. A binary number system represents a number in terms of only two digits, i.e., 0 (zero) and 1 (one). 

Computers use a method called Two’s Complement to represent negative numbers. Also, this method can be more effective when performing mathematical operations like adding and subtracting.

In this method, the bit at the far left side of the bit pattern is the most significant bit, or MSB is used to indicate positive or negative numbers.

Positive numbers always start with a 0 and the remaining bits are used to store the actual size of the number.

Negative numbers always start with a 1 and the remaining bits are used to store the actual size of the number. The biggest negative number is the largest binary value. (e.g. 1111 is -1)

Bitwise Operators                                    

Working with primitive data types like bytesbooleansintsfloatsdoubles, or with data structures is normal for a programmer. Sometimes in Computer Science, you need to go beyond this to a deeper level where you need to understand the importance of bits.

This is especially important if you are working on data compression and encryption algorithms, optimization, data correction, error detection algorithms, and so on.

AND Operator                                                                                                 

AND Operator (&) gives 1 only if both of the operands are 1, otherwise 0.

Check if the integer is even or odd:
def check_even_or_odd(n: int) -> str:                                 
    if (n & 1) == 0:                                                                    
        return f"{n} is even number."                                       
    else:                                                                                    
        return f"{n} is odd number."                                        

An integer is odd if and only if the least significant bit (LSB) is 1. By using AND (&) operator between given number (n) and 1, we are eliminating all bits other than LSB. After this operation, if the result is 0, that means LSB is 0 and the number is even. Otherwise, it is odd.

         0001 0001    (Binary of 17)                                                                                      
         0000 0001    (Binary of 1)                                                                                             
     & ------------------------------------                                                                                                    
        0000 0001 ------> 1, so 17 is odd number                                                                                     

        0000 1000   (Binary of 8)                                                                                                               
        0000 0001    (Binary of 1)                                                                                                                 
     & ------------------------------------                                                                                                                            
        0000 0000 ------> 0, so 8 is even number                                                                                           
                              

OR Operator                                                                                         

OR Operator (|) gives 0 only if both of the operands are 0, otherwise 1.

 

a = 10 = 1010 (Binary)
b = 4 =  0100 (Binary)

a | b = 1010
         |
        0100
      = 1110
      = 14 (Decimal)         

XOR Operator                                                                                      

XOR Operator (^) gives 1 for odd numbers of 1s, otherwise 0.

 

12 = 00001100 (In Binary)
25 = 00011001 (In Binary)

Bitwise XOR Operation of 12 and 25
  00001100
^ 00011001
  ________
  00010101  = 21 (In decimal)   

 

One’s Complement Operator                                                                 

One’s Complement Operator (~) is a unary operator and converts 0s to 1s and 1s to 0s.

a = 10 = 1010 (Binary)

~a = ~1010
   = -(1010 + 1)
   = -(1011)
   = -11 (Decimal)

 

Left Shift Operator                                                                                              

Left Shift Operator (<<) shifts the bits to the left and insert 0 bit at least a significant bit.

b = -10 = 1111 0110 (Binary)
b << 1 = 1110 1100 = -20
b << 2 = 1101 1000 = -40   

Right Shift Operator                                                                                    

Right Shift Operator (>>) shifts the bits to the right and the operator inserts 0 bit at the most significant bit.

  a = 10 = 0000 1010 (Binary)
a >> 1 = 0000 0101 = 5

What is Bit Mask?                                                                                         

Bit manipulation is the act of algorithmically manipulating bits or other pieces of data shorter than a byte. A bit mask (or Bitmap) is a data structure, usually an integer or array of bits, that represents a bit pattern that signifies a particular state in a particular computational problem. It takes advantage of bitwise operations.

We mostly use the following notations/operations on masks:                    
           bit(i, mask) – the i-th bit of mask                                                     
           count(mask) – the number of non-zero bits in the mask                
           first(mask) – the number of the lowest non-zero bit in the mask    
           set(i, mask) – set the ith bit in the mask                                       
           check(i, mask) – check the ith bit in the mask                               

We use bit masks because:

        -  it is memory efficient in most problems

        - it is computationally efficient as we can use bitwise operations which are natively supported by the computer system and will be faster than other operations like addition (+).

Masking is the act of applying a mask to a value. This is accomplished by doing:

  • Bitwise AND  in order to extract a subset of the bits in the value                            
  •     1 1 1 0 1 1 0 1     input
    (&)  0 0 1 1 1 1 0 0      mask
    ------------------------------
         0 0 1 0 1 1 0 0    output
  • Bitwise OR in order to set a subset of the bits in the value
  • data    10110010
    mask  | 01000000
            ________
    ans =   11110010
  •      1 1 1 0 1 1 0 1     input
    (^)  0 0 1 1 1 1 0 0      mask
    ------------------------------
         1 1 0 1 0 0 0 1    output
mask = ~(1<<2)  [Bitwise complement(~) operator : it will flip all bits ~(11110000) = (00001111)]

Bit operators are a useful way to pass a set of named boolean arguments to a function. 

Masks are used with IP addresses in IP ACLs (Access Control Lists) to specify what should be permitted and denied.

In computer graphics, when a given image is intended to be placed over a background, the transparent areas can be specified through a binary mask.

Toggle all bits after most significant bit                                                         

We can toggle a bit by doing XOR of it with 1 (Note that 1 ^ 0 = 1 and 1 ^ 1 = 0). The idea is to take a number temp with only one bit set. One by one move the only set bit of temp to left and do XOR of it with n until it crosses MSB (Most Significant Bit) of n.  

# Python program to toggle  set  bits starting  from MSB

def toggle(n):                                      

 # temporary variable to use XOR with one of a n

    temp =                                                                              

 # Run loop until the only set bit in temp crosses MST of n.

    while (temp <= n):                                                                            

   # Toggle bit of n  corresponding to  current set bit in  temp.

        n = n ^ temp                                              

        # Move set bit to next  higher position.                   

        temp = temp << 1                                     

    return n                                                                                                            

 

Time Complexity: O(log n)  Auxiliary Space: O(1)                                        

Another Approach:                                                                                                            

from math import log                                                  

# Returns a number which has all set bits  starting from MSB of n

def toggle(num):                                       

 # the number of bits is equal to log2num + 1

    n = int(log(num, 2)) + 1                           

# calculating mask                               

    mask = pow(2, n) - 1                  

# toggling bits using xor with mask             

    return num ^ mask                                 

 

Time Complexity: O(logn)    Auxiliary Space: O(1)                             

Optimization:                                                                                                             

def setAllBitsAfterMSB(n):                                                                             

  # This makes sure two bits  (From MSB and including MSB)  are set

    n |= n>>1                                                                          

  # This makes sure 4 bits (From MSB and including MSB)  are set

    n |= n>>2                                                                  

    n |= n>>4                                                

    n |= n>>8                                      

    n |= n>>16                                               

    return n                             

def toggle(n):                          

    n = n ^ setAllBitsAfterMSB(n)               

    return n                                                                                  

Time Complexity: O(1)          Auxiliary Space: O(1)                                             

Count set bits in an integer                                                                                                               

Write an efficient program to count the number of 1s in the binary representation of an integer.

Input : n = 7
Output : 3
Binary representation of 7 is 111 and has 3 set bits

Input : n = 17
Output : 2
Binary representation of 17 is 10001 and has 2 set bits.

# Python3 program to Count set  bits in an integer 

def  countSetBits(n):                                      

    count = 0                                                

    while (n):                                                

        count += n & 1                                               

        n >>= 1                     

    return count                                                                 

Time Complexity: O(logn)  Auxiliary Space: O(1)                                

Recursive Function:                                                                                

def countSetBits( n):                                                        

    if (n == 0):                                                   

        return 0                                              

    else:                                                      

        # if last bit set add 1 else  add 0                                      

        return (n & 1) + countSetBits(n >> 1)                     

Time Complexity: O(log n)      Auxiliary Space: O(1)                                                                        

Brian Kernighan’s Algorithm:                                                                        
Subtracting 1 from a decimal number flips all the bits after the rightmost set bit(which is 1) including the rightmost set bit. 
For Example : 
8 in binary is 00001000                          
7 in binary is 00000111                                                                        
So if we subtract a number by 1 and do it bitwise & with itself (n & (n-1)), we unset the rightmost set bit. If we do n & (n-1) in a loop and count the number of times the loop executes, we get the set bit count. 

def countSetBits(n):                                                 

    count = 0                                                       

    while (n):                                                       

        n &= (n-1)                                                   

        count += 1                                                                       

    return count                                                          

n =  9 (1001)
   count = 0

   Since 9 > 0, subtract by 1 and do bitwise & with (9-1)
   n = 9&8  (1001 & 1000)
   n = 8
   count  = 1

   Since 8 > 0, subtract by 1 and do bitwise & with (8-1)
   n = 8&7  (1000 & 0111)
   n = 0
   count = 2
   Since n = 0, return count which is 2 now.

Time Complexity: O(logn)   Auxiliary Space: O(1)                                    

Recursive Function:                                                                                             

def countSetBits(n):                                             

    if (n == 0):                   

        return 0                       

    else:                               

        return 1 + countSetBits(n & (n - 1))                    

Time Complexity: O(logn)                   Auxiliary Space: O(1)                               

 

print(bin(4).count('1'))                   # output 1                                      

print(bin(15).count('1'));                 # oupput 4                                          

Using Lookup table: We can count bits in O(1) time using the lookup table.

BitsSetTable256 = [0] * 256                                                   

# Function to initialise the lookup table                         

def initialize():                                                                                                     

  # To initially generate the  table algorithmically         

    BitsSetTable256[0] = 0                     

    for i in range(256):                                                  

        BitsSetTable256[i] = (i & 1) + BitsSetTable256[i // 2]     

# Function to return the count  of set bits in n

def countSetBits(n):                                          

    return (BitsSetTable256[n & 0xff] +                

            BitsSetTable256[(n >> 8) & 0xff] +             

            BitsSetTable256[(n >> 16) & 0xff] +                

            BitsSetTable256[n >> 24])                  

Time Complexity: O(1)    Auxiliary Space: O(1)                                              

0xFF is a hexadecimal constant which is 11111111 in binary. By using bitwise AND ( & ) with this constant, it leaves only the last 8 bits of the original.                     

Count unset bits of a number                                                                                      

Unset bits in a binary number is represented by 0. Whenever we calculate the binary number of an integer value then it is formed as the combination of 0’s and 1’s. So, the digit 0 is known as the unset bit in the terms of the computer.

Given a number n, count unset bits after MSB (Most Significant Bit).

Input : 17
Output : 3
Binary of 17 is 10001
so unset bit is 3

Input : 7
Output : 0

def countunsetbits(n):                                                    

    count = 0                                                                                              

 # x holds one set digit at a time  starting from LSB to MSB of n.

    x = 1                                                                                       

    while(x < n + 1):                                                   

        if ((x & n) == 0):                                 

            count += 1                                              

        x = x << 1                                                   

    return count                                                                                  

Time complexity is log(n).    Space Complexity: O(1)

Optimization:                                                                             

import math                                                           

def countUnsetBits(n):                                                                  

    x = n                                                                 

# Make all bits set MSB(including MSB).This makes sure two bits(From MSB  and   

  # including MSB) are set                                    

    n |= n >> 1                                                      

 # This makes sure 4 bits(From MSB and  including MSB) are set

    n |= n >> 2                                                       

    n |= n >> 4                                        

    n |= n >> 8                                                            

    n |= n >> 16                                    

    t = math.log(x ^ n, 2)                                                  

    # Count set bits in toggled number                                             

    return math.floor(t)                                                                          

Time Complexity: O(1)   Auxiliary Space:  O(1)

Equal Sum and XOR                                                                

Given a positive integer n, find count of positive integers i such that 0 <= i <= n and n+i = n^i .

Input: n = 12
Output: 4
12^i = 12+i hold only for i = 0, 1, 2, 3
for i=0, 12+0 = 12^0 = 12
for i=1, 12+1 = 12^1 = 13
for i=2, 12+2 = 12^2 = 14
for i=3, 12+3 = 12^3 = 15

# Python3 program to print count  of values such that n+i = n^i

# function to count number  of values less than  equal to n that satisfy  the given condition

def countValues (n):                                             

    result = 0;                                                                    

  # Traverse all numbers  from 0 to n and  increment result only 

   # when given condition  is satisfied.                                                 

    for i in range(n + 1):                                         

        if ((n + i) == (n ^ i)):                                  

            result += 1;                                        

    return result;                                                                           

Time Complexity: O(n)    Space Complexity: O(1)

An efficient solution is as follows: we know that (n+i) = (n^i) + 2*(n&i). So n + i = n ^ i implies n & i = 0

#  Function to count number of values less than  equal to n that satisfy the given condition

def countValues(n):                                                                             

 # unset_bits keeps track of count of un-set  bits in binary representation of n

    unset_bits = 0                                                                           

    while(n):                                                                

        if n & 1 == 0:                                                          

            unset_bits += 1                                                      

        n = n >> 1                                                                                   

    # Return 2 ^ unset_bits                                                

    return 1 << unset_bits                                              

 

Time Complexity: O(log(n))    Space Complexity: O(1)

Bitwise Operator Overloading                                                                

Operator overloading, sometimes termed operator ad hoc polymorphism, is a specific case of polymorphism, where different operators have different implementations depending on their arguments. Operator overloading is generally defined by a programming language, a programmer, or both.

We can overload all existing operators but we can’t create a new operator. To perform operator overloading, Python provides some special function or magic function that is automatically invoked when it is associated with that particular operator. For example, when we use + operator, the magic method __add__ is automatically invoked in which the operation for + operator is defined.

When we use an operator on user defined data types then automatically a special function or magic function associated with that operator is invoked. Changing the behavior of operator is as simple as changing the behavior of method or function. 

class D:                                        

    def __init__(self, x):                           

        self.x = x                              

    def __add__(self, y):                                          

        return self.x + y.x                                   

ob1 = D(9)                                                     

ob2 = D(8)                                                      

ob3 = D("Python")                                                        

ob4 = D("Magic")                                                                               

print(ob1 + ob2)                                                    

print(ob3 + ob4)                                                                                   

Output:        17                                                                                                       

                     Python Magic                                                                                    

class Bitwise():                                                

    def __init__(self, value):                                    

        self.value = value                                            

    def __and__(self, obj):                                               

        print("And operator overloaded")                

        if isinstance(obj, Bitwise):                                   

            return self.value & obj.value                            

        else:                      

            raise ValueError("Must be a object of class Bitwise")

    def __or__(self, obj):                                      

        print("Or operator overloaded")                                   

        if isinstance(obj, Bitwise):                                                   

            return self.value | obj.value                  

        else:                                                

            raise ValueError("Must be a object of class Bitwise")

    def __xor__(self, obj):                                            

        print("Xor operator overloaded")                  

        if isinstance(obj, Bitwise):                     

            return self.value ^ obj.value

        else:                              

            raise ValueError("Must be a object of class Bitwise")                    

    def __lshift__(self, obj):                                           

        print("lshift operator overloaded")                        

        if isinstance(obj, Bitwise):

            return self.value << obj.value                                

        else:                                                    

            raise ValueError("Must be a object of class Bitwise")

    def __rshift__(self, obj):                                       

        print("rshift operator overloaded")

        if isinstance(obj, Bitwise):                  

            return self.value & obj.value                                     

        else:                                                         

            raise ValueError("Must be a object of class Bitwise")

    def __invert__(self):                                               

        print("Invert operator overloaded")                    

        return ~self.value                                      

if __name__ == "__main__":                                  

    a = Bitwise(17)                                     

    b = Bitwise(7)                                           

    print(a & b)                                      

    print(a | b)                                       

    print(a ^ b)                                                   

    print(a << b)                                                  

    print(a >> b)                                                      

    print(~a)                                                       

 

 

 

 


Responses(0)