CODEWITHSUNDEEP
bit-manipulationbitwise-operatorsbit-shift
Matthew Schell
Matthew Schell

Reputation: 679

Why is the result of a bitwise shift unrecoverable if there is a mathematical equivalent of the same operation?

Take for example the number 91. That number in binary is 1011011. If you shift that number to the right by 5 bits, you would get 2 (10 in binary). According to a google search, bit shifting to the left or right by a certain amount of bits is the same as multiplying or dividing the number by 2 to the power of the number of bits to be shifted, respectively. so to get from 91 to 2 by bit shifting, the equation would look like this: 91 / 2^5, which is also 91 / 32. Now, of course if you did that in your calculator, there would be some decimal values, which aren't included when bit shifting. The resulting 2 is actually 2.84357. I'm sure you know that if you do a certain operation on a number and then you do the inverse, the result would be what you had in the first place. So does decimal precision have something to do with this?

Upvotes: 0

Views: 654

Answers (2)

phuclv
phuclv

Reputation: 41972

You can only recover the result of an operation if it has a 1-1 mapping between the inputs and outputs, i.e. it has an inverse function. But not all mathematical functions have an inverse function

For example if f(x) = x >> n with >> is the shift operator then it'll be equivalent to

f(x) = ⌊x/2n⌋

with ⌊ ⌋ being the floor function. Since there are many inputs that lead to the same output, the relationship isn't 1-1 and there can't be an inverse function for it. This function works the same for both signed and unsigned right shift:

91 >> 5 == floor(91.0/32.0) == 2
-91 >> 5 == floor(-91.0/32.0) == -3

Similarly for an unsigned left shift function g(x) = x << n then the equivalent is

g(x) = (x * 2n) mod 2N

with N being the size in bits of x, because integer math in hardware, C and many other languages always reduce modulo 2N due to the limit of register size and the use of two's complement. And it's clear that the modulo function also isn't invertible/recoverable. The signed left shift is almost the same with some small modifications

Upvotes: 1

slebetman
slebetman

Reputation: 114014

There is a mathematical equivalent of shifting to the right... and the mathematical operation is UNRECOVERABLE.

You seem to think that shifting to the right is:

bit shifting to the left or right by a certain amount of bits is the same as multiplying or dividing the number by 2

This is what you will hear people casually say, but it is only half right. As it it is not the same but only similar.

The correct statement is:

shifting a base-2 number one digit to the right is THE SAME as dividing by two in the integer domain

If you have an integer calculator, if you did 91/32 you will get 2. You will not get ANY decimal point because we are operating in the integer domain.

For real numbers, the equivalent operation is:

FLOOR(91/32)

Which is also unrecoverable because it also results in 2.

The lesson here is be careful when listening to what people CASUALLY say. Casual speech is often imprecise and assumes the listener is familiar with the subject. You need to dig deeper what the statement is actually trying to say.

As for why it is unrecoverable? Division of integers give two results: the quotient (which is the main result) and the remainder. When we divide 91 by 32 we are doing this:

       2
    _____
 32 ) 91
      64
      __
      27

So we get the result of 2 and a remainder of 27. The reason you can't get 91 by multiplying 2*32 is because we threw away the remainder.

You can get the result back if you saved the remainder. However, calculating the remainder is not a matter of simple shifts. Here's an example of how to make it reversable in C:

int test () {
    int a = 91;
    int b = 32;
    int result;
    int remainder;

    result    = a / b; // result will be 2
    remainder = a % b; // remainder will be 27

    return (result * b) + remainder; // returns 91
}

Upvotes: 1

Related Questions