Rotating bits of any integer in C

Question

Pass a integer 2 to this function and then return a integer which is 4

x = 2;
x = rotateInt('L', x, 1);

(left shift the bits by 1)

Example: 00000010 -> rotate left by 1 -> 00000100

but if I pass this:

x = rotateInt('R', x, 3);

it will return 64, 01000000

Here is the code, can someone correct the error... thanks

int rotateInt(char direction, unsigned int x, int y)
{
    unsigned int mask = 0;
    int num = 0, result = 0;
    int i;

    for (i = 0; i < y; i++)
    {     
        if (direction == 'R')
        {
            if ((x & 1) == 1)     
                x = (x ^ 129);
            else    
                x = x >> 1;
        }
        else if (direction == 'L')
        {
            if ((x & 128) == 1)  
                x = (x ^ 129);   
            else
                x = x << 1;
        }
    }
result = (result ^ x);
return result;   
}

And your question is? You want to know bitwise operations? http://en.wikipedia.org/wiki/Bitwise_operation#Shifts_in_C.2C_C.2B.2B_and_Java — wkl, Oct 13 '10 at 22:47
You really need to learn to indent your code. It makes your code much more readable. Plus you'll work faster and make less mistakes. — Cam, Oct 14 '10 at 00:51

score 6 · Accepted Answer · answered Oct 13 '10 at 23:15

So, I'll assume you know what right and left shifts are. And that you know the difference between arithmetic and logical shifts.

C only has arithmetic shifts. It doesn't do logical shifts, nor does it do rotates. okay I lied, C does logical shifts on unsigned ints.

A rotate does, well, exactly that: it's the same as a logical shift, except when you shift past the end of the number, the digits "wrap around" to the other side. For example

0010 right-rotated is 0001. If you right-rotate again, you get 1000. See, the 1 wrapped around, or rotated, to the other side of the integer.

The left rotate is similar: 0100 left rotate 1000 left rotate 0001 left rotate 0010 etc.

Note that rotates don't keep the sign bit as an arithmetic right-shift would.

So, C only has arithmetic shifts. So you have to implement the "rotate" part manually. So, take a left-rotate. You would want to:

Capture the value of the left-most bit. (is it a 0 or 1?)
Do a left-shift
Set the right-most bit - which is the bit we talked about in step 1 (which needs to be rotated around) to the correct value, based on what we captured from step 1.

You should be able to figure out a similar method for right rotates.

good luck!

Sorry to be contrary; whether a right shift on a signed quantity is arithmetic or logical is up to the individual C compiler — the ISO standard explicitly leaves it undefined. That's just being pedantic though, just stick to unsigned values. — Tommy, Oct 14 '10 at 01:14
@poundifdef That's great for rotating by 1, but how about rotating by *n*? — krb686, Feb 19 '14 at 23:43

Ricardo Sanchez-Saez · Answer 2 · 2015-05-07T16:26:58.097

5

The accepted answer is very nice and straight-forward.

However, I was doing some K&R exercises to refresh my C, and wanted to share this rotate-to-the-right function which may come in handy for people trying to learn bit-wise operations.

unsigned int rightRotateBits(unsigned int inputWord, int numberOfBitsToRotate) {
    int bitWidth = sizeof(inputWord) * 8;
    // Rotating 32 bits on a 32-bit integer is the same as rotating 0 bits;
    //   33 bits -> 1 bit; etc.
    numberOfBitsToRotate = numberOfBitsToRotate % bitWidth;

    unsigned int tempWord = inputWord;

    // Rotate input to the right
    inputWord = inputWord >> numberOfBitsToRotate;

    // Build mask for carried over bits
    tempWord = tempWord << (bitWidth - numberOfBitsToRotate);

    return inputWord | tempWord;
}

For left-rotations just pass values between -1 and -31 to the bitAmount argument.

Do note that this function favors teachability/legibility/simplicity over efficiency/portability/compactness.

edited May 07 '15 at 16:26

answered Feb 17 '13 at 00:53

Ricardo Sanchez-Saez

9,466
8
53
92

1

Also, if you want to visualize your results, you can use this nice function that prints the bit components of a word to the console: http://stackoverflow.com/a/1024414/269753 – Ricardo Sanchez-Saez Feb 17 '13 at 01:03
1

Note, this could be made a little more generic (pass in uint64_t etc), by defining `bit_width = sizeof(inputWord) * 8;` – ideasman42 Sep 25 '14 at 05:44
1

@ideasman42: Thanks, that's a good point. I updated the code. – Ricardo Sanchez-Saez Sep 25 '14 at 09:35

score 1 · Answer 3 · answered Oct 13 '10 at 23:25

1

Since no one told you how to implement this, you can use intrinsics, for visual studio they are _rotl, _rotl64, _rotr, _rotr64.

Oh, but rotation and shifts are 2 different things!

answered Oct 13 '10 at 23:25

Coder

3,695
7
27
42

j3141592653589793238 · Answer 4 · 2021-03-11T10:39:47.723

1

I was reading K&R, too, so this is a very straightforward rotate function for unsigned int:

unsigned int rightrot(unsigned int x, unsigned int n)
{
  return (x >> n) | (x << (sizeof(int) * CHAR_BIT - n)); /* CHAR_BIT is defined in limits.h */
}

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

Where n is the number of bits to rotate.

edited Mar 11 '21 at 10:39

answered Mar 10 '21 at 14:36

j3141592653589793238

1,810
2
16
38

score 0 · Answer 5 · answered Oct 13 '10 at 22:48

0

Have a look at the bitwise shift operators:

http://en.wikipedia.org/wiki/Bitwise_operators#Shifts_in_C.2C_C.2B.2B_and_Java

answered Oct 13 '10 at 22:48

Paul Baumgart

397
1
7

score 0 · Answer 6 · answered Oct 13 '10 at 23:19

It seems like your rotate to the right is RIGHT. 1 fell of the side and returned back again from the left?

Anyway, here are your ingredients:

http://tigcc.ticalc.org/doc/keywords.html#if - for determining if it is 'L' or 'R'

http://tigcc.ticalc.org/doc/keywords.html#for - for counting number of times to shift

and

http://msdn.microsoft.com/en-us/library/f96c63ed(VS.80).aspx - to actually shift it

Go, play with it. It WILL work eventually!

Mateen Ulhaq · Answer 7 · 2011-01-05T00:48:49.297

-1

I recommend using an unsigned int.

#define DIR_LEFT 0
#define DIR_RIGHT 1

unsigned int rotateInt(unsigned int in, int amount, byte dir)
{
    return(dir == DIR_RIGHT ? (in >> amount) | ((in & ((0x01 << amount) - 1)) << (sizeof(unsigned int)*8 - amount)) : (in << amount)  | ((in & ~((sizeof(unsigned int)*8*8 - 1) >> amount)));
}

edited Jan 05 '11 at 00:48

answered Oct 13 '10 at 23:22

Mateen Ulhaq

24,552
19
101
135

This shifts rather than rotates. – Olathe Jan 05 '11 at 00:29
@Olathe This better? There may be optimizations, but that's all I can come up with for now. – Mateen Ulhaq Jan 05 '11 at 00:51
Sorry it took so long to get back to you. Yes, that looks right, but you don't need the `&` masking: shifting will automatically throw away bits that fall off the end. `return dir == DIR_RIGHT ? (in >> amount) | (in << (8*sizeof(unsigned int) - amount)) : (in << amount) | (in >> (8*sizeof(unsigned int) - amount));` – Olathe Apr 19 '11 at 22:19

Rotating bits of any integer in C

7 Answers7

Linked