diff options
| -rw-r--r-- | ch2/2-08_rightrot.c | 52 |
1 files changed, 52 insertions, 0 deletions
diff --git a/ch2/2-08_rightrot.c b/ch2/2-08_rightrot.c new file mode 100644 index 0000000..7b157a3 --- /dev/null +++ b/ch2/2-08_rightrot.c @@ -0,0 +1,52 @@ +#include <stdio.h> + +/* The C Programming Language: 2nd Edition + * + * Exercise 2-8: Write a function rightrot(x,n) that returns the value of the + * integer x rotated to the right by n bit positions. + * + * Answer: The problem is a little ambiguous. If we're just moving the bits to + * the right n times, then the solution is a while loop combined with >>, which + * I think is much too easy. So I'm going with what I think it is: wrapping the + * bits around when they've reached the rightmost bit. It's more interesting + * and a _bit_ more difficult. Oh I kill me sometimes, ha. + * + * The trick is to determine whether masking the rightmost bit off changes the + * number that x is. If it does, then it's clear that the leftmost bit needs + * to be 1, but only after we've right-shifted x to accomodate. This requires + * a local mask variable. + * + * Due to the way shifting works, I have to establish the mask as ~0 first. + * Further bit manipulation must be done in a second statement, I assume + * because the ~ operator changes the bits that are filled in when you shift, + * too. This screws with our manipulation, so either my solution is + * suboptimal or it's just a side effect of the arithmetic. + */ + +unsigned rightrot(unsigned x, unsigned n) { + unsigned mask = ~0; + /* For some reason, I can't assign this value all at once. + * I have to assign it to all-ones, then use a separate + * statement to mess with it again... + */ + mask = ~(mask >> 1); + while (n > 0) { + /* If x is different after masking the last bit, there's a 1 in the far + * right bit and we know we need a 1 at the far left */ + if (x > (x & (~0 << 1))) { + x = x >> 1; + x = x | mask; + } else { + x = x >> 1; + } + n--; + } + return x; +} + +int main() { + printf("rightrot(3052, 3) produces %u\n", rightrot(3052, 3)); + printf("rightrot(1, 1) produces %u\n", rightrot(1, 1)); + printf("rightrot(4096, 4) produces %u\n", rightrot(4096, 4)); + return 0; +} |