A couple days ago, I was involved in this thread which concerns bit shifting (kind of) and a solution was found (by someone else). The problem is, something about the solution never really sat right with me. Hopefully someone can clarify this for me.
Code:
The code uses 1 constant and 2 function-like macros defined thus:
/*part of solution by WaltP */
#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)))Ultimately the value of the UINT_BITS macro winds up being 32 (on most modern compilers) and the constant value 32 gets used in the two rotate macros. I have no issue with these, I can see how they work after a little research/experimentation. But having figured this out raised a flag for me concerning the range of acceptable values for "n".
Description of the issue:
Just looking at these makes me think that "n" would have to be limited to a range something like [-31,64) otherwise when you do the shifts, you would loose all your bits in both directions and ultimately get a final result of zero (0).
Logic:
Look, for example, at the rotateleft macro. If you shift more than 31-bits left, all the '1' bits that exist would shift off the end and become '0' bits giving a value of zero. But, depending the distribution of the '1' bits (the original value of "x"), most of them are restored by the bitwise OR operation and the right shift, no issue there. The issue is the fact that 32-64=-32 which on a right shift operation is 32-bits left. Again, bringing me back to the fact that if you shift a 32-bit value more than 31-bits in either direction, you lose all your bits and get a zero (0) result.
Question:
Based on the logic above, it shouldn't be possible to use values for "n" outside of a specific range (which I have postulated to be [-31, 64), but is that even correct?). Yet, I can set up a loop that tests a range of [-96, 160] (full code below) and still get perfectly periodic results. Some of the results don't seem correct, but they're periodic none the less. How??? Is the compiler doing something that I can't see? Or is there something in the code/macros that I'm missing? I can see it working fine using successive single-bit shifts, but not in increments of over +/- 32-bits at a time.
#include <iostream>
#include <iomanip>
#include <ctime>
#include <climits>
/*part of solution by WaltP */
#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 std::cout;
using std::cin;
using std::endl;
using std::setw;
int main() {
unsigned int num = 1, a, b;
for (int i = -96; i <= 160; i++) {
a = rotateleft(num, i);
b = rotateright(num, i);
cout << "num= " << num << ", n=" << setw(3) << i << ", a=" << setw(12) << a << ", b=" << setw(12) << b << endl;
}
cin.get();
}Thanks.
