Threshold bit in C

Question

Problem: Exercise 2-8 in the C programming language: "Write a function rightrot (x, n) that returns the value of an integer x rotated to the right by n positions."

I did it the way I know. That is the question I have. Take a specific number for this exercise, say 29, and turn it one position to the right.
11101, and it will become 11110 or 30. Let's say, for the sake of argument, that the system we are working on has an unsigned integer size of 32 bits. Let it be said further that we have the number 29 stored in an unsigned integer variable. In memory, the number will have 27 zeros in front. Therefore, when we rotate 29 right, using one of several algorithms, my wire is placed below, we get the number 2147483662. This is obviously not the desired result.

unsigned int rightrot(unsigned x, int n) { return (x >> n) | (x << (sizeof(x) * CHAR_BIT) - n); } 

This is technically correct, but I thought the 27 zeros that are in front of 11101 were minor. I also tried several other solutions:

 int wordsize(void) { // compute the wordsize on a given machine... unsigned x = ~0; int b; for(b = 0; x; b++) x &= x-1; return x; } unsigned int rightrot(unsigned x, int n) { unsigned rbit; while(n --) { rbit = x >> 1; x |= (rbit << wordsize() - 1); } return x; 

This last and final decision is one in which I thought I had it, I will explain where he failed as soon as I get to the end. I am sure you will see my mistake ...

 int bitcount(unsigned x) { int b; for(b = 0; x; b++) x &= x-1; return b; } unsigned int rightrot(unsigned x, int n) { unsigned rbit; int shift = bitcount(x); while(n--) { rbit = x & 1; x >>= 1; x |= (rbit << shift); } } 

This solution gives the expected answer 30, which I was looking for, but if you use a number for x, for example, say 31 (11111), then there are problems, in particular, the result is 47, using one for n. I had not thought about this before, but if a number like 8 (1000) is used, then chaos. There is only one bit in 8 bits, so the shift will certainly be wrong. My theory at this stage is that the first two solutions are correct (mostly), and I just missed something ...

Answer 1

Bitwise rotation is always necessary within an integer of a given width. In this case, since you are assuming a 32-bit integer, 2147483662 ( 0b10000000000000000000000000001110 ) is really the correct answer; you are not doing anything wrong!

0b11110 will not be considered the correct result with any reasonable definition, since continuing to the right using the same definition will never return the original input. (Suppose another right rotation gives 0b1111 and continues to spin, which will have no effect.)

Answer 2

In my opinion, the spirit of the section of the book that immediately precedes this exercise would make the reader deal with this problem without knowing anything about the size (in bits) of integers or any other type. The examples in the section do not require such information; I do not believe that exercises should be.

Regardless of my belief, the book has not yet introduced the sizeof operator in Section 2.9, so the only way to determine the type size is to read the bit “manually”.

But we do not need to worry about all this. We can rotate bits in n steps, regardless of how many bits are in the data type, rotating one bit at a time.

Using only those parts of the language that the book covered before section 2.9, here is my implementation (with integer parameters returning an integer, as indicated by the exercise): Loop n times, x → 1 for each iteration; if the old least significant bit of x is 1, set the new high bit.

 int rightrot(int x, int n) { int lowbit; while (n-- > 0) { lowbit = x & 1; /* save low bit */ x = (x >> 1) & (~0u >> 1); /* shift right by one, and clear the high bit (in case of sign extension) */ if (lowbit) x = x | ~(~0u >> 1); /* set the high bit if the low bit was set */ } return x; } 

Answer 3

You can find the location of the first “1” in a 32-bit value using binary search. Then, pay attention to the bit at the LSB location, shift it to the right by the required number of places, and put the LSB bit at the first "1" position.

Answer 4

 int bitcount(unsigned x) { int b; for(b = 0; x; b++) x &= x-1; return b; } unsigned rightrot(unsigned x,int n) { int b = bitcount(x); unsigned a = (x&~(~0<<n))<<(b-n+1); x>> = n; x| = a; }