Thread: shifting numbers

is there a certain algorithm to do a rotation/shift of an integer x to say n positions right?

rot(x,n)
for example...rot(1234,2)
this would be 3412...

what i tried to do was input the number, and use a while loop to mod the number by 10 and place this result into an int array. so in the end i have the number in an int array backwards so it would be...

Code:

array={'4','3','2','1'};

then i reverse this array so its the correct number, i then perform a a few for loop methods and it would work for say this example but when i try a different x value and also n value, the results are very unexpected.

how can i go about this problem more effectively?
i looked through k&r about shifting >> but im stumped on what goes on or how shifting would work in this case.

cheers!

There are ways to manipulate numbers like that, but not directly in C. Shifting left multiplies the number by 2^shift and shifting right divides by 2^shift. There are other bitwise instructions that will do an arithmetic shift right and left but you will have to use assembly to do it. Also MMX can do exactly what you want to do and it will saturate the answer so that it is not in danger of overflowing.

But shifting is not meant for what you are wanting to do.

Lets say you wanted to multiply by 16

value<<4

would do this.

To divide by 16

value>>4.



I'll explain briefly why this is.

Look at the 8 bit data type here (char or unsigned char).
This will be an unsigned char so we don't have to mess with the sign bit.

(^ represents exponential operation in the following examples)

0 0 0 0 0 0 0 1

This is the number 1 or

0*(2^7)+
0*(2^6)+
0*(2^5)+
0*(2^4)+
0*(2^3)+
0*(2^2)+
0*(2^1)+
1*(2^0)

The bit pattern is on the left.

Now shift left by 1 and we get:

0 0 0 0 0 0 1 0

or

0*(2^7)+
0*(2^6)+
0*(2^5)+
0*(2^4)+
0*(2^3)+
0*(2^2)+
1*(2^1)+
0*(2^0)

which equals 2 -> [1*(2^shift)] =[1*(2^1)]=[1*2]=2.

See what shifting is doing? For shifting right, simply move all of the bits right one slot or binary position. This effectively divides the number by 2^shift, where shift is always positive.


There are some problems with shifting. Overflow conditions are not checked. So if we have an unsigned char or an 8 bit value our min value is 0 and our max is 255 or 0xFF or 11111111. If you shift bits out of the number they are not saved (essentially) and you will lose precision or data - this is true for shifting left and shifting right. There are also bit rotate opcodes that will take the value that was shifted out and put it back in the value at the highest (if it was shifted out the right side) or the lowest (if it was shifted out of the left side) bit position.

In bits, 0 is the lowest and rightmost position. So as you go left the bits increase in value.

I hope this helps. Perhaps I only confused you but mess around with it for a bit and you should get the hang of it.