Opposite functions?

[cwarn23]

Hi - it's me again. I have the following code but don't exactly know what it means or how to make the opposite code. The code I currently have is

#define rotateleft(x,n) ((x<<n) | (x>>(32-n)))   
#define rotateright(x,n) ((x>>n) | (x<<(32-n)))

Then can be used like the following

a = rotateleft(123,456)
b = rotateright(123,456)

But as for the question, I have the values a and b stored. But now I need to reverse the formula so I get parameter 1 back (123). So say in the above code I have value a, I put it through a function then it should be 123 just like b. So how exactly do I do that because none of this makes any sense. Please help... Thanks.

[JasonHippy]

The macro functions rotateleft and rotateright perform binary shift operations, shifting the binary value of x by n places in the appropriate direction using the << and >> binary shift operators.

So using some smaller, more sensible values for x and n (e.g. x=4 n=2);
if we now did something like:

x= rotateleft(x,n);

Using my example values for x and n, we know that x==4.
In binary 4 is represented as:
100

if we shift the binary value of x (4), n places to the left (n==2 remember), we get this..
10000
Which is the binary representation of the number 16.

So the value of x would become 16.

To get the original value of x back, you need to call rotateright passing x and n, which will output the value that results from shifting x (16) to the right by n (2) places.
So we'd call this:

x = rotateright(x,n);

This time the value of x is 16. n is still 2.
16 in binary is:
10000

shifting 2 places to the right gives you the binary value:
100

Which is the number 4 (the original value of x!)

Just in case you're not 100% clear, have a butchers at this simple example:

#include <iostream>
#include <string>

#define rotateleft(x,n) ((x<<n) | (x>>(32-n)))   
#define rotateright(x,n) ((x>>n) | (x<<(32-n)))

using std::cout;
using std::endl;

void output(const std::string &message, const int &x, const int &n)
{
	cout << message << endl << "x=" << x << " n=" << n << endl << endl;
}

int main()
{
	// set initial values for x and n
	int x = 4, n = 2;

	// output values to console
	output("Initial values:", x, n);

	// perform left shift and output values
	x = rotateleft(x, n);
	output("After rotate left:", x, n);
	// NOTE: we've modified the value of x  in the above call to rotateleft.
	// if we wanted to perform the left shift and store the result in a separate variable 
	// while keeping the original value of x we'd use something like:
	// int num1 = rotateleft(x,n)


	// perform right shift and output
	x = rotateright(x, n);
	output("After rotate right:", x, n);
	// NOTE: Again, we've modified the value of x.
	// if you used the commented out line from the previous comment block
	// e.g. int num1 = rotateleft;
	// To get the value of num1 back to the original value of x you could use:
	// num1 = rotateright(num1, n); // <<- modifying num1
	// OR
	// int num2 = rotateright(num1, n); // <<- storing result in a separate variable.

	return  0;
}

I hope that clears things up for you.
Cheers for now,
Jas.

ps. in the context of your original post:

int a = rotateleft(123,456);
int b = rotateright(123,456);

To get a and b back to 123 you could do this:

a = rotateright(a, 456);
b = rotateleft(b,456);

OR

int c = rotateright(a, 456);
int d = rotateleft(b, 456);

But you should also note that there is some code in the macro functions to limit the shifted numbers to 32 bits.
e.g. in rotateleft:
(x << n) shifts x by n places to the left, but this value is then OR'ed with the value of x shifted to the right by 32-n to give the final result. So I don't think it will work well with particularly large numbers for x or n.

456 is certainly far too big for n. n should be somewhere between 1 and 31 (shifting x by 32 places in either direction will give you x!)

[Fbody]

...shifting x by 32 places in either direction will give you x!

I don't think this is correct. I'll admit, I'm still figuring out bitwise operators myself, but last I knew they don't wrap around. (Still looking for reference where I read it.)

The way I understand it is if you shift a '1'-bit off the left end, it does not come back around to the right end as a '1'. It's simply replaced with a '0'. The same is true for a right shift.

EDIT: Found the reference...

