So I recently came across a scenario where I needed to set a single bit in a 64 bit value. Simple:
uint64t result = 1ull << n;
I expected to rely on result being zero when n is out of range (n >= 64). Technically, this is how an arithmetic and logical shift would behave, according to their definitions as per wikipedia and technically intels x86 manual. Practically this is not how they behave on our hardware at all and I think this is interesting to share.
So I wrote this little test to see what happens when you shift out of range:
#include <iostream>
#include <bitset>
#include <stdint.h>
int main()
{
uint64t bitpattern = 0xF0FF0FF00FF0FF0Full;
// shift overflow
for (uint64t shift = 0;shift <= 128ull;shift++)
{
uint64t shiftresult = bitpattern << shift;
std::bitset<64> bitsetresult(shiftresult);
std::cout << bitsetresult << " for a shift of " << shift << std::endl;
}
return 0;
}
And right at the threshold to 64 the output does something funny:
1111000011111111000011111111000000001111111100001111111100001111 for a shift of 0
1110000111111110000111111110000000011111111000011111111000011110 for a shift of 1
1100001111111100001111111100000000111111110000111111110000111100 for a shift of 2
...
1110000000000000000000000000000000000000000000000000000000000000 for a shift of 61
1100000000000000000000000000000000000000000000000000000000000000 for a shift of 62
1000000000000000000000000000000000000000000000000000000000000000 for a shift of 63
1111000011111111000011111111000000001111111100001111111100001111 for a shift of 64
1110000111111110000111111110000000011111111000011111111000011110 for a shift of 65
1100001111111100001111111100000000111111110000111111110000111100 for a shift of 66
...
1100000000000000000000000000000000000000000000000000000000000000 for a shift of 126
1000000000000000000000000000000000000000000000000000000000000000 for a shift of 127
1111000011111111000011111111000000001111111100001111111100001111 for a shift of 128
It behaves as if
result = input << n % 64; !!So, I did a little bit of digging and found that GCC uses the SAL instruction (arithmetic shift) to implement this. From what I gathered, when working with unsigned types the logical shift should be used but this is of no relevance as SAL and SHL are apparently equivalent on x86_64 machines (which I can confirm).
What is far more interesting is that these instructions seem to just ignore out of range shift operands. I guess CPU's are wired to siply just care about the bottom 6 significant digits (or 5 in the case of the 32 bit wide instruction equivalent, as this also happens with 32 bit values at n = 32.) Notably, it does not happen at n = 16 for 16 bit values, they still use the 32 bit range.
MSVC and clang both do insert an SHL (logical left shift) instead of a SAL but the result is the same.
Now, there is one thing that really tripped me when debugging this initially:
uint64t result = 0;
uint64t n = 63;
result = 1ull << (n + 1); // result is 1
result = 1ull << 64; // result is 0 !?
So, apparently, when GCC was able to just precompute the expression it would come up with the wrong result. This might be a compiler bug? This also happens on clang, I didn't test it on MSVC.
Just something I thought was interesting sharing. Took me quite a while to figure out what was happening and where my bug came from. It really stumped me for a day
https://redd.it/1ow3g9y
@r_cpp
