Kenny Kenny - 5 months ago 8
Javascript Question

How to make sense of `Zero-fill right shift` (`>>>`) in `d3.bisector` source code?

I could find resources on the operation of

Zero-fill right shift
, meaning how
15 >>> 2
return
3
.

I kind of understand how we get 3 from 15 by using this operation, but I have no idea the meaning and purpose of this operation.

Here I want to understand the logic of
d3.bisector
, but
d3.bisector
source code
has the following line using
>>>
, I have absolutely no idea what it is for or intend to get:

var mid = lo + hi >>> 1;


According to the purpose of this function
d3.bisector
, variable
mid
seems to define the middle index of array
a
. If this is the case, then
lo + hi >>> 1
should be used to find the middle index. Based on this assumption I tried the following codes:

var a = 0 + 5 >>> 1;
console.log(a); // 2
var a = 0 + 6 >>> 1;
console.log(a); // 3
var a = 1 + 6 >>> 1;
console.log(a); //3


These examples seem to confirm the assumption. So, here are my questions


  1. is
    var mid = lo + hi >>> 1;
    to find middle index of an array?

  2. if it is, then why and how such operation could achieve it? at this stage, this code is like a black box, I know its purpose or what the outcome is for, but I understand no why, nor I can use
    >>>
    in any other cases.



Thanks

Answer

The bitwise operators >> and >>> are often used to perform fast integer division by 2.

For a positive number a, a >>> n equals Math.trunc(a / Math.pow(2, n))

The ordinary division operator is quite slow compared to bitwise shifting, which explains why it is often used whenever the divisor is a multiple of 2.

Beware: all bitwise operators convert their operands to 32 bit two-complements, thus reducing the effective range of a. Using >>> instead of >> guarantees that the result is always a positive number and returns the expected result for a in [0, 2^32-1]. This is desirable when working with arrays whose indices are always within this range.

Comments