I'm reading through the underscore.js code. I found this:

var mid = (low + high) >> 1;

What does >> 1 do? Why is it useful?

I'm reading through the underscore.js code. I found this:

var mid = (low + high) >> 1;

What does >> 1 do? Why is it useful?

• javascript
• underscore.js

Share Improve this question Follow asked Sep 17, 2011 at 5:32 RandomblueRandomblue 116k150150 gold badges362362 silver badges557557 bronze badges 2

• The author probably thought that >> 1 would be more efficient than / 2. In most languages, that would be incorrect; for example, a C piler would probably generate the same code for both. I don't know whether the same applies to JavaScript. – Keith Thompson Commented Sep 17, 2011 at 5:35
• @Keith: JavaScript would switch to floating point values for the division so using the shift keeps everything in integer land without having to use Math.floor. – mu is too short Commented Sep 17, 2011 at 5:40

Add a ment  | 

4 Answers 4

Sorted by: Reset to default 8

It shifts the bits in the left side to the right by one bit. It is equivalent to dividing by 2.

In 'Ye olden times' this was faster than simply dividing, though I doubt it would make a whole lot of difference in underscore's case.

>> is the sign propagating right shift operator. It shifts the bit pattern of (low + high) right by 1 place and the leftmost bit is copied to the left place. It's effectively same as Math.floor((low + high) / 2).

I would be remiss if I didn't point out a subtle bug with using (low + high) >> 1 to pute the mid point of an array in binary search which can cause overflow. (low + high) >>> 1 where >>> is zero filling right shift operator, is devoid of overflow bug.

That's a bitwise right shift. For integers, it is equivalent to dividing by two; for JavaScript numbers, it is roughly the same as Math.floor((low + high) / 2) but avoids the floating point altogether.

It's probably there to keep the value an integer. Dividing by 2 here may convert the result to a floating point number in some cases, for example, if (low + high) is odd.

The two operations are not exactly equivalent:

> (5+2)/2
3.5
> (5+2)>>1
3

For this particular use, though, there are better idioms for finding the midpoint of two numbers.