In Computer Engineering and in Systems with Microcontrollers areas of interest, performing **bit operations** is quite usual. In this tutorial we are going to learn what **bit shifting** and **bit rotation** means, an how to implement some simple algorithms in Scilab.

We are going to focus on:

**left / right bit shifting****left / right bit rotation**

For simplicity, in our examples, we are going to use only **unsigned (positive) integers**.

Any **decimal** number can be represented in **binary** format and vice-versa. To recall how to perform a decimal to binary and back to decimal conversion, read the articles Decimal to Binary Conversion and Binary to Decimal Conversion. Further, for a better understanding on the types of number representations, read the article Numbers Representation Systems – Decimal, Binary, Octal and Hexadecimal.

For an easy conversion from decimal to binary, we can use the Scilab functions `dec2bin()`

and `bin2dec()`

. For example, the decimal value `60`

is represented in binary as `00111100`

:

`--> dec2bin(60,8)`

`ans =`

`00111100`

`-->`

`--> bin2dec('00111100')`

`ans =`

` 60.`

`-->`

The number `8`

in the `dec2bin()`

function states how many bits we use to represent the binary notation.

**Bit shifting and bit rotation** means moving bits from one position to another. There are similarities between bit shifting and bit rotation, the former having the property of keeping all the values of the bits, not loosing any.

### Left and right bit shifting

Bit shifting means moving the position of the bits in the left direction or in the right direction. For example, if we write in binary form the decimal number `23`

, we get `00010111`

. If we shift all bits left with one position, we’ll get `00101110`

. Bit 7 (MSB) was replaced by bit 6, bit 6 by bit 5 and so on.

Generally speaking, when shifting bits to left, bit *n* is replaced by bit *n-1* and LSB becomes `0`

.(see image below).

Since bit 0 was moved into position 1, a new bit 0 is stuffed in, with the value 0. After shifting, with one position, we got a new binary number. If we convert it to decimal, we get:

`--> bin2dec('00101110')`

`ans =`

` 46.`

`-->`

Our initial decimal number was `23`

, after shifting the bits left with one position we got `46`

, which is twice the initial value. Let see what happens if we shift the bits left but with two positions. We’ll get the binary number `01011100`

, which in decimal is:

`--> bin2dec('01011100')`

`ans =`

` 92.`

`-->`

Again, the final number `92`

is twice the initial one (`46`

). We can now conclude that **left bit shifting** with *n* positions means **multiplying** the initial number with *2 ^{n}*.

What about **right bit shifting**? As the name suggests, the bits are moved to the right. Generally speaking, when shifting bits to the right, bit *n* is replaced by bit *n+1* and MSB becomes `0`

(see image below).

If we take the same example, decimal `23`

in binary is `00010111`

. Shifting to the right with one position will result in the binary number `00001011`

. Converting to decimal representation gives `11`

:

`--> bin2dec('00001011')`

`ans =`

` 11.`

`-->`

Let’s shift the bits right but with two positions. Our binary number is now `00000101`

which in decimal notation is `5`

.

`--> bin2dec('00000101')`

`ans =`

` 5.`

`-->`

**Right bit shifting** is the equivalent of **dividing** the decimal number with *2 ^{n}*, where

*n*is the number of positions to shift. Only the integer part of the division is kept,

`23`

shifted right with one position gave `11`

, which is the integer part of `23/2 = 11.5`

.### Scilab implementation of left and right bit shift

Scilab does not contain embedded functions for bit shifting. To overcome this limitation we are going to implement a custom Scilab function for bit shifting, defined as:

`y=bitshift(str,dir,n,bit)`

where:

`str`

– string, defines the binary representation of a decimal number

`dir`

– string, represents the direction of the bit shifting; can take only two values `'l'`

for left or `'r'`

for right

`n`

– scalar, defines the number of positions to shift

`bit`

– scalar, represents the number of bits for the output; can take only the following values: `8`

, `16`

, `32`

or `64`

.

`y`

– string, the return of the function, represents the binary number after the bit shift operation

Open a new Scilab script file and copy and paste the instructions below:

function y=bitshift(str,dir,n,bit) dec=bin2dec(str); switch bit case 8 if dir=='r' then y=dec2bin(uint8(dec/(2^n)),bit); elseif dir=='l' then y=dec2bin(uint8(dec*(2^n)),bit); end case 16 if dir=='r' then y=dec2bin(uint16(dec/(2^n)),bit); elseif dir=='l' then y=dec2bin(uint16(dec*(2^n)),bit); end case 32 if dir=='r' then y=dec2bin(uint32(dec/(2^n)),bit); elseif dir=='l' then y=dec2bin(uint32(dec*(2^n)),bit); end case 64 if dir=='r' then y=dec2bin(uint64(dec/(2^n)),bit); elseif dir=='l' then y=dec2bin(uint64(dec*(2^n)),bit); end end endfunction

The Scilab functions `uint8()`

, `uint16()`

, `uint32()`

and `uint64()`

are used to format the decimal value on the corresponding number of bits as the function argument `bit`

. For a better understanding of the **if-else** and **switch-case** routines, read the articles Scilab programming – IF ELSE conditional statements and Scilab programming – SELECT CASE conditional statements.

Save the script file as `bitshift.sci`

and execute it. Now you can use it in the Scilab console.

Let’s shift left, one position, the binary number `00111100`

:

`--> bitshift('00111100','l',1,8)`

`ans =`

` 01111000`

`-->`

If we want to display the same result on 32 bits, we need to change the `bit`

argument as:

`--> bitshift('00111100','l',1,32)`

