C program to rotate bits of a number

Bitwise operator exercises

C Basics C Programming Tutorial
Basic C Exercises Bitwise Operator Exercises Conditional Operator Exercises If else Exercises Switch case Exercises Loop Exercises Star Patterns Number Patterns Functions Exercises Array Exercises String Exercises Pointer Exercises File handling Exercises
Data Structures

C program to rotate bits of a number

Write a C program to input a number and rotate bits of number using bitwise shift operators. How to rotate bits of a given number using bitwise operator in C programming. Logic to left or right rotate bits of a number using bitwise shift operator in C program.

Required knowledge

Operators, Data Types in c, Variables in C, Basic input/output, What is function

What is meant by rotating bits of a number

Rotating bits of a number to left, means shifting all bits to left and pushing the dropped Most Significant Bit to Least Significant Bit.

Rotating bits of a number to right, means shifting all bits to right and pushing the dropped Least Significant Bit to Most Significant Bit.

Rotating bits of -15 two times to right.

There is small difference in logic of left and right rotation of number. I have explained logic of both problems separately.

Logic to left rotate bits in a number

Left rotation of bits in C is supported using bitwise left shift operator <<. But left shift operator drops Most Significant Bit (MSB) on each shift. Which is what we don't want. Instead of dropping MSB on each rotation, Least Significant Bit (LSB) should get replaced as dropped MSB.

Step by step descriptive logic to left rotate bits of a number.

  1. Input number to rotate and rotation amount from user. Store it in some variable say num and rotation.

  2. Find most significant bit of the number that is about to drop and store it in some variable say DROPPED_MSB = (num >> INT_BITS) & 1.

  3. Left Shift num one times and set its least significant bit to DROPPED_MSB i.e. perform num = (num << 1) | DROPPED_MSB.

  4. Repeat step 2 and 3 for given number of rotations.

Logic to right rotate bits of a number

Right rotation of bits in C programming is supported using bitwise right shift operator >>. Similar to left shift, right shift operations also results in bit loss. On every shift operation the least significant bit is dropped.

What we need to do is, instead of dropping the least significant bit replace most significant bit with the dropped least significant bit.

Step by step descriptive logic to right rotate bits of a number.

  1. Input number to rotate and rotation amount from user. Store it in some variable say num and rotation.

  2. Find least significant bit of the number about to drop and store it in some variable say DROPPED_LSB = num & 1.

  3. Right shift number one time i.e. perform num = num >> 1.

  4. Clear most significant bit of number i.e. perform num = num & (~(1 << INT_BITS)).

  5. Set the DROPPED_LSB as most significant bit of num. Perform num = num | (DROPPED_LSB << INT_BITS).

  6. Repeat step 2 to 5 for given number of rotations.


    Note: INT_BITS is total number of bits in integer - 1.

Program to rotate bits of a number



/**
 * C program to rotate bits of a number.
 */


#include <stdio.h>

#define INT_SIZE sizeof(int)        // Size of int in bytes
#define INT_BITS INT_SIZE * 8 - 1   // Size of int in bits - 1


/* Function declarations */
int rotateLeft(int num, unsigned int rotation);
int rotateRight(int num, unsigned int rotation);


int main()
{
    int num;
    unsigned int rotation;

    /* Input number from user */
    printf("Enter a number: ");
    scanf("%d", &num);

    /* Input number of rotation */
    printf("Enter number of rotation: ");
    scanf("%u", &rotation);


    /* Print rotated number */
    printf("%d left rotated %u times = %d\n\n",  num, rotation, rotateLeft(num, rotation));
    printf("%d right rotated %u times = %d\n", num, rotation, rotateRight(num, rotation));


    return 0;
}



/**
 * Function to rotate bits of a number to left.
 *
 * @num         Number to rotate.
 * @rotation    Number of times to rotate left.
 */
int rotateLeft(int num, unsigned int rotation)
{
    int DROPPED_MSB;

    // The effective rotation
    rotation %= INT_BITS;


    // Loop till rotation becomes 0
    while(rotation--)
    {
        // Get MSB of num before it gets dropped
        DROPPED_MSB = (num >> INT_BITS) & 1; 

        // Left rotate num by 1 and 
        // Set its dropped MSB as new LSB
        num = (num << 1) | DROPPED_MSB;
    }

    return num;
}



/**
 * Function to rotate bits of a number to right.
 *
 * @num         Number to rotate.
 * @rotation    Number of times to rotate right.
 */
int rotateRight(int num, unsigned int rotation)
{
    int DROPPED_LSB;

    // The effective rotation
    rotation %= INT_BITS;


    // Loop till rotation becomes 0
    while(rotation--)
    {
        // Get LSB of num before it gets dropped
        DROPPED_LSB = num & 1;

        // Right shift num by 1 and 
        // Clear its MSB
        num = (num >> 1) & (~(1 << INT_BITS));

        // Set its dropped LSB as new MSB
        num = num | (DROPPED_LSB << INT_BITS);
    }

    return num;
}


Note: I have used %u format specifier for unsigned int. Learn about various format specifiers used in C.

To short the logic you can combine all bitwise operations as one. You can further decay above two functions as.



int rotateLeft(int num, unsigned int rotation)
{
    rotation %= INT_BITS;

    while(rotation--)
        num = (num << 1) | (1 & (num >> INT_BITS));

    return num;
}

int rotateRight(int num, unsigned int rotation)
{
    rotation %= INT_BITS;

    while(rotation--)
        num = ((num >> 1) & (~(1 << INT_BITS)) | ((num & 1) << INT_BITS));

    return num;
}


Output:

Enter a number: -15
Enter number of rotation: 2

-15 left rotated 2 times = -57
-15 right rotated 2 times = 2147483644



Recommended posts



Instagram


C Programming


Subscribe to: Posts (Atom)