Shift operators in bit level programming

-

Why bit level programming ?

Hi everyone, this blog post is about shift operators in bit level programming. The first question which comes in most of the readers mind is why we are doing bit level programming? The answer is as simple as that, bit level programming is the lowest level programming. Here we will be using only bits of memory. It will help in saving a lot of memory space. Please remember that 1 byte = 8 bits.

An example of bit level programming is given. Find whether a number is a power of 2. 
This question can be answered in many ways. 

  • We can find the number modulus 2 and check whether it is equal to 0. Then we can divide the number by 2 till it is possible. Simultaneously check the modulus of that number. If the mode of that number = 0, it is power of 2.
Here, we are doing integer programming. The size of 'int' is 4 bytes or 32 bits.

But, the same can also be done using bits.
  • Take the 'AND' operation of that number and number - 1 in bits. If it is equal to 0, then it is a power of 2.
This method takes less amount of time than the previous method.

So, I hope everyone understood the importance of bit level programming. Now let us take a look at shift operators in bit level programming. 

Shift operators in bit level programming

In java, there are three types of shift operators. They are left shift operator, signed right shift operator and unsigned right shift operator.

1) Left shift operator

Left shift operator shifts the bits to left of an expression. In theory, it increases the value of a positive number. In java, left shift is denoted as '<<'. By doing left shift of a number by 1, the number becomes double of its value. When a negative number is shifted 1 time to its left, its value becomes half of its initial value. When a number is shifted to 32 times to its left or a multiple of 32 times, it will be the same number. This happens because there are only 32 bits in integer value in java. When the MSB, goes to 32nd position and when it gets shifted again, the value will decrease for positive integer.

In general, if a  number is shifted 'N' number of times, it is same as shifting it 'N' modulus 32 times.

Following program gives a better idea about left shift operators in java.


public class BitShift {

    public static void main(String args[])
    {
        System.out.println("Shift operators in bit level programming");
        System.out.println();
        System.out.println(" Left Shift Operation");
        System.out.println();
        int num=8;
        int num1 = 17;
        int num2= -63;
        System.out.println("The number "+num+" when shifted 1 time to left = "+(num<<1));
        System.out.println("The number "+num+" when shifted 2 times to left = "+(num<<2));
        System.out.println("The number "+num+" when shifted 32 times to left = "+(num<<32));
        System.out.println("The number "+num+" when shifted 33 times to left = "+(num<<33));
        System.out.println("The number "+num+" when shifted 100 times to left = "+(num<<100));

        System.out.println();
        
        System.out.println("The number "+num1+" when shifted 1 time to left = "+(num1<<1));
        System.out.println("The number "+num1+" when shifted 2 times to left = "+(num1<<2));
        System.out.println("The number "+num1+" when shifted 32 times to left = "+(num1<<32));
        System.out.println("The number "+num1+" when shifted 33 times to left = "+(num1<<33));
        System.out.println("The number "+num1+" when shifted 100 times to left = "+(num1<<100));
        System.out.println();
        
        System.out.println("The number "+num2+" when shifted 1 time to left = "+(num2<<1));
        System.out.println("The number "+num2+" when shifted 2 times to left = "+(num2<<2));
        System.out.println("The number "+num2+" when shifted 32 times to left = "+(num2<<32));
        System.out.println("The number "+num2+" when shifted 33 times to left = "+(num2<<33));
        System.out.println("The number "+num2+" when shifted 100 times to left = "+(num2<<100));
        
    }
}

The output of the above program is as follows: -

Shift operators in bit level programming

 Left Shift Operation

The number 8 when shifted 1 time to left = 16
The number 8 when shifted 2 times to left = 32
The number 8 when shifted 32 times to left = 8
The number 8 when shifted 33 times to left = 16
The number 8 when shifted 100 times to left = 128

The number 17 when shifted 1 time to left = 34
The number 17 when shifted 2 times to left = 68
The number 17 when shifted 32 times to left = 17
The number 17 when shifted 33 times to left = 34
The number 17 when shifted 100 times to left = 272

The number -63 when shifted 1 time to left = -126
The number -63 when shifted 2 times to left = -252
The number -63 when shifted 32 times to left = -63
The number -63 when shifted 33 times to left = -126
The number -63 when shifted 100 times to left = -1008

