Undoing shifts without truncating

Question

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".

That's undefined behavior right there. [*"if the value of the right operand is negative or is greater or equal to the number of bits in the promoted left operand, the behavior is undefined"*](http://en.cppreference.com/w/cpp/language/operator_arithmetic#Bitwise_shift_operators). — HolyBlackCat, Apr 13 '18 at 23:56
Look at the assembly code the compiler produced - you'll find your answer in there — YePhIcK, Apr 14 '18 at 00:06
Also note that shifting a *signed* type has different behavior than shifting an *unsigned* type, particularly during right-shifts. — Remy Lebeau, Apr 14 '18 at 00:09
Idc about the sign, only the binary, Also the behavior can be undefined with certain values, but it behaves the same way with any other value greater than 0. — theRobotized, Apr 14 '18 at 02:43

score 1 · Answer 1 · answered Apr 14 '18 at 00:28

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.

Rassoul · Accepted Answer · 2018-08-09T12:04:31.057

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

You're right, anything between 33 to 63 (inclusive) truncates the values. Thanks! — theRobotized, Apr 14 '18 at 02:49
*"Looks like the C compiler works a little strange..."* - [Is right shift undefined behavior if the count is larger than the width of the type?](https://stackoverflow.com/q/18918256/608639), [Why does left shift operation invoke Undefined Behaviour when the left side operand has negative value?](https://stackoverflow.com/q/3784996/608639), [Is left-shifting (<<) a negative integer undefined behavior in C++11?](https://stackoverflow.com/q/19593938/608639), [Undefined behaviour of right shift (a >> b) when b is greater than the number of bits in a?](https://stackoverflow.com/q/29136207), etc. — jww, Apr 14 '18 at 04:39
https://stackoverflow.com/questions/31794709/strange-behavior-of-bit-shift?noredirect=1&lq=1 this answer is awful @jww — Rassoul, Apr 16 '18 at 06:58
That may be, but at least that answer is correct. This answer is misleading at best. — user4581301, Apr 16 '18 at 16:47
Because it implies "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" is what the compiler does when it is something that a compiler COULD do. — user4581301, Apr 17 '18 at 20:48
I you try with cpp code that I provide exactly can see what is happening. — Rassoul, Apr 18 '18 at 23:43
Undefined behavior can manifest in different ways. This answer is merely documenting one of those ways. One cannot use reason to reach this conclusion because it's not the way the language specification says it should work. It's just what happens on some particular hardware with some particular compiler. — Chris Uzdavinis, Aug 09 '18 at 12:16

Undoing shifts without truncating

2 Answers2

Linked