Bit Manipulation Python : Easy guide to perform bit manipulation in Python

Understand what bit manipulation is and follow our easy guide to perform bit manipulation in Python.

What is bit manipulation?

Bits make up the language that machines understand at their core. A bit, which can either be a 0 or 1, is the most basic instruction in computing. Working with bits means faster computations. In bit manipulation, a number is treated as a string of bits, which are then either shifted, or manipulated using a bit operator accordingly. 

Shifting can be done either to the right or to the left. Bit operators used to carry out the bit manipulation are the NOT, AND, OR and XOR. These operators work like the Boolean logic operators, however are applied on individual bits.

Bitwise Operators In Python

In Python, bitwise operators are performed on signed numbers and these numbers are treated as two’s complement binary. The two’s complement of positive signed numbers is the same as normal binary, however, when it comes to negative numbers, the representation is slightly different. For negative numbers, the leading bits are 1s.

To briefly explain bit representation using two’s complement, if we are using 4-bit numbers, we can use 0111 to represent from 0 to number 7 as with classical binary. The leading bit is negative, so in this case, 1000 is representing –8. To manually work out how numbers –1 to –7 are represented in two’s complement we follow the below steps:

1. Represent the number x-1 in binary;
2. Use the complement by switching all the bits, 1 becoming 0 and 0 becoming 1.

To show this with a small example, if one wanted to represent the number -6:

1. 6-1 gives 5, and 5 in binary is 0101; 
2. Switching all the bits, it becomes 1010, which is the two’s complement representation of –6.

The respective symbols used in Python to perform these bit operations are as follows:

These will be explained in some more detail below. For simplicity’s sake, 8-bit numbers will be used for the examples provided. Python uses infinite bit representation.

• Left Shift

A left shift is equivalent to multiplying a number by 2x. Let us see the example below:

The number two converted to binary is 0000 0010. The number three indicates how many places the ‘1’ needs to be shifted to the left. Three shifts to the left we get 0001 0000 and this represents sixteen.

• Right Shift

A right shift is equivalent to dividing a number by 2x. Check out the example below:

Converting eight to binary is 000 1000.  Shifting two to the left as indicated gives us 0000 0010 which represents number two.

• NOT

The NOT operator switches each bit in the pattern, replacing 0 with 1 and 1 with 0. The NOT bit operation is achieved by using the operator ‘~’. For example:

As can be seen, the result is a negative. This is because, as explained earlier, the numbers in Python are represented using two’s complement. This means that if the leading bit is 1, that means the number is a negative one.

The number three to binary becomes 0000 0011. Switching all bits, we get 1111 1100 which, in two’s complement represents –4.

• AND

This operator works by outputting a 1 when all inputs are a 1, otherwise a 0 is given. Let us take the below example:

Converting five to binary, one gets 0101. The number three in binary is represented as 0011.

After using the & operator on each individual column, the result, being 0001, represents number one.

• OR

The OR operator gives a result of 0 when the both bits are 0, otherwise a 1 is given. For example:

Converting five to binary, one gets 0101. The number three in binary is represented as 0011.

After using the | operator on each individual column, the result, being 0111, represents number seven. 

• XOR

The bitwise exclusive OR gives a value of 1 when there is an odd number of 1’s in the input. Naturally the rest remain 0. See the example below:

The number seven in binary is represented as 0111. Converting five to binary, one gets 0101. 

After using the ^ operator on each individual column, the result is 0010, representing number two.

A More Complex Bit Manipulation Example

The above are simplified examples. Bit manipulation can get very complex and can be used in things like encryption and compression. The following example is a program which takes a small letter between a and z and encrypts it using the Caeser Cipher algorithm, using only bitwise operators. 

This Caeser Cipher encryption method is a very simple algorithm which traverses each letter according to the number of times specified. For example if the shift pattern is 2 and we input the plain letter ‘r’, the resultant encrypted letter shifted two times will be ‘t’.

It can be easily done using a traversing algorithm with arithmetic operators in Python, as can be seen here. 

To use bitwise operators, one needs to take a different approach.

def add_num(x: int, y: int): 
    ''' 
    Adds a number x by another number y using bitwise operators. 
    :param x:   Any number between 97 and 122. 
    :param y:   Number to add to x. 
    ''' 
    # Iterate till there is no carry   

    while (y != 0): 
        # carry now contains common  
        # set bits of x and y  
        carry = x & y  
        # Sum of bits of x and y where at  
        # least one of the bits is not set  
        x = x ^ y 
        # Carry is shifted by one so that     
        # adding it to x gives the required sum  
        y = carry << 1 
     return x 

def subtract_num(x: int, y: int): 
    ''' 
    Subtracts a number x from another number y using bitwise operators. 
    :param x:   Any number between 97 and 122. 
    :param y:   Number to subtract from y. 
    ''' 
    # Iterate till there is no carry  

    while (y != 0):  
        # borrow contains common   
        # set bits of y and unset  
        # bits of x  
        borrow = (~x) & y  
        # Subtraction of bits of x  
        # and y where at least one  
        # of the bits is not set  
        x = x ^ y  
        # Borrow is shifted by one   
        # so that subtracting it from  
        # x gives the required sum 
        y = borrow << 1       
      return x    
def encrypt_lower_case(letter: str, pattern: int):      
        #Shifts a given character according to the shift pattern in Caeser Cipher algorithm.      
        #:param letter:  Any number between 97 and 122.      
        #:param pattern: Number to add to x.
        
        letter_unicode = ord(letter)      
        # Check if character is a letter between a and z. If not raise ValueError exception.      
        if letter_unicode not in range(97,123):          
            raise ValueError("Error! Input not in allowed range...")      
        result_unicode = add_num(letter_unicode, pattern)      
        
        # If letter exceeds z, shift starts from a again.     
        if result_unicode > 122: 
              diff = subtract_num(result_unicode, 123) 
              result_unicode = add_num(97, diff) 
        return chr(result_unicode) 

plain_letter = input("Enter letter a-z to encrypt: ") 
pattern = input("Enter Ceaser Cipher shift pattern: ") 
print(f"{plain_letter} -> {encrypt_lower_case (plain_letter, int(pattern))}")

To understand more how the addition and subtraction using bitwise operators is carried out in add_num and subtract_num functions, one needs to understand the Half Adder logic. The logic for the addition and subtraction was taken from here.

The main method for the encryption, encrypt_lower_case() works as follows:

1. Convert character to Unicode using ord();
2. Check if character is a lower case letter, otherwise raise an error;
3. Add the shift pattern to the Unicode representation to find the Unicode representation of the encrypted letter required. To do this we use bitwise operators.
4. If the result of the addition exceeds the Unicode representation of the letter ‘z’(122):
   1. Find the difference between Unicode representation of ‘z’ and the resultant Unicode. This gives us the amount of shifts still required to find the encrypted letter when arriving at the last letter of the alphabet;
   2. Add this remaining number to Unicode representation of the letter ‘a’(97) to find the encrypted letter when starting  again from the beginning of the alphabet.
5. Return the character representation of the Unicode using chr().

Conclusion

This was an overview of what bitwise operators are and how they are used. 

They are essential when working with certain systems like embedded ones. Although working with bits might seem less intuitive, there are certainly advantages to consider, namely speed and optimisation, which undoubtedly exhibits the power one has when using bit manipulation.