Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

The C Programming Language (K&R) exercise 2-8: Rotate a number to the right. Is this OK?

I'm following The C Programming Language (K&R). This is exercise 2-8. It says to create a function to rotate a number to the right by some number of bits.

The answer I came up with 'seems' to do the job, and in two lines. However, I was checking for other methods online. This Stack Overflow answer talks about a shifting each bit one by one. What is wrong if I shift in bulk (as in my code below)? Is there something I'm missing?

#include <stdio.h>

/* Rotate number 'num' to the right by 'rbits' bits */

int RotRight(unsigned int num, int rbits) {

    unsigned int mask = num << ((sizeof(int)*8)-rbits);
    return (num>>rbits)|mask;
}

To accommodate what I’ve learnt from the comments, here is an edited version of the above code. Does this look good?

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int RotRight(int num, int rbits) {

    if(num<0) {
        fprintf(stderr, "Rotating negative numbers is undefined\n");
        exit(EXIT_FAILURE);
    }

    if(rbits >= sizeof(int)*CHAR_BIT)
        rbits = rbits % (sizeof(int)*CHAR_BIT);

    if(rbits <= 0)
        return num; // rbit range should be 0 to (bitwidth - 1)

    unsigned int mask = num << ((sizeof(int)*CHAR_BIT)-rbits);
    return (num>>rbits)|mask;
}
like image 987
Somjit Avatar asked Dec 05 '25 08:12

Somjit


1 Answers

The first edition of code was good, but the second version is getting overly complicated. I suggest using unsigned numbers to simplify.

Since the code is rotating the bits, rotating the N times bit width is the same as rotating 0. In other words, we only need to use the least-significant bits of the shift count.

#include <stdio.h>
#include <limits.h>

/* Rotate number 'num' to the right by 'rbits' bits */

unsigned RotRight(unsigned num, unsigned rbits) {
  #define BIT_WIDTH (CHAR_BIT * sizeof num)
  #define RBIT_MASK (BIT_WIDTH - 1)
  rbits %= BIT_WIDTH;  // The compiler is likely to change this to rbits &= RBIT_MASK;
  unsigned mask = num << ((BIT_WIDTH - rbits) % BIT_WIDTH);
  return (num >> rbits) | mask;
}
like image 96
chux - Reinstate Monica Avatar answered Dec 09 '25 14:12

chux - Reinstate Monica