Kenny Kenny - 1 year ago 59
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

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
, but
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
, variable
seems to define the middle index of array
. 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.


Answer Source

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download