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...

 

[Don Porges]

#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.

 

[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 ;-)

 

[Thad Smith]

#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.

 

[Tomás Ó hÉilidhe]

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

Yeah but what's a rotate function?

 

[Sjouke Burry]

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]

Yeah but what's a rotate function?

A circular bit-shift.

 

[Tomás Ó hÉilidhe]

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.

 

[cr88192]

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?...

 

[mrdarrett]

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.

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/class/cs306/books/artofasm/Chapter_6/CH06-3.html

Enjoy,

Michael

 

[mrdarrett]

<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?...

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

Michael

 

[cr88192]

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

yeah, an example:
mining entropy out of a small-order non-deterministic source (such as the
timing of incomming system events).

one can have a variable, that they keep rotating, and xoring something (for
example, the current time) into this whenever a system event arrives.
this leaves a small chaotic value, with a much higher apparent randomness
than simply the times of various events (user interaction, ...).

we can then pull values off of this, and use them to feed randomness into
the state of a much bigger PRNG.

this kind of thing has a few uses as well...


for example, I mostly use random numbers for the generation of 'probably
unique numbers (GUIDs, non-clashing-names, ...).

 

[Stephen Sprunk]

#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

 

[Syren Baran]

#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.