RotateLeft, what does it do?

[Tomás Ó hÉilidhe]

#define ROTATE_LEFT(a,n)(((a)<<(n)) | (((a) & 0xffffffff)>>(32-(n))))

I've been trying to figure out what this macro is supposed to do. Here it
is written in a more reader-friendly manner:

long unsigned RotateLeft(long unsigned const value,unsigned const places)
{
long unsigned x = (value & 0xffffffff); /* Get lower 32 bits only */

x >>= (32-places); /* Shift it to the right */

long unsigned const x = value << places; /* Shift to the left */

return x | y;
}

If I put 11111111111111111111111111111111 into it for "a" and have 19 for
"n", I get:

x == 11111111111111111111111111111111

(x >>= 32-19) == (x >>= 13) == 00000000000001111111111111111111

y == value << 19 == 11111111111111111110000000000000

I then OR the two of them:

x = 00000000000001111111111111111111
y = 11111111111111111110000000000000

And I'm left with all one's again.

Haven't been able to fathom what it's supposed to do yet...

--
Tomás Ó hÉilidhe

[Don Porges]

"Tomás Ó hÉilidhe" <to*@lavabit.comwrote in message news:Xn**************************@194.125.133.14.. .

>
#define ROTATE_LEFT(a,n)(((a)<<(n)) | (((a) & 0xffffffff)>>(32-(n))))

I've been trying to figure out what this macro is supposed to do. Here it is written in a more reader-friendly manner:

long unsigned RotateLeft(long unsigned const value,unsigned const places)
{
long unsigned x = (value & 0xffffffff); /* Get lower 32 bits only */

x >>= (32-places); /* Shift it to the right */
long unsigned const x = value << places; /* Shift to the left */

return x | y;
}

If I put 11111111111111111111111111111111 into it for "a" and have 19 for "n", I get:

You've chosen a bad example. Try "0000000000....1" as the initial value and
it will be clearer.

x == 11111111111111111111111111111111

(x >>= 32-19) == (x >>= 13) == 00000000000001111111111111111111

y == value << 19 == 11111111111111111110000000000000

You got the wrong value for "y", also.

I then OR the two of them:

x = 00000000000001111111111111111111
y = 11111111111111111110000000000000

And I'm left with all one's again.

Haven't been able to fathom what it's supposed to do yet...

--
Toms hilidhe

[Coos Haak]

Op Sat, 05 Jan 2008 21:01:32 GMT schreef Tomás Ó hÉilidhe:

#define ROTATE_LEFT(a,n)(((a)<<(n)) | (((a) & 0xffffffff)>>(32-(n))))

I've been trying to figure out what this macro is supposed to do. Here it
is written in a more reader-friendly manner:

long unsigned RotateLeft(long unsigned const value,unsigned const places)
{
long unsigned x = (value & 0xffffffff); /* Get lower 32 bits only */

x >>= (32-places); /* Shift it to the right */

long unsigned const x = value << places; /* Shift to the left */

return x | y;
}

If I put 11111111111111111111111111111111 into it for "a" and have 19 for
"n", I get:

x == 11111111111111111111111111111111

(x >>= 32-19) == (x >>= 13) == 00000000000001111111111111111111

y == value << 19 == 11111111111111111110000000000000

y == value << 19 == 11111111111110000000000000000000

>
I then OR the two of them:

x = 00000000000001111111111111111111
y = 11111111111111111110000000000000

y = 11111111111110000000000000000000

>
And I'm left with all one's again.

Of course, x was the number with all bits set.
Choose one with some zero's in it and all will be revealed ;-)
--
Coos

[Thad Smith]

Tomas wrote:

>
#define ROTATE_LEFT(a,n)(((a)<<(n)) | (((a) & 0xffffffff)>>(32-(n))))

I've been trying to figure out what this macro is supposed to do. Here
it is written in a more reader-friendly manner:

long unsigned RotateLeft(long unsigned const value,unsigned const places)
{
long unsigned x = (value & 0xffffffff); /* Get lower 32 bits only */

x >>= (32-places); /* Shift it to the right */
long unsigned const x = value << places; /* Shift to the left */

return x | y;
}

