Jump to: navigation, search

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);
}
Personal tools