As bits are shifted off one end, 0's are brought in the other end. (In the case of a signed, negative integer, a right shift will cause a 1 to be brought in so that the sign bit is preserved.) Remember, a shift is not a rotate. (emphasis added by Fbody) That is, the bits shifted off one end do not come back around to the other. The bits shifted off are lost.

[Fbody]

Nuts, ran out of edit time.

This code should demonstrate that fact:

#include <iostream>
#include <iomanip>

using std::cout;
using std::cin;
using std::setw;

int main() {
	int num = 1;

	for (int i = 0; i < (8*sizeof(int)+3); i++) {
		cout << "after shift#" << setw(3) << i << ", num = " << num << "\n";
		num = num << 1;
	}
	cin.get();
}

It starts with a '1' in the far right position and shifts if left until it shifts it off the left end. It then performs 3 more for demonstration purposes.

Coincidentally, this also gives you the base-10 value of each position in a signed 32-bit binary number...

[JasonHippy]

But if you take another look at the code that is being used in the rotateleft and rotateright functions in the OP, it's not just a straight shift, there actually is some rotation going on. (or at least something equally as cunning!)

There are two operations in the rotateleft and rotateright functions. The first operation is a straightforward shift of x by n places in the relevant direction, but the result of the first operation is OR'ed with the result of the second operation. The second operation shifts x by 32-n places in the opposite direction.

Try running my code and vary the values a little and you'll see.
Perhaps keep x as 4 (or something easily predictable) and try varying the value of n.
In fact if you set n to 32, you'll find that the result of shifting x by 32 places in either direction (using rotateleft or rotateright) results in the value of x staying the same.

[EDIT] In fact, because it actually does rotate, try n as 64, 96, 128 or any other multiple of 32 and the result will be x.

Cheers for now,
Jas.

[JasonHippy]

456 is certainly far too big for n. n should be somewhere between 1 and 31 (shifting x by 32 places in either direction will give you x!)

This is the statement you were referring to, just to clarify things here I should really have written:

456 is certainly far too big for n. n should be somewhere between 1 and 31 (shifting x by 32 places using rotateleft or rotateright will give you x!)

[edit] But as there is rotation going on, I guess that entire statement is actually pretty redundant!

[Dave Sinkula]

Hi - it's me again. I have the following code but don't exactly know what it means or how to make the opposite code. The code I currently have is

#define rotateleft(x,n) ((x<<n) | (x>>(32-n)))   
#define rotateright(x,n) ((x>>n) | (x<<(32-n)))

Then can be used like the following

a = rotateleft(123,456)
b = rotateright(123,456)

But as for the question, I have the values a and b stored. But now I need to reverse the formula so I get parameter 1 back (123). So say in the above code I have value a, I put it through a function then it should be 123 just like b. So how exactly do I do that because none of this makes any sense. Please help... Thanks.

Use an unsigned value to be rotated.

#include <iostream>
#include <climits>

#define UINT_BITS ( CHAR_BIT * sizeof(unsigned int) )
#define rotateleft(x,n)  ( (x << n) | ( x >> (UINT_BITS - n) ) )   
#define rotateright(x,n) ( (x >> n) | ( x << (UINT_BITS - n) ) )

int main() 
{
   unsigned int value = 123;
   for ( int i = 0; i < UINT_BITS + 3; i++ )
   {
      unsigned int a = rotateleft(value, i);
      unsigned int b = rotateright(a, i);
      std::cout << "value = " << value 
                << ", shift = " << i 
                << ", a = " << a 
                << ", b = " << b << "\n";
   }
   return 0;
}

