Binary Rotation

[gonzilla]

Hello,

I'm new to bitwise operation, so sorry if I speak incorrectly.

I need to write a function that takes two ints. One is the number to work on, the other is the number of bits to shift the number over. It also has to replace the bits on the right end with the bits that are shifted off the left end, thus rotating the bits. So something like this will shift the bits:

unsigned int shift(unsigned int x, int y)
{
x <<= y

return (x)
}

But, how do I get the bits to reappear on the other side?

If x = 129 (10000001) and y = 2
then
x <<= y == 6 (00000110)

I don't want the code, just a starting point. I use the MS C++ compiler if that helps (I know some compilers handle bits differently).

Thanks in advance for your help.

-Tyler

 

[Loon]

Not very elegant but...

Instead of shifting by y straight off, shift by 1 - y times. Then as you shift each MSB off the end of the int, make the LSB equal to this...

Bare in mind what size the data type you are shifting is, i.e. is it 8-bit byte, 16 bit word, 32 bit.. etc..

Also different compliers have different endian values, big-endian or little-endian, which determines which is the most significant byte to start with.

so something like:

unsigned char msb = (x << 1) & 2^(sizeof(x)*8);

might do the job.. haven't tried it though!

Cheers
Loon

 

[Nosferatu]

Try instead using the functions from <stdlib.h>:
_rotl and _rotr
Both take an unsigned value to be shifted and the numbers of bits to be rotated...
So, rotr(1001011,2) would yeld something like
1110010... [red]Nosferatu[/red]
We are what we eat...
There's no such thing as free meal...
once stated: methane@personal.ro

 

[gonzilla]

Thanks for the responses.

The library function won't do since I would like to know how it is done, not necessarily done for me.

BTW - For some reason (old IE version I guess) I can't properly display TGML on my computer at work, so I can't read the idea that Loon gave. I'll have to wait until I get home.

Any other ideas?

Thanks again.

-Tyler

 

[Zyrenthian]

int x = some_value;

int bits_to_top = 0;

bits_to_top = ~(1<<(bits_to_shift_by +1) & some_value);
bits_to_top = bits_to_top<<(31-bits_to_shift_by);

some_value = some_value>>bits_to_shift_by | bits_to_top;


I think this is the correct logic but I have not tested it.

If it is off, change the 31 to 32 but that makes no sence to me because if the shift is 0 then your shifting the number away.

Matt

 

[adyrotaru]

Now, that you really wanted to know how rotation is done, i'll give you a reference:

http://www.penguin.cz/~literakl/intel/intel.html

which is the main page with Intel x86 Instruction Set

and specifically

http://www.penguin.cz/~literakl/intel/r.html#ROL

which is the exact instruction that accomplishes the rotation to left: ROL.

Have fun!