2-8 K & RC Exercise: What's Wrong?
I do this exercise
write a function rightrot (x, n) that returns the value of an integer x rotated to the right n positions in bits.
but when i try to run it i dont get what i expect.
#include"stdio.h"
int most_signficant_bit(unsigned x){
int bitpos;
for(bitpos = -1; x!=0;++bitpos){
x=x>>1;
}
return bitpos;
}
unsigned rightrot(unsigned x, unsigned n){
int bitpos;
bitpos = most_signficant_bit(x);
x = ((x>>n)|(((~(~0<<n))&x)<<(bitpos-n)));
return x;
}
int main(int argc, char const *argv[]) {
unsigned int c1;
c1 = 0xff1;
printf("bitfield %x "
" after rightrot %x \n",c1, rightrot(c1, 4) );
return 0;
}
I know I (x>>n)
move bitfield "n" to the right 0000 1111 1111
in order to copy "n" less significant bits from that space.
(~(~0<<n))&x)
copy the n least significant bits ( 1111 1111 0001
and 0000 0000 1111
= 0000 0000 0001
) and then move those bits to the desired location <<(bitpos-n)
and after or copy those bits to x
.
But instead I got 0xff
instead 0x1ff
or instead of binary 0000 1111 1111
0001 1111 1111
.
what's wrong?
source to share
I think this expression
x = ((x>>n)|(((~(~0<<n))&x)<<(bitpos-n+1)));
too complicated and unreadable. :)
Also, a function implementation using this expression is invalid, since n may be gretaer than the number of bits in an unsigned int object.
The function can be written as follows, as shown in the demo program
#include <stdio.h>
#include <limits.h>
unsigned int rotate_right( unsigned int x, size_t n )
{
const size_t N = CHAR_BIT * sizeof( int );
n %= N;
return x >> n | x << ( N - n );
}
int main( void )
{
unsigned int x = 0x12345678;
size_t n = CHAR_BIT * sizeof( int );
do
{
printf( "%x\n", x );
x = rotate_right( x, CHAR_BIT / 2 );
} while ( n -= CHAR_BIT / 2 );
}
Program output
12345678 81234567 78123456 67812345 56781234 45678123 34567812 23456781
You can remove the header <limits.h>
and count the number of bits in the type object unsigned int
using the following function
size_t bit_count()
{
size_t n = 0;
for ( unsigned int i = ~0u; i; i >>= 1 ) ++n;
return n;
}
source to share