aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--ch2/2-08_rightrot.c52
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;
+}