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.

3
Contributors
5
Replies
7
Views
8 Years
Discussion Span
Last Post by Fbody

>If you shift more than 31-bits left
The behavior is undefined.

>The issue is the fact that 32-64=-32 which on a right shift operation is 32-bits left.
No, that's undefined too. If you shift in either direction by a negative value or by a value greater than or equal to the number of bits in the target, the behavior is undefined.

>Some of the results don't seem correct, but they're periodic none the less. How???
It's generally best not to try explaining undefined behavior. Your results could be wildly different on another compiler, so you don't gain as much as you would by learning that what you did is undefined. :)

Edited by Narue: n/a

>>If you shift more than 31-bits left
>The behavior is undefined.
So is this an invalid statement then:

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.

Or, is this a more situational statement that it seems to be?

The conversation contained in the linked thread occurred after I read it, that may be part of why I'm confused.

>>The issue is the fact that 32-64=-32 which on a right shift operation is 32-bits left.
>No, that's undefined too. If you shift in either direction by a negative value or by a value greater than or equal to the number of bits in the target, the behavior is undefined.
It sounds like you are telling me this post is a junk post then...

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:

Sorry if I seem argumentative, I'm just trying to figure this stuff out. It doesn't help that I get the same results in VC++ and in Dev-C++(w/ MinGW).

Edited by Fbody: n/a

>So is this an invalid statement then:
>Remember, a shift is not a rotate.

The statement is valid. It refers to the value being shifted, not the shift amount.

>It sounds like you are telling me this post is a junk post then...
Absolutely. dusktreader was probably relying on how a single implementation interprets the undefined behavior rather than the standard language definition. Here's what the standard says (emphasis mine):

shift-expression:

The operands shall be of integral or enumeration type and integral promotions are performed. The type of the result is
that of the promoted left operand. The behavior is undefined if the right operand is negative, or greater than or equal to
the length in bits of the promoted left operand.

The value of E1 << E2 is E1 (interpreted as a bit pattern) left-shifted E2 bit positions; vacated bits are zero-filled. If E1
has an unsigned type, the value of the result is E1 multiplied by the quantity 2 raised to the power E2, reduced modulo
ULLONG_MAX+1 if E1 has type unsigned long long int, ULONG_MAX+1 if E1 has type unsigned long int, UINT_-
MAX+1 otherwise. [ Note: the constants ULLONG_MAX, ULONG_MAX, and UINT_MAX are defined in the header <climits>.
—end note ]

The value of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a
nonnegative value, the value of the result is the integral part of the quotient of E1 divided by the quantity 2 raised to the
power E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

``````/*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)))``````

Be more careful quoting. I never posted in that thread nor did I write that code.

Be more careful quoting. I never posted in that thread nor did I write that code.

My apologies, it was actually Dave Sinkula.... not sure why I put your name there...

@Narue:
I see, I guess I'll just have to accept that there is a wierdness there and move on. I'll have to keep those issues in mind if I ever come across that again. It seems that, at least some, compilers implement the undefined behavior in a way consistent with what my workaround would be.

Was my logic at least reasonably valid though? Can you understand the reason why.

Edited by Fbody: n/a