-1

I was trying to solve the exercise that says

Exercise 2-7. Write the function rightrot(b, n) which rotates the integer b to the right by n bit positions.

and i did code it, here is the code

#include <stdio.h>

int rightrot(int b, int n) {
    char i = 1;

    while (n > 0) {
        if ((b & i) == i) {
            b = b >> 1;
            b = b << 25;
            b = ~b;
            b = b >> 1;
            b = ~b;
            b = b >> 24;
        }
        else
            b = b >> 1;
        n--;
    }

    return b;
}

int main() {
    int i, j, k;

    printf("Enter number: ");
    scanf("%d", &i);
    printf("Enter rotation: ");
    scanf("%d", &j);
    
    k = rightrot(i, j);
    printf("%d\n", k);
    return 0;
}

inputs and output are

Enter number: 153
Enter rotation: 3
-13

153 in binary is 00000000000000000000000010011001, so when it goes in while loop inside while it goes in if for first time (when n is 3), and as you see inside if there are 6 lines of code with bitwise operators to manipulate b and this is what i think how those 6 lines should change b

00000000000000000000000001001100
10011000000000000000000000000000
01100111111111111111111111111111
00110011111111111111111111111111
11001100000000000000000000000000
00000000000000000000000011001100

and then n is 2 and then other 2 while loops should go through else that i wont explain as if's 6 lines code itself doesn't work as i want them too, i know it because i tested them separately.

Also all that is for i am rotating binary as its 8 bit not 32 bit.

Final output should be 51, and i am using arch linux which is 64 bit fully updated, terminal is st by suckless, text editor is vim, i compiled the code using "gcc main.c -o main".

11
  • 1
    Did not look too deeply, but start with working with unsigned types instead of signed. Also you are making many assumptions regarding the types width, so you probably also want fixed-width types (as in uint32_t and friends from stdint.h) Commented Jan 8 at 20:24
  • 1
    Where are the numbers 25 and 24 coming from? Commented Jan 8 at 20:26
  • 1
    I am still learning and i don't want to include stuff in code that i have not covered yet like libraries, data types and etc. Commented Jan 8 at 20:30
  • 1
    I also don't understand how 51 can be the correct output. If we're working with 32 bit integers as your notes suggest, then rightrot(153, 3) should be binary 00100000000000000000000000010011 which is 536870931. Commented Jan 8 at 20:31
  • 3
    Re i j k b n please stop doing that. Use meaningful names except for the very simplest obvious iterations. If you want to make typing easy, search and replace them afterwards. Commented Jan 8 at 20:39

2 Answers 2

1

Final output should be 51

Achievable when unsigned math is used for b.

// int rightrot(int b, int n) {
int rightrot(unsigned b, int n) {

Code like b = b >> 24; does a sign extended shift right when perhaps a logical shift right is desired.

Sign up to request clarification or add additional context in comments.

4 Comments

For those who like short code #include <stdint.h> uint8_t rotate_right8(uint8_t b, unsigned n) { n &= 8-1; return (uint8_t) ((b >> n) | (b << (8-n))); }.
Right shift of negative values isn't always sign-preserving. It's implementation-defined for each signed integer type.
@IanAbbott "It's implementation-defined for each signed integer type." --> Moving forward, with C latest release of C23 in Oct. 2024, only 2's compliment encoding allowed for signed integer types, right shift of negative values is always sign-preserving seems like the way to go, unless one needs to code to prior standards. I suppose the IDB could imply a lot of things to novel implementations, but Darwinian pressure will push for sign preserving.
Right shifting of negative values is still implementation defined in C23 even though 2's complement is assumed. Some old CPU instruction sets do not support arithmetic shift right (at least for wider than int types), so standardizing on ASR for signed types would make the implementation hideously inefficient on such CPUs.
0

The first thing you need to consider is that signed bit shifts to the right just copy the sign bit to the most significant part of the number, so using bit arithmetic with signed numbers will make you run into trouble.

After that, a right rotation of n bits can be considered a bit exchange between the left part and the right part of the number, as shown in the comment to my code. This requires no loop, and is a direct operation.

What about doing it like this:

/* the idea is to consider that the integer can be divided at bit n
 * and the right left and right part exchanged.
 *  {      32 - n      }{   n      }
 *  xxxxxxxxxxxxxxxxxxxxyyyyyyyyyyyy
 *  ||||||||\\\\\\\\\\\\////////////
 *  |||||||\ \\\\\\\\\\XX//////////
 *  ||||||\ \ \\\\\\\\XXXX////////
 *  |||||\ \ \ \\\\\\XXXXXX//////
 *  ||||\ \ \ \ \\\\XXXXXXXX////
 *  |||\ \ \ \ \ \\XXXXXXXXXX//
 *  ||\ \ \ \ \ \ XXXXXXXXXXXX
 *  |\ \ \ \ \ \ X/XXXXXXXXXX\\
 *  \ \ \ \ \ \ X/X/XXXXXXXX\\\\
 *   \ \ \ \ \ X/X/X/XXXXXX\\\\\\
 *    \ \ \ \ X/X/X/X/XXXX\\\\\\\\
 *     \ \ \ X/X/X/X/X/XX\\\\\\\\\\
 *      \ \ X/X/X/X/X/X/\\\\\\\\\\\\
 *       \ X/X/X/X/X/X/\||||||||||||
 *        X/X/X/X/X/X/\|||||||||||||
 *       //X/X/X/X/X/\||||||||||||||
 *      ////X/X/X/X/\|||||||||||||||
 *     //////X/X/X/\||||||||||||||||
 *    ////////X/X/\|||||||||||||||||
 *   //////////X/\||||||||||||||||||
 *  ////////////\|||||||||||||||||||
 *  yyyyyyyyyyyyxxxxxxxxxxxxxxxxxxxx
 */
#define WORD_SIZE_BITS     (32)
uint32_t rotate_right32(uint32_t b, unsigned char n)
{
    n %= WORD_SIZE_BITS; /* rotating will produce the same result after 32 rots */
    return (b >> n) || (b << (WORD_SIZE_BITS - n));
} /* rotate_right32 */

with no loop at all, and just simple bit arithmetic?

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.