`ans =`

` 00000000000000000000000001111000`

`-->`

Same binary number shifted right, four positions and displayed on 16 bits:

`--> bitshift('00111100','r',4,16)`

`ans =`

` 0000000000000011`

`-->`

If we don’t know the binary representation of the number on which we want to bit shift, we can call the function replacing the `str`

argument with the` dec2str()`

function. Example:

`--> bitshift(dec2bin(23),'l',2,8)`

`ans =`

` 01011100`

`-->`

If we want to work only with decimal numbers, we can also put the function `bitshift()`

as an argument for the `bin2dec()`

function. Example:

`--> bin2dec(bitshift(dec2bin(23),'l',2,8))`

`ans =`

` 92.`

`-->`

### Left and right bit rotation

**Bit rotation** is similar to bit shift. It actually is bit shift but with a difference. The end bits, MSB or LSB are not any more lost and they come back on the other side of the string. Bit rotation is also known as **circular bit shift**.

When performing **left bit rotation**, with one position, bit *n* is replaced by bit *n-1*, and MSB comes at the back of the queue, replacing LSB.

Let’s take as example the decimal number `157`

. It’s binary representation is `10011101`

. If we rotate left, one position, we get `00111011`

, or decimal `59`

.

`--> dec2bin(157)`

` ans =`

`10011101`

`--> bin2dec('00111011')`

` ans =`

`59.`

`-->`

**Right bit rotation** has the same principle, the difference being that LSB is replacing MSB and bit *n* is replaced by bit *n+1*.

If we perform right bit rotation to the decimal number `59`

, we’ll get back our initial number `157`

. This is because we rotate back the bits on the initial positions, and `00111011`

becomes `10011101`

.

### Scilab implementation of left and right bit rotation

Scilab doesn’t contain embedded functions for performing bit rotations. Thus, we are going to implement a custom Scilab function to perform **bit rotation**.

An efficient way of doing it is to split the bit rotation into 3 steps:

- left bit shift by
*n*positions - right shift by (
*NB – n*) positions, where*NB*is the number of bits (8, 16, 32 or 64) - perform a logical OR between the results

For a better understanding of the algorithm, let’s assume that we have the following 8 bit binary number and we want to rotate it left with 3 positions.

`b7 b6 b5 b4 b3 b2 b1 b0`

1. shift left with 3 positions

`b4 b3 b2 b1 b0 0 0 0`

2. shift right (the initial representation) with 8-3=5 positions

`0 0 0 0 0 b7 b6 b5`

3. perform a bit OR operation

`b4 b3 b2 b1 b0 b7 b6 b5`

As you can see, **bit rotation** (also known as **circular bit shift**) can be performed using left, right bit shifts and bit OR operations. The same principle applies to right bit rotation but with reversed bit shift operations.

With this is mind, let’s design a Scilab function which performs bit rotations. The syntax of the function is:

`y = bitrot(str,dir,n,bit)`

where:

`str`

– string, defines the binary representation of a decimal number

`dir`

– string, represents the direction of the bit rotation; can take only two values, `'l'`

for left or `'r'`

for right

`n`

– scalar, defines the number of positions to rotate

`bit`

– scalar, represents the number of bits for the output; can take only the following values: `8`

, `16`

, `32`

or `64`

.

`y`

– string, the return of the function, represents the binary number after the bit shift operation

As you can see, the arguments of the `bitrot()`

function are defined in the same way as the arguments of the `bitshift()`

function.

Open a new Scilab script file and copy and paste the instructions below:

function y = bitrot(str,dir,n,bit) if dir=='l' then LS = bitshift(str,'l',n,bit); RS = bitshift(str,'r',bit-n,bit); elseif dir=='r' then RS = bitshift(str,'r',n,bit); LS = bitshift(str,'l',bit-n,bit); end y = dec2bin(bitor(bin2dec(LS),bin2dec(RS)),bit); endfunction

For left and right bit shifting we are using the `bitshift()`

function defined above. `LS`

and `RS`

are local variables representing the Left Side and Right Side of the bit OR operation.

To perform the bit OR operation we used the Scilab `bitor()`

function. Notice that this function expects decimal inputs and returns also decimal outputs. That is why we used `bin2dec()`

and `dec2bin()`

functions for conversion.

Save the file as `bitrot.sci`

and execute it. Now it can be called in the Scilab console.

Let’s test our function using the bit rotation example above:

`--> bitrot('10011101','l',1,8)`

` ans =`

`00111011`

`-->`

`--> bin2dec(ans)`

` ans =`

`59.`

`-->`

Let’s rotate the binary number `11111111`

to the right, 4 positions and display the result on 32 bits:

`--> bitrot('11111111','r',4,32)`

` ans =`

`11110000000000000000000000001111`

`-->`

If we want to use decimal numbers instead of binary representation strings, we can use the `dec2bin()`

function instead of the `str`

argument:

`--> bitrot(dec2bin(65535),'l',22,32)`

` ans =`

`11111111110000000000000000111111`

`-->`

We can return the result of the bit rotation into a decimal value, by using the `bitrot()`

function as argument for the `bin2dec()`

function:

`--> bin2dec(bitrot(dec2bin(127),'r',8,16))`

` ans =`

`32512.`

`-->`

Bit shift and bit rotate functions are used in **cryptographic hash algorithms**. For example **SHA-256** (Security Hash Algorithm-256) contains several bit shift and rotate operations in its algorithm.

For any questions, observations and queries regarding this article, use the comment form below.

Don’t forget to Like, Share and Subscribe!