2) Signed Right Shift Operator

 Right shift operator shifts the bits to right of an expression. In theory, it decreases the value of a positive number. In java signed right shift is represented as '>>'. By right shifting a positive number once, it becomes half of that, while a negative number becomes double. If the number is odd, then it becomes floor value of its half, when it is right shifted once. (Provided that the number is positive). When the number is shifted 32 times to it right, it becomes the same number. (Same as that of left shift operator).

Following program gives a better idea about signed right shift operator.


public class BitShift {

    public static void main(String args[])
    {
        System.out.println("Shift operators in bit level programming");
        System.out.println();
        System.out.println("Signed Right Shift Operation");
        System.out.println();
        int num=8;
        int num1 = 17;
        int num2= -63;
        
        System.out.println("The number "+num+" when shifted 1 time to right (signed)= "+(num>>1));
        System.out.println("The number "+num+" when shifted 2 times to right (signed)= "+(num>>2));
        System.out.println("The number "+num+" when shifted 32 times to right (signed)= "+(num>>32));
        System.out.println("The number "+num+" when shifted 33 times to right (signed)= "+(num>>33));
        System.out.println("The number "+num+" when shifted 100 times to right (signed)= "+(num>>100));

        System.out.println();
        
        System.out.println("The number "+num1+" when shifted 1 time to right (signed)= "+(num1>>1));
        System.out.println("The number "+num1+" when shifted 2 times to right (signed)= "+(num1>>2));
        System.out.println("The number "+num1+" when shifted 32 times to right (signed)= "+(num1>>32));
        System.out.println("The number "+num1+" when shifted 33 times to right (signed)= "+(num1>>33));
        System.out.println("The number "+num1+" when shifted 100 times to right (signed)= "+(num1>>100));
        System.out.println();
        
        System.out.println("The number "+num2+" when shifted 1 time to right (signed)= "+(num2>>1));
        System.out.println("The number "+num2+" when shifted 2 times to right (signed)= "+(num2>>2));
        System.out.println("The number "+num2+" when shifted 32 times to right (signed)= "+(num2>>32));
        System.out.println("The number "+num2+" when shifted 33 times to right (signed)= "+(num2>>33));
        System.out.println("The number "+num2+" when shifted 100 times to right (signed)= "+(num2>>100));
        
        
    }
}

The output of the above program is as follows: -

Shift operators in bit level programming

Signed Right Shift Operation

The number 8 when shifted 1 time to right (signed)= 4
The number 8 when shifted 2 times to right (signed)= 2
The number 8 when shifted 32 times to right (signed)= 8
The number 8 when shifted 33 times to right (signed)= 4
The number 8 when shifted 100 times to right (signed)= 0

The number 17 when shifted 1 time to right (signed)= 8
The number 17 when shifted 2 times to right (signed)= 4
The number 17 when shifted 32 times to right (signed)= 17
The number 17 when shifted 33 times to right (signed)= 8
The number 17 when shifted 100 times to right (signed)= 1

The number -63 when shifted 1 time to right (signed)= -32
The number -63 when shifted 2 times to right (signed)= -16
The number -63 when shifted 32 times to right (signed)= -63
The number -63 when shifted 33 times to right (signed)= -32
The number -63 when shifted 100 times to right (signed)= -4

3) Unsigned Right Shift Operator

 The unsigned right shift operator fills the higher order bits with the value zero, whenever a shift happens. In case of positive number, signed right shift is same as unsigned right. In java, the unsigned right shift is represented by '>>>'.  Here, the negative number will be stored in 32 bit 2's complement form. (2's complement = 1's complement + 1) and (1's complement = complement of every bit, i.e 1->0 and 0-> 1). When the number is shifted 32 times, it becomes the same number.

Following program gives a better idea about unsigned right shift operator.


public class BitShift {

