r/Cplusplus • u/Any_Wait_7309 • 7h ago
Question Signed left shift causes overflow, and therefore undefined behavior
I was solving a question on Leetcode: Reversing Bits
The goal is simple, that we have been given an positive even number and we are supposed to reverse it's binary representation.
If we notice, it says "even" number - that implies the LSB is set to 0 and when we reverse the binary representation the 0 would move to MSB
I thought, it would be great to reverse it with just "bit manipulation" which is as folllows:
```cpp
n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1);
n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2);
n = ((n >> 4) & 0x0F0F0F0F) | ((n & 0x0F0F0F0F) << 4);
n = ((n >> 8) & 0x00FF00FF) | ((n & 0x00FF00FF) << 8);
n = (n >> 16) | (n << 16);```
Instead of reversing the number, we swap 2 bits, then 4 bits, then 8 bits and then 16 bits. The resultant sequence is exactly the reverse of the original binary representation.
Now, the incoming number is a signed int meaning it has range from:
```cpp
-2,147,483,648 to 2,147,483,647
-2^(31) to 2^(31) - 1
10000000 00000000 00000000 00000000 to 01111111 11111111 11111111 11111111
```
My perspective is that: Just shifting things around isn't really going to make it overflow, since it's a signed int - all that's gonna happen is the result will be interpreted in a wrong manner.
Example: Take the INT_MIN and << 1, what happens? Mathematically it should produce a smaller number that falls outside of the range of INT_MIN, but in computers the 1 is just discarded and we are left with a value of 0
Example: Take the INT_MAX and << 1, what happens? It turns into a negative number, because we are using signed int, does it over flow? not really.
I had initially used int for this and it produced wrong values because the reversed final value would be read as int, so i started casting int to uint and worked with it. Which internally should only work with positive numbers and correct binary representation and it worked.
Where it got weird was - I asked chatGPT to see if my logic is sound and it said that without the cast the number would just overflow in a signed int. From what I understand that's not really possible, because we are just shifting things around and even if we set the MSB to 1 ( for largest possible positive number ) it's just gonna get interpreted as a negative number.
Verdict: It won't overflow
But then it says that the representation is not an issue, it's c++ standard and due to that it may produce an undefined value - basically, in our first example it won't allow wrapping because mathematically it doesn't make sense. But it works!
At this point, i am 100% sure that it's wrong, it's just not possible to overflow the signed int through this algorithm, it makes sense to use uint because it would maintain proper representation internally and then finally when we cast it back to int - we would get the correct representation in signed format. It's only possible to overflow if we were working with decimal values.
I would say that even if the input was an odd number, still there wouldn't be any overflow just wrong representation!
TLDR: Don't sideline me for using AI, i just used it to summarize and verify my understanding. I think that it's wrong according to the current standards and undefined behavior or overflowing isn't really any issue. Just that the results will be wrong because it would be interpreted wrong.
The same would apply to even if the incoming number was negative or odd or completely positive (uint)
Thoughts?! What am I missing like would it really overflow?