I'm reading through the underscore.js code. I found this:
var mid = (low + high) >> 1;
What does >> 1 do? Why is it useful?
Asked
Active
Viewed 471 times
3
Randomblue
- 112,777
- 145
- 353
- 547
-
The author probably thought that `>> 1` would be more efficient than `/ 2`. In most languages, that would be incorrect; for example, a C compiler would probably generate the same code for both. I don't know whether the same applies to JavaScript. – Keith Thompson Sep 17 '11 at 05: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 Sep 17 '11 at 05:40
4 Answers
7
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.
µBio
- 10,668
- 6
- 38
- 56
-
Strictly speaking it is equivalent to *integer division* by 2, rounding towards negative infinity. (I'm not the downvoter.) – Stuart Cook Sep 17 '11 at 05:37
-
2@BioBuckyBall: `5 / 2 === 2.5`, but `5 >> 1 === 2`. In JavaScript, dividing two integers yields a floating-point result. `>>` does integer division where `/` wouldn't. – icktoofay Sep 17 '11 at 05:40
2
>> 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 compute 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.
Chandra Patni
- 17,347
- 10
- 55
- 65
-
-
https://developer.mozilla.org/en/JavaScript/Reference/Operators/Bitwise_Operators#Bitwise_shift_operators is a good resource. – Chandra Patni Sep 17 '11 at 05:52
-
You can read about the overflow bug here http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html. It's a bug in JDK for many years. The same applies to bitwise operations in JavaScript because they have the same semantic. – Chandra Patni Sep 26 '11 at 05:18
1
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.
mu is too short
- 426,620
- 70
- 833
- 800
-
-
@Randomblue: Yes, the shift should be faster because everything should be done in integers and it avoids the `Math.floor` function call. I don't know if the difference matters much with a decent JavaScript implementation. – mu is too short Sep 17 '11 at 05:45
0
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.