Your code will fail to compile. Please cut and paste successfully compiled
code instead of retyping.

Even without the compiler error, the functionality is different for
implementations that have more than 32 bits in an unsigned long.

The macro/function implements a rotate operation which is a single
instruction on many machines.

--
Thad

[Tomás Ó hÉilidhe]

Thad Smith <Th*******@acm.orgwrote in comp.lang.c:

The macro/function implements a rotate operation which is a single
instruction on many machines.

Yeah but what's a rotate function?

--
Tomás Ó hÉilidhe

[Sjouke Burry]

"Tomï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï ¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ " wrote:

Thad Smith <Th*******@acm.orgwrote in comp.lang.c:

>The macro/function implements a rotate operation which is a single
instruction on many machines.

Yeah but what's a rotate function?

Shift the bits, and the bit falling off at the end,
re-enters at the other site, so all bits move as if in a circle.
ROR for rotating to the right, ROL to rotate to the left.

[andreyvul]

On Jan 5, 10:11 pm, "Tomás Ó hÉilidhe" <[e-mail]:

Thad Smith <[e-mail] in comp.lang.c:

The macro/function implements a rotate operation which is a single
instruction on many machines.

Yeah but what's a rotate function?

A circular bit-shift.

[Tomás Ó hÉilidhe]

andreyvul <an********@gmail.comwrote in comp.lang.c:

On Jan 5, 10:11 pm, "Tomás Ó hÉilidhe" <[e-mail]:

>Thad Smith <[e-mail] in comp.lang.c:

The macro/function implements a rotate operation which is a single
instruction on many machines.

Yeah but what's a rotate function?

A circular bit-shift.

Are the bits that fall off the end supposed to come back on the other
side? For example, if we took:

0000000010101010
^^^^^^^^
76543210

and "circular bit-shifted" it to the right by four, would it become the
following:

1010000000001010
^^^^ ^^^^
3210 7654

I've never come across a need for such a shift. I saw the macro in
algorithmic code that someone sent to me, and instead of trying to figure
out the macro I just rewrote the code... and found no need for any kind
of circular shift.

--
Tomás Ó hÉilidhe

[cr88192]

"Toms hilidhe" <to*@lavabit.comwrote in message
news:Xn**************************@194.125.133.14.. .

andreyvul <an********@gmail.comwrote in comp.lang.c:

>On Jan 5, 10:11 pm, "Toms hilidhe" <[e-mail]:

>>Thad Smith <[e-mail] in comp.lang.c:

The macro/function implements a rotate operation which is a single
instruction on many machines.

Yeah but what's a rotate function?

A circular bit-shift.

<snip>

>
I've never come across a need for such a shift. I saw the macro in
algorithmic code that someone sent to me, and instead of trying to figure
out the macro I just rewrote the code... and found no need for any kind of
circular shift.

uses for things are subtle, but when they are needed, they are needed.

otherwise, if there were no need for something like this, why would so many
people know what it is, and, more so, why would you have encountered such a
macro in the first place?...
one could then also ask: of what possible use is max, abs, or sqrt, or
tan?...

do we conclude that trigonometry functions are useless, for example, because
we write apps that primarily do integer arithmetic and work with objects and
strings?...

--
Toms hilidhe

[mrdarrett]

On Jan 6, 4:34 pm, "Tomás Ó hÉilidhe" <[e-mail]:

andreyvul <[e-mail] in comp.lang.c:

On Jan 5, 10:11 pm, "Tomás Ó hÉilidhe" <[e-mail]:

Thad Smith <[e-mail] in comp.lang.c:

The macro/function implements a rotate operation which is a single
instruction on many machines.

Yeah but what's a rotate function?

A circular bit-shift.

Are the bits that fall off the end supposed to come back on the other
side? For example, if we took:

0000000010101010
^^^^^^^^
76543210

and "circular bit-shifted" it to the right by four, would it become the
following:

1010000000001010
^^^^ ^^^^
3210 7654

I've never come across a need for such a shift. I saw the macro in
algorithmic code that someone sent to me, and instead of trying to figure
out the macro I just rewrote the code... and found no need for any kind
of circular shift.

