Exercise 2-8 (rightrot - Right rotation)

Chapter_2     Exercise_2-7

bitcount     Exercise_2-9

---

---

Exercise 2-8     K&R, p. 49

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.

rightrot.c         download

#include <stdio.h> // for printf(), scanf(), putchar()

#define LENGTH 100 // bits

// rotate x to the right by n bit positions:
unsigned rightrot(unsigned x, int n);
// reverse s[], knowing its length:
void reverse(char s[], int len);
// get the bits of x into bits[], return length of bits[] (no of bits):
int bitstring (char bits[], unsigned x);

int main()
{
char bits[LENGTH];
unsigned x;
int len1, len2, n, diff;

printf("Give a positive integer: ");
scanf("%u", &x);

len1 = bitstring(bits, x);
printf("x: %s\n", bits);

printf("Rotate x to the right by 0 <= n <= %d bit positions:\n", len1);
printf ("n = ");
scanf("%d", &n);

x = rightrot(x,n);
len2 = bitstring(bits, x); // rotated x may be shorter, but not longer
diff = len1 - len2;
while (diff > 0)
{
putchar('0');
diff--;
}
printf("%s\n", bits);

return 0;
}
// rotate x to the right by n bit positions:
unsigned rightrot(unsigned x, int n)
{
char bits[LENGTH];
int len = bitstring(bits, x); // a sort of bitcount would actually suffice here
// len >= n, first portion of x has (len-n) length, the second length n
// save the two portions of x in two masks, then interchange them:
unsigned mask1 = ~(~0 << (len-n)); // ends in (len-n bits) of 1 (the rest are 0)
unsigned mask2 = ~(~0 << n); // ends in n bits 0f 1 (the rest are 0)

mask2 = mask2 & x; // holds second portion (last n bits) of x, the rest is 0
// the second portion of x may have leading 0s
// shifting x to the right may add 1s or 0s at the left end (implementation defined):
x = x >> n; // first portion of x must have a leading 1 or else it is just 0
mask1 = x & mask1; // clear first bits of x (if they were 1)

mask2 = mask2 << (len-n);

return mask2 | mask1; // interchange the two parts of x
}
// reverse s[], knowing its length:
void reverse(char s[], int len)
{
int i = 0, j = len-1;
char temp;

while (i < j)
{
temp = s[i];
s[i] = s[j];
s[j] = temp;
i++;
j--;
}
}
// get the bits of x into bits[], return length of bits[] (no of bits):
int bitstring (char bits[], unsigned x)
{
int i = 0;

if (x == 0)
{
bits[i++] = '0';
bits[i] = '\0';

return i;
}

while (x > 0)
{ // last bit gives the parity:
bits[i++] = '0' + x % 2; // 0 for even, 1 for odd
x /= 2; // x = x / 2; // lose last bit
}
bits[i] = '\0'; // end the string

reverse(bits, i);

return i;
}
/*
gcc rightrot.c -o rightrot
./rightrot
Give a positive integer: 74
x: 1001010
Rotate x to the right by 0 <= n <= 7 bit positions:
n = 0
1001010

./rightrot
Give a positive integer: 74
x: 1001010
Rotate x to the right by 0 <= n <= 7 bit positions:
n = 7
1001010

./rightrot
Give a positive integer: 74
x: 1001010
Rotate x to the right by 0 <= n <= 7 bit positions:
n = 1
0100101 // we keep the initial length of the bit string

./rightrot
Give a positive integer: 74
x: 1001010
Rotate x to the right by 0 <= n <= 7 bit positions:
n = 6 // similar to a left rotate by 1
0010101
*/

---

---

Chapter_2     Exercise_2-7

BACK_TO_TOP

bitcount     Exercise_2-9