KnR excersice 2-8 : Rotate a number to the right. Is this ok?

Question

I'm following KnR. This is excercise 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 SO 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;
}

EDIT : To accommodate what i'v 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;
}

I wonder why the function returns a different type to the `num` passed. — Weather Vane, Dec 27 '14 at 17:51
Because shifting signed bits are tricky (and probably not what i should be doing). So kept the input as unsigned. Didn't think about keeping the output type unsigned though! — Somjit, Dec 27 '14 at 17:53
and also, i was thinking of a logical shift, not an arithmetic one. — Somjit, Dec 27 '14 at 17:54
@pmg : yup, i would, but this was just a barebones 'lets-see-what-happens-if-i-do-this' kinda code. so kept it minimal. — Somjit, Dec 27 '14 at 17:56
But the function should still return the same type as passed. — Weather Vane, Dec 27 '14 at 18:09
This is kind-of silly, just test the function. Just for your info, I can already tell you that it's not okay because shift operations that exceed the number of bits in the integer are undefined. Oh, and please avoid casts and use the correct type from the start. — Ulrich Eckhardt, Dec 27 '14 at 18:12
Leave that up the the caller, be consistent. I thought you didn't want to mess with signed values. — Weather Vane, Dec 27 '14 at 18:12
There's also a magic number in that code, you probably mean CHAR_BITS (or something like that, just search the web) instead of hardcoding 8 bits for a char, which is very common but still not guaranteed. — Ulrich Eckhardt, Dec 27 '14 at 18:14
Well, `sizeof` provides the size in multiples of a char, not in multiples of a byte. The intention is for those two to be mostly synonymous though. Still, a byte is only almost always an octet. — Ulrich Eckhardt, Dec 27 '14 at 18:16
@Somjit here is a previous SO question about rotating signed values. http://stackoverflow.com/questions/13544519/bitwise-shift-operators-on-signed-types — Weather Vane, Dec 27 '14 at 18:18
@WeatherVane : hey thanks for that. Going by the answers to the OP's 1st question (what happens if num is signed negative) , which is undefined behavior, i can just add a disclaimer to the user that negative rotating is undefined. That would eliminate the type mismatch i had to put in thinking of MSB=1 in case of signed negative. — Somjit, Dec 27 '14 at 18:21
As long as `rbits` is in the range 0 to "bit width - 1", this is OK. — chux - Reinstate Monica, Dec 27 '14 at 18:22
@chux why not 0..bitwidth? The left shift would be bitwidth..0 bits. — Weather Vane, Dec 27 '14 at 18:22
@Weather Vane "If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined." C11 §6.5.7 3 — chux - Reinstate Monica, Dec 27 '14 at 18:24
OK thanks, though I am surprised that shifting out every bit is undefined. — Weather Vane, Dec 27 '14 at 18:24
@chux : its really amazing how u guys fish out these extracts so quickly.. — Somjit, Dec 27 '14 at 18:32
@Somjit Decades of experience [Grasshopper](http://en.wikipedia.org/wiki/Kung_Fu_(TV_series)#Overview). — chux - Reinstate Monica, Dec 27 '14 at 18:50
@Weather Vane Note: early 8086/8088 processors bit shift opcode did shift out every bit in the range 0-255. Values pass 16 made no functional difference to a 16-bit reg. This instruction, which couldn't be interrupted, did 1 shift/clock. It became the worst case command, taking 255 clock ticks to complete. So if a critical interrupt occurred in tick 1, 250+ ticks had to pass before the interrupt could be serviced-that is a significant [interrupt latency](http://en.wikipedia.org/wiki/Interrupt_latency). Following processors used only the 5 least significant bits of the shift for 32-bit shift. — chux - Reinstate Monica, Dec 27 '14 at 18:59
@chux That sounds like quite the oversight on Intel's part. Glad they fixed it! — , Dec 27 '14 at 19:03
@chux I can see there is no *point* rotating by bitwidth but I don't see why undefined. There are other undefined operations too, such as incrementing an integer value past INT_MAX, both of these examples are very well defined behaviour when working in assembler, so are these UB conditions *policy* rather than physical limitation? (BTW I worked with 8086/88 :-) — Weather Vane, Dec 27 '14 at 19:40
@WeatherVane not everything is an x86 (nor a VAX) strange architectures exist, and they need to be supported by a generic standard. — wildplasser, Dec 27 '14 at 19:56
@WeatherVane: on the instruction leven there *could be* a reason for shifting more than the wordsize. In some archtectures the carry flag (or other flags) could be affected. (x86 actually has two shi/rot instructions: RO[LR] and SH[LR]) — wildplasser, Dec 27 '14 at 20:01
@WeatherVane As to "don't see why undefined", IDK. Best guess: it was most accommodating to various processors of the day. It certainly is easier to implement in hardware a rotation, using only using the least significant bits of the shift amount and ignoring the rest. — chux - Reinstate Monica, Dec 27 '14 at 21:58
@wildplasser you were probably not familiar enough with 8086/88 to know there are 3 left shift/rotate and 4 right shift/rotate instructions. — Weather Vane, Dec 27 '14 at 23:34

score 1 · Answer 1 · answered Dec 27 '14 at 19:50

1st edition of code was good, but 2nd version is getting overly complicated. Suggest using unsigned numbers to simplify.

Since code is rotating the bits, rotating the N times bit width is the same as rotating 0. IOW, 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;  // compiler likely to change this to rbits &= RBIT_MASK;
  unsigned mask = num << ((BIT_WIDTH - rbits) % BIT_WIDTH);
  return (num >> rbits) | mask;
}

why '// compiler likely to change this to rbits &= RBIT_MASK;' ? — Somjit, Dec 28 '14 at 03:50
@Somjit `BIT_WIDTH` is a constant. It is likely a power-of-2. In that case `rbits %= BIT_WIDTH` is equivalent to `rbits &= RBIT_MASK` and `&=` is a fast instruction - likely faster than `%=`. — chux - Reinstate Monica, Dec 28 '14 at 06:10

KnR excersice 2-8 : Rotate a number to the right. Is this ok?

1 Answers1