/* my output
value = 123, shift = 0, a = 123, b = 123
value = 123, shift = 1, a = 246, b = 123
value = 123, shift = 2, a = 492, b = 123
value = 123, shift = 3, a = 984, b = 123
value = 123, shift = 4, a = 1968, b = 123
value = 123, shift = 5, a = 3936, b = 123
value = 123, shift = 6, a = 7872, b = 123
value = 123, shift = 7, a = 15744, b = 123
value = 123, shift = 8, a = 31488, b = 123
value = 123, shift = 9, a = 62976, b = 123
value = 123, shift = 10, a = 125952, b = 123
value = 123, shift = 11, a = 251904, b = 123
value = 123, shift = 12, a = 503808, b = 123
value = 123, shift = 13, a = 1007616, b = 123
value = 123, shift = 14, a = 2015232, b = 123
value = 123, shift = 15, a = 4030464, b = 123
value = 123, shift = 16, a = 8060928, b = 123
value = 123, shift = 17, a = 16121856, b = 123
value = 123, shift = 18, a = 32243712, b = 123
value = 123, shift = 19, a = 64487424, b = 123
value = 123, shift = 20, a = 128974848, b = 123
value = 123, shift = 21, a = 257949696, b = 123
value = 123, shift = 22, a = 515899392, b = 123
value = 123, shift = 23, a = 1031798784, b = 123
value = 123, shift = 24, a = 2063597568, b = 123
value = 123, shift = 25, a = 4127195136, b = 123
value = 123, shift = 26, a = 3959422977, b = 123
value = 123, shift = 27, a = 3623878659, b = 123
value = 123, shift = 28, a = 2952790023, b = 123
value = 123, shift = 29, a = 1610612751, b = 123
value = 123, shift = 30, a = 3221225502, b = 123
value = 123, shift = 31, a = 2147483709, b = 123
value = 123, shift = 32, a = 123, b = 123
value = 123, shift = 33, a = 246, b = 123
value = 123, shift = 34, a = 492, b = 123
*/

[Fbody]

But if you take another look at the code that is being used in the rotateleft and rotateright functions in the OP, it's not just a straight shift, there actually is some rotation going on. (or at least something equally as cunning!)

There are two operations in the rotateleft and rotateright functions. The first operation is a straightforward shift of x by n places in the relevant direction, but the result of the first operation is OR'ed with the result of the second operation. The second operation shifts x by 32-n places in the opposite direction.

Try running my code and vary the values a little and you'll see.
Perhaps keep x as 4 (or something easily predictable) and try varying the value of n.
In fact if you set n to 32, you'll find that the result of shifting x by 32 places in either direction (using rotateleft or rotateright) results in the value of x staying the same.

[EDIT] In fact, because it actually does rotate, try n as 64, 96, 128 or any other multiple of 32 and the result will be x.

Cheers for now,
Jas.

I laid the shifts out in a spreadsheet, I see how it works now. Thanks for the info...

@Dave:
Thx for using a variation of my code :). That helped me see it a little better too.

@OP:
Sorry if you feel hijacked, that was not my intent... :(

[JasonHippy]

Ooops, good point Dave. Nicely done!

I should've been using unsigned ints in my code too. I completely forgot to take the sign into consideration. The rotate functions in the OP's code won't work with negative numbers! {kicking self!}

I toyed with the idea of doing something like your UINT_BITS definition to get the actual system size, but admittedly I would've ended up doing it for int... Tut! I should've thought it through! However, I decided to run with the hard-coded 32 that the OP posted in their code.

Anyways, hats off to the Davester!

Jas.

[dusktreader]

One more note on the rotate function:

Because the bitshift operators can take negative numers as the rvalue aruments, there is not really a need for two macros. You can simply use a negative index to rotate in the opposite direction:

#include <iostream>
#include <climits>

#define UINT_BITS ( CHAR_BIT * sizeof(unsigned int) )
#define rotateleft(x,n)  ( (x << n) | ( x >> (UINT_BITS - n) ) )
#define rotateright(x,n) ( (x >> n) | ( x << (UINT_BITS - n) ) )

using namespace std;

int main()
{
   unsigned int value = 123;
   unsigned int a = rotateleft(value, 7);
   cout << "after rotate left: " << a << endl;
   a = rotateright(value, -7);
   cout << "after negative rotate right: " << a << endl;
   return 0;
}

output"

after rotate left: 15744
after negative rotate right: 15744

Of course, there is no harm in having both declared, in fact, it may improve readability to have both. I just felt compelled to but in and add the extra info.