From 927df414819f236b900f9f0d925b1a6a9385c115 Mon Sep 17 00:00:00 2001 From: zlg Date: Thu, 4 Apr 2013 06:12:40 -0500 Subject: Solve Exercise 2-8: rightrot() --- ch2/2-08_rightrot.c | 52 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 52 insertions(+) create mode 100644 ch2/2-08_rightrot.c 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 + +/* 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; +} -- cgit v1.2.3-70-g09d2 /.gitignore?h=v0.3b8&id=aef722de5512a4770d91d718194c01bc77844687'>unfollow)
AgeCommit message (Expand)AuthorFilesLines
2018-09-29cli: Add pretty printing to 'list' commandzlg3-17/+107
2018-09-08setup.py: Bump to alpha4 for PyPIzlg1-1/+1
2018-09-08cli: add '--raw' option to list commandzlg2-9/+45
2018-09-08Add remaining filters to vgstash packagezlg1-2/+11
2018-09-04Update LICENSE to match setup.pyzlg1-80/+67
2018-09-03Branch off from master with pytest, tox, clickzlg16-778/+779
2018-03-18Flesh out filter types and ownership statuszlg3-82/+144
2018-03-18README.mdown: break line correctlyzlg1-1/+1
2018-03-18add 'playlog' list filterzlg2-2/+9
2018-03-13Update helpers a bitzlg1-2/+9
2018-03-13Make VGSTASH_DB_LOCATION point to a filezlg2-21/+20
2016-11-18Remove settings from helpers.shZe Libertine Gamer1-5/+0
2016-11-15Correct phrasing in README.Ze Libertine Gamer1-4/+4
2016-11-13DerpZe Libertine Gamer1-0/+1
2016-11-03Improve error handling in shell scriptsZe Libertine Gamer4-3/+23
2016-10-24Correct run_again, add recursionZe Libertine Gamer1-0/+4
2016-10-21Add quotes to correct behavior for arglistZe Libertine Gamer1-1/+1
2016-10-14updater.sh: add recursion, error handlingZe Libertine Gamer1-43/+101
2016-10-14Correct pipe-handling behaviorZe Libertine Gamer1-1/+9
2016-10-12Clarify a method to move between platformsZe Libertine Gamer1-2/+5