--
Tomás Ó hÉilidhe

Bit shifts are useful in cryptography and data compression, among
other uses.

http://en.wikipedia.org/wiki/SHA_hash_functions

http://www.arl.wustl.edu/~lockwood/c..._6/CH06-3.html

Enjoy,

Michael

[mrdarrett]

On Jan 6, 8:11 pm, "cr88192" <[e-mail]:

"Toms hilidhe" <[e-mail] in message

news:Xn**************************@194.125.133.14.. .

andreyvul <[e-mail] in comp.lang.c:

On Jan 5, 10:11 pm, "Toms hilidhe" <[e-mail]:
Thad Smith <[e-mail] in comp.lang.c:

The macro/function implements a rotate operation which is a single
instruction on many machines.

>Yeah but what's a rotate function?
A circular bit-shift.

<snip>

I've never come across a need for such a shift. I saw the macro in
algorithmic code that someone sent to me, and instead of trying to figure
out the macro I just rewrote the code... and found no need for any kind of
circular shift.

uses for things are subtle, but when they are needed, they are needed.

otherwise, if there were no need for something like this, why would so many
people know what it is, and, more so, why would you have encountered such a
macro in the first place?...

one could then also ask: of what possible use is max, abs, or sqrt, or
tan?...

do we conclude that trigonometry functions are useless, for example, because
we write apps that primarily do integer arithmetic and work with objects and
strings?...

--
Toms hilidhe

No kidding... the average Joe has no need for the error function, for
Bessel functions, or for the incomplete gamma function...

Michael

[Stephen Sprunk]

"Toms hilidhe" <to*@lavabit.comwrote in message
news:Xn**************************@194.125.133.14.. .

>
#define ROTATE_LEFT(a,n)(((a)<<(n)) | (((a) & 0xffffffff)>>(32-(n))))

I've been trying to figure out what this macro is supposed to do.

"Rotate" is a cyclic shift, where the bits that go off the end are stuffed
back on the other end. Some CPUs have built-in instructions to do rotates
(e.g. x86's ROL/ROR); others need the macro above. Smarter compilers will
turn the above macro into a single instruction if the target CPU has one.

Rotate left by 2:
10010001 -01000110 -00011001 -01100100 -10010001

Note that rotating left X is equal to rotating right BITS-X. Rotating by
more than BITS either is undefined, evaluates as rotating by X%BITS, or
results in 0 depending on the implementation.

y == value << 19 == 11111111111111111110000000000000

You only shifted it left 13 places, not 19.

I then OR the two of them:

x = 00000000000001111111111111111111
y = 11111111111111111110000000000000

y = 11111111111110000000000000000000

And I'm left with all one's again.

Haven't been able to fathom what it's supposed to do yet...

If you rotate an all-ones value, it won't do anything useful. Try it again
with a more interesting bit pattern.

S

--
Stephen Sprunk "God does not play dice." --Albert Einstein
CCIE #3723 "God is an inveterate gambler, and He throws the
K5SSS dice at every possible opportunity." --Stephen Hawking

[Syren Baran]

"Tomï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï ¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ " schrieb:

>
#define ROTATE_LEFT(a,n)(((a)<<(n)) | (((a) & 0xffffffff)>>(32-(n))))

The question might be considered stupid, but wtf.
RotateLeft, usually known as ROL by processors, shifts all bits in a
variable to the left by n. Any bits shifted beyond the "edge" are
inserted on the other side.
I´ll just assume you want to know "why" and "what for".
As to the "why".
For a processor this is a very simple instructon.
As to the "what for".
Analog to your question i might ask "* , what does it do?". Its a simple
function/operator/commnand/instruction/whatsoever_depends_who_you_ask
which can be pretty usefull at times.
I cant recall using it myself, but i remember using shiftleft and right
often enough back in the days DIV was "forbidden" (well, not
forbidden, but performances dictated using MUL + SHR).
But being such a mean guy i wont answer the question "why would i use
it?". I´ll just ask an abstract question:
"Why would you consider writing a=b*c when you could just well write
"for(i=0,a=0;i<b;i++) a+=c""?
Same results, eh?
But well, might as well learn python and not care about efficiency.