theRobotized
Reputation: 43
Undoing shifts without truncating
I'm a bit baffled by this. Shouldn't the values truncate after the shift?
Does anyone know why this happens?
long a, b, c, n;
//assign any value to a, set b and c to 0x000...0
n = 128; //any number works;
b = a << n;
c = b >> n;
a == (b >> n); // True
a == c; //True;
Postscript
I've always understood that if you shift a buffer in any direction, the values that "fall" outside the buffer size get truncated, and that they're essentially lost unless you get them from the original buffer. Thats been true for every platform I've ever worked with in assembly, and I thought that'd extend to the higher level languages.
However, in c++ i can shift a buffer (int or long) by more bits than it can hold, and if I then shift in the opposite direction, the result is equal to the original "buffer".
Upvotes: 1
Views: 492
Answers (2)
Rassoul
Reputation: 194
Looks like the C compiler works a little strange, but its absolutely reasonable
if the number of shifts be greater than the operand length (in bits) so compiler divide it to operand length and use reminder as number for shifts
// A << N
L = length of A
if L < N
then N = A % L;
Therefore you can set such a number for number of shifts that makes it undoing disable !!!
N = 63 might be your answer, It doesn't work (your conditions are FALSE) for any value on A (even A=1) (except A=0)
PUT [61 < N < 64] , A = 3 MAKES IMPOSSIBLE UNDO
[60 < N < 64] AND , A = 7
...
Try this code to understand what happen
#include <cstdlib>
#include <cstdio>
using namespace std;
void DisplayBinary(unsigned int n, int l)
{
for (int i = l - 1 ; i >= 0; i--)
{
printf("%x", (n & (1 << i)) >> i);
}
}
int main(int argc, char** argv)
{
// x = 340
unsigned int x = 0x154;
for (int numberOfShifts = 0; numberOfShifts < 100; numberOfShifts++) {
printf("numberOfShifts = %d\tresult = ", numberOfShifts);
DisplayBinary(x << numberOfShifts, 32);
printf("\n");
}
return 0;
}
Look Output:
numberOfShifts = 0 result = 00000000000000000000000101010100
numberOfShifts = 1 result = 00000000000000000000001010101000
numberOfShifts = 2 result = 00000000000000000000010101010000
numberOfShifts = 3 result = 00000000000000000000101010100000
numberOfShifts = 4 result = 00000000000000000001010101000000
numberOfShifts = 5 result = 00000000000000000010101010000000
numberOfShifts = 6 result = 00000000000000000101010100000000
numberOfShifts = 7 result = 00000000000000001010101000000000
numberOfShifts = 8 result = 00000000000000010101010000000000
numberOfShifts = 9 result = 00000000000000101010100000000000
numberOfShifts = 10 result = 00000000000001010101000000000000
numberOfShifts = 11 result = 00000000000010101010000000000000
numberOfShifts = 12 result = 00000000000101010100000000000000
numberOfShifts = 13 result = 00000000001010101000000000000000
numberOfShifts = 14 result = 00000000010101010000000000000000
numberOfShifts = 15 result = 00000000101010100000000000000000
numberOfShifts = 16 result = 00000001010101000000000000000000
numberOfShifts = 17 result = 00000010101010000000000000000000
numberOfShifts = 18 result = 00000101010100000000000000000000
numberOfShifts = 19 result = 00001010101000000000000000000000
numberOfShifts = 20 result = 00010101010000000000000000000000
numberOfShifts = 21 result = 00101010100000000000000000000000
numberOfShifts = 22 result = 01010101000000000000000000000000
numberOfShifts = 23 result = 10101010000000000000000000000000
numberOfShifts = 24 result = 01010100000000000000000000000000
numberOfShifts = 25 result = 10101000000000000000000000000000
numberOfShifts = 26 result = 01010000000000000000000000000000
numberOfShifts = 27 result = 10100000000000000000000000000000
numberOfShifts = 28 result = 01000000000000000000000000000000
numberOfShifts = 29 result = 10000000000000000000000000000000
numberOfShifts = 30 result = 00000000000000000000000000000000
numberOfShifts = 31 result = 00000000000000000000000000000000
numberOfShifts = 32 result = 00000000000000000000000101010100 <<<===
numberOfShifts = 33 result = 00000000000000000000001010101000
numberOfShifts = 34 result = 00000000000000000000010101010000
numberOfShifts = 35 result = 00000000000000000000101010100000
numberOfShifts = 36 result = 00000000000000000001010101000000
numberOfShifts = 37 result = 00000000000000000010101010000000
numberOfShifts = 38 result = 00000000000000000101010100000000
numberOfShifts = 39 result = 00000000000000001010101000000000
numberOfShifts = 40 result = 00000000000000010101010000000000
numberOfShifts = 41 result = 00000000000000101010100000000000
numberOfShifts = 42 result = 00000000000001010101000000000000
numberOfShifts = 43 result = 00000000000010101010000000000000
numberOfShifts = 44 result = 00000000000101010100000000000000
numberOfShifts = 45 result = 00000000001010101000000000000000
numberOfShifts = 46 result = 00000000010101010000000000000000
numberOfShifts = 47 result = 00000000101010100000000000000000
numberOfShifts = 48 result = 00000001010101000000000000000000
numberOfShifts = 49 result = 00000010101010000000000000000000
numberOfShifts = 50 result = 00000101010100000000000000000000
numberOfShifts = 51 result = 00001010101000000000000000000000
numberOfShifts = 52 result = 00010101010000000000000000000000
numberOfShifts = 53 result = 00101010100000000000000000000000
numberOfShifts = 54 result = 01010101000000000000000000000000
numberOfShifts = 55 result = 10101010000000000000000000000000
numberOfShifts = 56 result = 01010100000000000000000000000000
numberOfShifts = 57 result = 10101000000000000000000000000000
numberOfShifts = 58 result = 01010000000000000000000000000000
numberOfShifts = 59 result = 10100000000000000000000000000000
numberOfShifts = 60 result = 01000000000000000000000000000000
numberOfShifts = 61 result = 10000000000000000000000000000000
numberOfShifts = 62 result = 00000000000000000000000000000000
numberOfShifts = 63 result = 00000000000000000000000000000000
numberOfShifts = 64 result = 00000000000000000000000101010100 <<<===
numberOfShifts = 65 result = 00000000000000000000001010101000
numberOfShifts = 66 result = 00000000000000000000010101010000
numberOfShifts = 67 result = 00000000000000000000101010100000
numberOfShifts = 68 result = 00000000000000000001010101000000
numberOfShifts = 69 result = 00000000000000000010101010000000
numberOfShifts = 70 result = 00000000000000000101010100000000
numberOfShifts = 71 result = 00000000000000001010101000000000
numberOfShifts = 72 result = 00000000000000010101010000000000
numberOfShifts = 73 result = 00000000000000101010100000000000
numberOfShifts = 74 result = 00000000000001010101000000000000
numberOfShifts = 75 result = 00000000000010101010000000000000
numberOfShifts = 76 result = 00000000000101010100000000000000
numberOfShifts = 77 result = 00000000001010101000000000000000
numberOfShifts = 78 result = 00000000010101010000000000000000
numberOfShifts = 79 result = 00000000101010100000000000000000
numberOfShifts = 80 result = 00000001010101000000000000000000
numberOfShifts = 81 result = 00000010101010000000000000000000
numberOfShifts = 82 result = 00000101010100000000000000000000
numberOfShifts = 83 result = 00001010101000000000000000000000
numberOfShifts = 84 result = 00010101010000000000000000000000
numberOfShifts = 85 result = 00101010100000000000000000000000
numberOfShifts = 86 result = 01010101000000000000000000000000
numberOfShifts = 87 result = 10101010000000000000000000000000
numberOfShifts = 88 result = 01010100000000000000000000000000
numberOfShifts = 89 result = 10101000000000000000000000000000
numberOfShifts = 90 result = 01010000000000000000000000000000
numberOfShifts = 91 result = 10100000000000000000000000000000
numberOfShifts = 92 result = 01000000000000000000000000000000
numberOfShifts = 93 result = 10000000000000000000000000000000
numberOfShifts = 94 result = 00000000000000000000000000000000
numberOfShifts = 95 result = 00000000000000000000000000000000
numberOfShifts = 96 result = 00000000000000000000000101010100 <<<===
numberOfShifts = 97 result = 00000000000000000000001010101000
numberOfShifts = 98 result = 00000000000000000000010101010000
numberOfShifts = 99 result = 00000000000000000000101010100000
Upvotes: 0
Stephen Newell
Reputation: 7863
Check out Godbolt with a simplified example:
long left_shift(unsigned long a) {
return (a << 128);
}
long right_shift(unsigned long a) {
return ((a << 128) >> 128);
}
We get assembly that looks like this (gcc-7.3.0, -O2):
left_shift(unsigned long):
xor eax, eax
ret
right_shift(unsigned long):
xor eax, eax
ret
As HolyBlackCat said, this is undefined behavior. gcc implements it by treating the result of the shifts as 0, even in the right_shift function where we could logically deduce the result. clang does nothing in the left_shift function, which is also perfectly cromulent.
Upvotes: 1