    public static void main(String args[])
    {
        System.out.println("Shift operators in bit level programming");
        System.out.println();
        System.out.println("Signed Right Shift Operation");
        System.out.println();
        int num=8;
        int num1 = 17;
        int num2= -63;
        
        System.out.println("The number "+num+" when shifted 1 time to right (unsigned)= "+(num>>>1));
        System.out.println("The number "+num+" when shifted 2 times to right (unsigned)= "+(num>>>2));
        System.out.println("The number "+num+" when shifted 32 times to right (unsigned)= "+(num>>>32));
        System.out.println("The number "+num+" when shifted 33 times to right (unsigned)= "+(num>>>33));
        System.out.println("The number "+num+" when shifted 100 times to right (unsigned)= "+(num>>>100));

        System.out.println();
        
        System.out.println("The number "+num1+" when shifted 1 time to right (unsigned)= "+(num1>>>1));
        System.out.println("The number "+num1+" when shifted 2 times to right (unsigned)= "+(num1>>>2));
        System.out.println("The number "+num1+" when shifted 32 times to right (unsigned)= "+(num1>>>32));
        System.out.println("The number "+num1+" when shifted 33 times to right (unsigned)= "+(num1>>>33));
        System.out.println("The number "+num1+" when shifted 100 times to right (unsigned)= "+(num1>>>100));
        System.out.println();
        
        System.out.println("The number "+num2+" when shifted 1 time to right (unsigned)= "+(num2>>>1));
        System.out.println("The number "+num2+" when shifted 2 times to right (unsigned)= "+(num2>>>2));
        System.out.println("The number "+num2+" when shifted 32 times to right (unsigned)= "+(num2>>>32));
        System.out.println("The number "+num2+" when shifted 33 times to right (unsigned)= "+(num2>>>33));
        System.out.println("The number "+num2+" when shifted 100 times to right (unsigned)= "+(num2>>>100));
        
        
    }
}

The output of the above program is as follows:-

Shift operators in bit level programming

 Unsigned Signed Right Shift Operation

The number 8 when shifted 1 time to right (unsigned)= 4
The number 8 when shifted 2 times to right (unsigned)= 2
The number 8 when shifted 32 times to right (unsigned)= 8
The number 8 when shifted 33 times to right (unsigned)= 4
The number 8 when shifted 100 times to right (unsigned)= 0

The number 17 when shifted 1 time to right (unsigned)= 8
The number 17 when shifted 2 times to right (unsigned)= 4
The number 17 when shifted 32 times to right (unsigned)= 17
The number 17 when shifted 33 times to right (unsigned)= 8
The number 17 when shifted 100 times to right (unsigned)= 1

The number -63 when shifted 1 time to right (unsigned)= 2147483616
The number -63 when shifted 2 times to right (unsigned)= 1073741808
The number -63 when shifted 32 times to right (unsigned)= -63
The number -63 when shifted 33 times to right (unsigned)= 2147483616
The number -63 when shifted 100 times to right (unsigned)= 268435452

Points to remember

 1) For a positive integer, left shift doubles the value and right shift halves the value. Opposite for negative integer. When the MSB of the bit goes to 32nd position and then it gets shifted, the value will decrease for positive number and increase for negative number.
2) If we shift a number 32 times (any type of shift), we will get the same number.
3) If a number is shifted 'N' number of times, it is same as shifting 'N' modulus 32 times.
4) During unsigned right shift of negative integers, it is stored as 2's complement of that integer.
5) Unsigned right shift of positive integers is same as it's signed right shift.

I hope this blog post had given you a clear idea of shift operators in bit level programming. Thank you for reading the post. Comments/suggestions are always welcome.

Comments

Post a Comment

Popular posts from this blog

Difference between "diff" and "sdiff" commands in Unix

-
Image
Hi everyone, in this blog post, I will be discussing about the difference between "diff" and "sdiff" commands in Unix. This is my first post about Unix. diff command diff command will compare two files and prints the difference between the 2 files. The format of diff command is diff file1 file2 . sdiff command sdiff command will compare two files side by side. The format of sdiff command is sdiff file1 file2. The contents of files are displayed side by side with a marker denoting the difference between each files. Some of the important markers used in sdiff are as follows: | - denotes the 2 files differ in the line completely. < - only the first file contains the line. > - only the second file contains the line. The better way to depict the difference is by showing examples. Here, I am comparing 2 files which are named as " ipl_teams_2008.txt " and " ipl_teams_2015.txt ". Let's see the contents of the files.
Read more

Anonymous classes in C++

-
Anonymous Classes in C++ Anonymous class is a class with no name. The main advantage of using an anonymous class is that it provides reusability of the class. Also anonymous class helps in encapsulation of data. Anonymous class is basically used when only one instance of the class is needed and it has only a short body. By defining an anonymous class, it does the same steps of defining a local class and instantiating it. The anonymous class is rightly used after it is defined. Following specifies an example of anonymous class in C++. class { int a; } c1; Here, c1 is an object of the anonymous class. Usually, anonymous classes in C++ are defined using "typedef" ( a keyword to assign alternative names to existing types). Typedef helps in giving another name to the class. It is shown as below: typedef class { int a; } newclass; newclass c2; Here newclass is the object of the anonymous class and c2 is its instance. Member variables can also be initialized in ano
Read more