The C Programming Language, 2nd Edition, by Kernighan and Ritchie
Exercise 2.08 on page 49
Write a function rightrot(x,n)
that returns the value of the integer x
rotated to the right by n
bit positions.
Solution by Vidhan Gupta
/* Write a function rightrot(x,n) that returns the value of the integer x rotated to the right by n bit position. */ #include <stdio.h> // Function prototype for rightrot unsigned rightrot(unsigned x, int n); // Function prototype for printing integers in binary form void print_binary(unsigned x); // Main Function int main() { print_binary(245); print_binary(rightrot(245,5)); return 0; } // Function that rotates x to the right by n bit position. unsigned rightrot(unsigned x, int n) { return (x>>n) | ((x & ~(~0<<n)) << (sizeof(x)*8 - n)); } // Function to print binary of unsigned integer void print_binary(unsigned x) { int n = sizeof(x) * 8; for (int i = n - 1; i >= 0; i--) { int curBit = (x >> i) & 1; printf("%d", curBit); } printf("\n"); }
OUTPUT: 00000000000000000000000011110101 10101000000000000000000000000111
Solution by Gregory Pietsch (Cat 0)
unsigned rightrot(unsigned x, unsigned n) { while (n > 0) { if ((x & 1) == 1) x = (x >> 1) | ~(~0U >> 1); else x = (x >> 1); n--; } return x; } /* main driver added, in a hurry while tired, by RJH. Better test driver suggestions are welcomed! */ #include <stdio.h> int main(void) { unsigned x; int n; for(x = 0; x < 700; x += 49) for(n = 1; n < 8; n++) printf("%u, %d: %u\n", x, n, rightrot(x, n)); return 0; }
Solution by Bob Wightman (Cat 1)
/* K&R exercise 2-8 It is class 1 due to the /sizeof/ operator (CHAR_BIT is introduced with <limits.h> in Chapter 1). I could have used the conditional operator but thought that this is clearer. Notes: 1. Implicit int removed (not absolutely necessary but...) 2. Checks for the size of the shift and reduces it to the range 0 - (number of bits in an int) - 1 This is to avoid right shifting the number into oblivion. 3. If either the value or the shift is zero then nothing need to be done to the parameter so just return it. */ unsigned int rightrot(unsigned int x, unsigned int n) { /* calculate number of bits in type */ size_t s = sizeof(x) * CHAR_BIT; size_t p; /* limit shift to range 0 - (s - 1) */ if(n < s) p = n; else p = n % s; /* if either is zero then the original value is unchanged */ if((0 == x) || (0 == p)) return x; return (x >> p) | (x << (s - p)); } /* Driver based on yours but runs the shift values beyond the size of an unsigned integer on any system */ int main(void) { unsigned int val; unsigned int pos; unsigned int max = sizeof (pos) * CHAR_BIT + 1; for(val = 0; val < 700; val += 49) { for(pos = 0; pos < max; ++pos) { printf("%u, %d: %u\n", x, n, rightrot(val, pos)); } } }
Solution by Pilcrow
This seems simpler to me. The function asbits (see my solution to Ex 2-6) is now in the header "pilcrow.h", as is getbits from K&R.
#include <stdio.h> #include "pilcrow.h" unsigned int rightrot(unsigned int x, int n) { int m, i; for(i=0; i < n; i++) { m = getbits(x, 0, 1); m <<= (sizeof(m)*8-1); x >>= 1; x |= m; } return x; } int main(void) { unsigned int x = 0xabcdef12; int n = 8; printf("rotate right %u bits\n", n); asbits(x,sizeof(x),1); asbits(rightrot(x,n),sizeof(x),1); return 0; }
Solution by `artlite
I started recent, but may be this?
#include "stdafx.h" unsigned rightrot(unsigned x, int n); int main(void) { printf("%u\n", rightrot(8, 5)); return 0; } unsigned rightrot(unsigned x, int n){ return x >> n | ((x & (~(~0 << n))) << (8 - n)); }
Solution by Jorje
#include <stdio.h> unsigned rightrot(unsigned, int); void get_param_values(unsigned *, int *); int main() { unsigned x; int p, n; get_param_values(&x, &n); printf("rightrot(%u, %d) = %u\n", x, n, rightrot(x, n)); return 0; } unsigned rightrot(unsigned x, int n) { return (x >> n) | ((x & ~(~0 << n)) << (sizeof(x) * 8 - n)); } void get_param_values(unsigned *x, int *n) { printf("x: "); scanf("%u", x); printf("n: "); scanf("%d", n); }
Solution by Luke Panayi
Simplified version of Gregory's category 1 solution
#include <stdio.h> unsigned rotright(unsigned x, int n) { /* Example with x = 11010101 (213 in decimal), n = 2 First iteration: x = (01101010) | ~(11111111 >> 1) = 11101010 Second iteration: x = (01110101) | ~(11111111 >> 0) = 01110101 Returns 01110101 - in reality returns 32 bits, the result in these comments will not convert to the correct result, however sticking with 8 bits for readability/simplicity in explanations. */ for (; n > 0; n--) x = (x >> 1) | ~(~0U >> (x & 1)); //must be unsigned or you're right shifting a signed int which behaviors differently on different machines! return x; } int main() { printf("%d\n", rotright(213, 2)); return 0; }
Solution by Cromagnon (Category 0)
This solution uses the type char by default, because it is easy to understand bitwise operation in a byte/char.
To change the default type, set the preprocessor macro TYPE
to another unsigned integer type.
Change SAMPLE
and NUM
to use another value and rotation number, respectivelly.
Also, check my optimized solution.
This is a Category 0 solution.
#include <stdio.h> #include <limits.h> #define TYPE char #define SAMPLE 0XAB #define NUM 3 unsigned TYPE rightrot(unsigned TYPE x, TYPE n); int main(void) { printf("%X\n", rightrot(SAMPLE,NUM)); return 0; } /* rightrot: rotate to the right by n bit positions */ unsigned TYPE rightrot(unsigned TYPE x, TYPE n) { for (; n > 0 ; n--) x = (x >> 1) | ~((unsigned TYPE) (~0) >> (x & 1)); return x; }
Solution by Cromagnon (Category 1)
Same as my non-optimized solution.
This solution is category 1 because it uses the operator sizeof, which have not been covered at the point in the book at which the exercise appears.
Using sizeof takes out the need for a loop in the function.
This is a Category 1 solution.
#include <stdio.h> #include <limits.h> #define TYPE char #define SAMPLE 0XAB #define NUM 3 unsigned TYPE rightrot(unsigned TYPE x, TYPE n); int main(void) { printf("%X\n", rightrot(SAMPLE,NUM)); return 0; } /* rightrot: rotate to the right by n bit positions */ unsigned TYPE rightrot(unsigned TYPE x, TYPE n) { unsigned int s; s = sizeof x * CHAR_BIT; n = n % s; return (x >> n) | (x << (s - n)); }
Solution by Codybartfast (category 0)
unsigned rightrot(unsigned x, unsigned n) { unsigned bits = sizeof_uint(); if (n == 0 || n == bits) return x; return (x >> n) | x << (bits - n); } /* size of uint in bits */ int sizeof_uint(void) { unsigned x2, x = 1; int bits = 1; while (x < (x2 = x * 2)) { x = x2; ++bits; } return bits; }
Solution by anonymous
getbits based on book and printBinary based on Pilcrow's asbits. The p and n values were set to unsigned chars since the values must be positive and valid values should never be much longer than 64 based on the current minimum size of long long ints (64 bits). If a system has a data type that is larger than 256 bits, than it would be necessary to change the data type to a short or int
Comments were added to thoroughly explain what is going on.
#include <stdio.h> /* 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 */ int getbits(int x, unsigned char p, unsigned char n); void printBinary(int x, size_t size); unsigned int rightrot(unsigned int x, unsigned int n); int main(void) { unsigned int x = 0xBEEFCAFE; // 1011 1110 1110 1111 1100 1010 1111 1110 printBinary(x, sizeof(x)); x = rightrot(x, 63); // equivalent to x = rightrot(x, 31); when ints are 32 bits printBinary(x, sizeof(x)); return 0; } // returns the value of the integer x rotated to the right by n bit positions // x is unsigned to ensures that when it is right-shifted, vacated bits will be filled with zeros, not sign bits, regardless of the machine the program is run on. unsigned int rightrot(unsigned int x, unsigned int n) { // get the number of bits in x size_t size = sizeof(x) * 8; // reduce n to be within the bounds of the bit size of x without messing up the final location of the bits from rotating (the modulo operator is perfect for this) // for example if n is 16516 and int size is 32, then after 516 complete rotations (the bits are back in the same place as last time), // the bits will only be rotated 4 more times (16516 % 32 = 4). So rotating by 4 instead of 16516 not only reduces the program complexity, but prevents // an undefined behavior of shift count overflows. Plus, shifting by the exact size of the data type (e.g. 32 bit >> 32) doesn't seem to work (returns 0 every time in tests), // but the remainder will be 0 if it is the same size so it will have the desired effect of rotating completely around to the exact same spot (so not rotating has the same value) // so this accurately handles n > size and n == size n %= size; // first, right shift x by n to get right side bits aligned. Next, get the total size and subtract n // to get the amount to left shift. Left shift x by that value to get the left side values // then merge them together with bitwise OR return (x >> n) | (x << (size - n)); /* For example: this is what would happen if rightrot(0xBEEFCAFE, 63); was called: size = sizeof(x) * 8 size = 4 * 8 size = 32 n %= size n = 63 % 32 n = 31 (x >> n) | (x << (size - n)) (0xBEEFCAFE >> 31) | (0xBEEFCAFE << (32 - 31)) (10111110111011111100101011111110 >> 31) | (10111110111011111100101011111110 << 1) (0000000000000000000000000000000 -> 10111110111011111100101011111110) | (10111110111011111100101011111110 <- 0) (00000000000000000000000000000001) | (01111101110111111001010111111100) return 01111101110111111001010111111101 */ } // prints out the binary representation of a value void printBinary(int x, size_t size) { int i; for(i = size * 8 - 1; i >= 0; i--) { if (getbits(x, i, 1) == 1) printf("1"); else putchar('0'); // printf("0"); was here but clc-wiki <c> code blocks apparently don't allow "0" unless it is in a comment. Bug? if(i % 4 == 0) printf(" "); } printf("\n"); } // get n bits from position p. Does not support negative numbers for p or n, p is zero based index // doesn't seem to care if right shift is arithmetic or logical. Returns -1 if p and/or n is invalid int getbits(int x, unsigned char p, unsigned char n) { size_t size = sizeof(x) * 8; char shift = p + 1 - n; if (p >= size || shift < 0) return -1; else if (n == size && shift == 0) return x; return (x >> shift) & ~(~0ULL << n); }
Solution by Foowar
/* * exercise 2-8: * * Write a function rightrot(x,n) that returns the value of integer x rotated * to the right by n bit positions. */ /* * I implemented 2 solution, the first one does not rely on the size of unsigned int * but the second one does. */ unsigned int rightrot(unsigned int x, int n) { int i; unsigned int mask; /* set the left most bit to 1, others to 0 */ mask = ~(~0u >> 1); for (i = 0; i < n; ++i) { if (x % 2 == 0) { /* first bit 0 */ x >>= 1; } else { /* first bit 1 */ x >>= 1; x |= mask; } } return x; } unsigned int rightrot(unsigned int x, int n) { int get_uint_size(void); unsigned int bits; int uint_size = get_uint_size(); n %= uint_size; bits = ~(~0 << n); bits &= x; bits <<= uint_size - n; x >>= n; return x | bits; } int get_uint_size(void) { unsigned int x; int len; x = ~0; len = 0; while (x != 0) { x >>= 1; ++len; } return len; }