What does 'x << ~y' represent in JavaScript?

What does 'x << ~y' represent in JavaScript?

I understand that the bitwise SHIFT operation does this:

x << y AS x * 2y

And a tilde ~ operator does:

~x AS -(x+1)

So, I assume the following:

5 << ~3 AS 5 * 2-4 or 5 * Math.pow(2, -4)

It should result in 0.3125.

But, when I run 5 << ~3 it results in 1342177280.

What is a step-by-step explanation? How and why does this combination of operations result in 1342177280 instead of 0.3125?

(This question is similar to Stack Overflow question What are bitwise operators? about the bitwise SHIFT operator.)


Solution 1:

x << -n is equal to x << (32 - n)
~3 == -4 so
5 << ~3 === 5 << (32 - 4) === 5 << 28 which is 1,342,177,280

to be accurate X << -n is not the same as X << (32 - n) ... in fact it's both simpler and more complicated ... the valid range of a bit shift operator is 0 to 31 ... the RHS in a bit shift operator is first converted to an unsigned 32 bit integer, then masked with 31 (hex 1f) (binary 11111)

                   3 = 00000000000000000000000000000011  
                  ~3 = 11111111111111111111111111111100
       0x1f (the mask) 00000000000000000000000000011111
                       --------------------------------
            ~3 & 0x1f  00000000000000000000000000011100 = 28

when the magnitude is less than 32, it's exactly the same as what I posted above though

Bit operations work with 32 bit integers. Negative bit shifts are meaningless so are wrapped into positive 32 bit integers

How the << operator works

The rhs is converted to an unsigned 32bit integer - like explained here ToUInt32

ToUint32 basically takes a number and returns the number modulo 2^32

Solution 2:

The ~ operator flips the bits of the item, while << is a bitwise left shift. Here is what is happening in binary step-by-step. Note that the most left bit being 1 signified a negative number, this format is twos compliment:

3         // (00000000000000000000000000000011 => +3 in decimal)
// ~ flips the bits
~3        // (11111111111111111111111111111100 => -4 in decimal)
// The number 5 (..00101) shifted by left by -4 (-4 unsigned -> 28)
5         // (00000000000000000000000000000101 => +5 in decimal)
5 << -4   // (01010000000000000000000000000000 => +1342177280 in decimal)

In the last line the bits are shifted and "rotated" to the other side, leading to a large positive number. In fact shifting by a negative number is similar to a bitwise rotation (overflowed bits are rotated to the other side), where shifting by positive numbers do not have such behaviour. The draw back is that the non-rotated bits are disregarded. Essentially meaning that 5 << -4 is the same as doing 5 << (32 - 4), that rather the rotation is actually a large shift.

The reasoning for this is because bit shifts are only a 5 bit unsigned integer. So the binary number in twos compliment-4 (11100) unsigned would be 28.

Solution 3:

Your analysis is correct, except that you should not interpret ~3 (11100) (the bit-complement of 3 (00011)) as -4 , but as an unsigned (that is non-negative) 5-bit integer, namely 28 = 16 + 8 + 4 (11100).

This is explained in the ECMAScript standard (NB in most modern machines, positive and negative integers are represented in memory using two's complement representation):

12.8.3 The Left Shift Operator ( << )

NOTE Performs a bitwise left shift operation on the left operand by the amount specified by the right operand.

12.8.3.1 Runtime Semantics: Evaluation

ShiftExpression : ShiftExpression << AdditiveExpression

  1. Let lref be the result of evaluating ShiftExpression.
  2. Let lval be GetValue(lref).
  3. ReturnIfAbrupt(lval).
  4. Let rref be the result of evaluating AdditiveExpression.
  5. Let rval be GetValue(rref).
  6. ReturnIfAbrupt(rval).
  7. Let lnum be ToInt32(lval).
  8. ReturnIfAbrupt(lnum).
  9. Let rnum be ToUint32(rval).
  10. ReturnIfAbrupt(rnum).
  11. Let shiftCount be the result of masking out all but the least significant 5 bits of rnum, that is, compute rnum & 0x1F.
  12. Return the result of left shifting lnum by shiftCount bits. The result is a signed 32-bit integer.

Solution 4:

~x will reverse the bit representation of your x value (32 bits signed value with two's complement).

x << y is the left shift operator (here left). Your mathematical interpretation is correct :)

You can read more about bitwise operations over here: bitwise operators in Javascript

Solution 5:

5 << ~3 gives the same result as 5 << -4, you are right.

Important thing: shifting x << y really results into x * 2y, but it is not a direct usage, it is just a useful side-effect.
Moreover, if you have a negative y, it doesn't work in the same way.