CODEWITHSUNDEEP
cbit-manipulationbit
paupau
paupau

Reputation: 57

Rotate right using bit operation in c

I am trying to come up with a function int rotateRight (int x, int n) that rotates x to the right by n. For example,

rotateRight(0x87654321,4) = 0x76543218

This is what I have so far:

int rotateRight(int x, int n) {
  int mask = (((1 << n)-1)<<(32-n));
  int reserve = (int)((unsigned) (x&mask) >>(32-n));
  return (x << n) | reserve; 
}

However, I am forbidden to use any casting, and the allowed operations are ~ & ^ | + << and >>. Can anyone help me fix this?

Upvotes: 4

Views: 20557

Answers (3)

chux
chux

Reputation: 153456

A rotation is done with a combination of left and right shifts.

Shifting a signed integer's sign bit is a problem. Suggest converting to unsigned to perform the shift. @The Paramagnetic Croissant

An example of implementation-defined behavior is the propagation of the high-order bit when a signed integer is shifted right.

Shifting by the bit width or more is a problem. Limit actual shifting to n modulo Bit_width. OP's (...<<(32-n)); code is a problem when n == 0.

OP's example looks more like a left rotate. Will assume the function should rotate right. (0x87654321,4) --> 0x18765432. @Mark Shevchenko

An int may have a width other than 32.

#include <limits.h>
#define INT_BIT_WIDTH (sizeof (int) * CHAR_BIT)

int rotateRight(int x, int n) {
  unsigned xu = x;
  unsigned nu = n;
  nu %= INT_BIT_WIDTH;
  unsigned y = xu >> nu;
  if (nu > 0) {
    y |= xu << (INT_BIT_WIDTH - nu);
  }
  return y;
}

[Edit] as OP is limited to ~ & ^ | + << >>, use the alternate following code.
Note: This is an issue in rare cases where the width of an int is not a power of 2.

// nu %= INT_BIT_WIDTH;
nu &= INT_BIT_WIDTH - 1;

[Edit2] Thought I would form an unsigned minimalistic solution as inspired by @RPGillespie as OP cannot use %.

#include <limits.h>
#define UNS_WIDTH    (sizeof (unsigned) * CHAR_BIT)
#define UNS_WIDTH_M1 (UNS_WIDTH - 1)

unsigned unsigned_rotate_right(unsigned x, unsigned n) {
  return (x >> (n & UNS_WIDTH_M1)) | (x << ((UNS_WIDTH - n) & UNS_WIDTH_M1));
}

Upvotes: 1

Gillespie
Gillespie

Reputation: 6561

Basically all you have to do is:

  • shift everything right by n bits using right shift: >>

  • shift the bits you want to rotate all the way to the left: <<

  • Combine the shifted right and shifted left bits with or: |

See this code for an example implementation using the function signature you require:

int rotateRight(int x, int n) {

    //if n=4, x=0x12345678:

    //shifted = 0x12345678 >> 4 = 0x01234567
    int shifted = x >> n;

    //rot_bits = (0x12345678 << 28) = 0x80000000
    int rot_bits = x << (32-n);

    //combined = 0x80000000 | 0x01234567 = 0x81234567
    int combined = shifted | rot_bits;

    return combined;
}

This implementation isn't safe though, at least not without a few guarantees - namely that x will always be positive, and n will be positive and always <= 32.

If you pass in a negative integer for shifting, it will work incorrectly since it will sign-extend the left-most bit. If you want this function to work for all integers, you should change all the types from int to unsigned int (that way no sign-extension or negative left-shifting will take place) and then modulo n by 32 (% 32). Here is a safe version of the function:

unsigned int rotateRight(unsigned int x, unsigned int n) {

    //needed so you don't right shift more than int width
    n %= 32;

    //needed so you don't left shift more than int width
    unsigned int leftshift_val = (32-n) % 32 

    unsigned int shifted = x >> n;
    unsigned int rot_bits = x << leftshift_val;
    unsigned int combined = shifted | rot_bits;

    return combined;
}

And golfed down to a single line, for you minimalists:

unsigned rotr(unsigned x, unsigned n) {
    return (x >> n % 32) | (x << (32-n) % 32);
}

Upvotes: 9

Codor
Codor

Reputation: 17605

According to this explanation, rotation can be done with the following implementation.

#include<stdio.h>
#define INT_BITS 32

/*Function to left rotate n by d bits*/
int leftRotate(int n, unsigned int d)
{
   /* In n<<d, last d bits are 0. To put first 3 bits of n at
     last, do bitwise or of n<<d with n >>(INT_BITS - d) */
   return (n << d)|(n >> (INT_BITS - d));
}

Upvotes: 0

Related Questions