56

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

Community
  • 1
  • 1
choz
  • 17,242
  • 4
  • 53
  • 73
  • 7
    How could a bit shift operation give a fractional result like 0.3125? – edc65 Dec 18 '15 at 07:59
  • @edc65 That's what I assume the answer to be based on basic learning of `XOR` and tilde `~`. I absolutely have no clue how this supposed to work in anyway. – choz Dec 18 '15 at 08:04
  • 9
    after `!--` and `<<~` what is next? I'm supposed to post "What does the `^<<!~` operator do?" – dhein Dec 18 '15 at 12:00
  • 4
    @Zaibis `!~--this[](...[this[$]],_=>..._)` – azz Dec 18 '15 at 13:20
  • @JonnyHenly I think you meant one's complement (`~`). Two's complement is unary minus. – Oliphaunt Dec 18 '15 at 14:05
  • 2
    @Zaibis you could probably just interchange left-shift with right-shift and ask this question again. You might get 20 up-votes. – Jonny Henly Dec 18 '15 at 14:21
  • 1
    @JonnyHenly: Changing left and right shift... but.... that would be .... `>>~`It looks like a guy..... what could he be doing.... I feel like I have the duty to ask SO "What does the Guy operator do?" x'D – dhein Dec 18 '15 at 14:32
  • @Zaibis Not gonna lie, now I kinda wanna know what the Guy operator does. Maybe even continuously edit your question every time there's a new answer and swap out bitwise operators, or add operators from other languages like Groovy's Elvis operator `?:`. That could be fun, until people look at the edit history. – Jonny Henly Dec 18 '15 at 14:59
  • 1
    @JonnyHenly: related: http://stackoverflow.com/q/34359823/2003898 – dhein Dec 18 '15 at 16:22

5 Answers5

58

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

Jaromanda X
  • 53,868
  • 5
  • 73
  • 87
  • 2
    How do you get the reference that `-n` is equal to `(32 - n)`? I am not doubting the fact that this is the answer. But, I am just curious since I couldn't find one. – choz Dec 18 '15 at 08:07
  • 6
    @choz That actually goes all the way back to computer architecture. This is because most computer instructions set used 5 bits for storing the shift amount (*at least for MIPS*). Specially these bits are un-signed binary. – Spencer Wieczorek Dec 18 '15 at 08:14
  • It's not 32-n. It's using just the least siginficant 5 bits, that is `n & 31` (see cited reference about operator <<, 12.8.3.11 subpoint 11). If *n* is negative, then `32+n` == `n & 31` – edc65 Dec 18 '15 at 08:16
  • 2
    @choz ... `-n modulo X` = `X - n` when `abs(n) <= X` ... it's an over simplification on my part – Jaromanda X Dec 18 '15 at 08:16
  • If +3 is (binary) ....0011 then the two's complement if this is ....1101 not ....1100 where the ellipses extend the most significant bit as far left as needed. OOPS!!! this comment is superfluous or incorrect or both, but I can't delete it, sorry – Harry Weston Dec 22 '15 at 22:43
  • ~ is bitwise NOT (or one's complement) ... two's complement is a different animal altogether – Jaromanda X Dec 22 '15 at 23:28
22

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.

Spencer Wieczorek
  • 21,229
  • 7
  • 44
  • 54
  • @JaromandaX Ah your right, it's binary 5 shifted by -4. Give me one second, this explains by it seems I'm off by 1. – Spencer Wieczorek Dec 18 '15 at 06:39
  • Thanks for your answer spencer. I am using online binary converter that `00000111111111111111111111111111` is `0x07FFFFFF` which resulted as `134217727`. Am I doing something wrong here? – choz Dec 18 '15 at 06:39
  • @choz That was a mess-up on my part, I read the last expression in a wrong order and got a very close number by chance. I've updated my answer. – Spencer Wieczorek Dec 18 '15 at 06:42
  • 1
    maybe add a disclaimer or FYI that javascript converts the number from a 64bit double precision floating point to a 32bit integer, does the bit manipulations, then converts back. Good answer though, now that it's fixed. – Jonny Henly Dec 18 '15 at 06:47
  • @SpencerWieczorek I am wondering since `5 << -4` is right shifting the binary of `5` for 4 times, correct? Doesn't it mean it should be like an equal of `5 >> 4` then? I am kinda confused in shifting this bs.. :( – choz Dec 18 '15 at 07:33
  • a rotation does NOT disregard bits ... but we are dealing with a SHIFT, not a ROTATION – Jaromanda X Dec 18 '15 at 07:42
  • @Choz should it? No, it's not defined that way. I could be nice if a minus sign could revert the shift direction, but in fact it does not. – edc65 Dec 18 '15 at 08:21
9

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.
hkBst
  • 2,818
  • 10
  • 29
7

~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

Mr_Pouet
  • 4,061
  • 8
  • 36
  • 47
6

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.

Yeldar Kurmangaliyev
  • 33,467
  • 12
  • 59
  • 101
  • How is that supposed to work with negative value btw? I am sorry I don't really understand about bit representation of anything. – choz Dec 18 '15 at 06:10
  • 1
    *, if you have a negative y, it doesn't work in the same way* so you don't actually have an answer to the actual question – Jaromanda X Dec 18 '15 at 06:30