Replace Math.floor() into >>> shift operation in JS for optimization
Published: 2023-04-09 08:27:08

Thanks to Tony B's comment on my Leetcode blogging post, I got to look up again on shift operators in Javascript. 
*Love the community's feedback. One more reason to post my progress and studies :P*

![Tony B's comment and feedback](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bi51d7423vjlkoy360jz.png)


```js
mid = Math.floor((lower + upper) / 2);
```
Above can be changed to below.

```js
mid = lower + ((upper - lower) >>> 1);

// or this

mid = (lower + upper) >>> 1;

```
*Quick Note*
Regarding the basic mathematical equation of getting the middle number of two different numbers, `lower + (upper-lower)/2` is as same as `(lower + upper)/2`.


### Learning points
- Math.floor() is not very optimized operation.
- [What is & How to use >>> shift operation](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Unsigned_right_shift)
- Exception: >>> operation does not work for `BigInt`. 

*Disclaimer*: I got some help of ChatGPT to get these explanations. 

### How come is this replaceable / possible?

- The >>> (zero-fill right shift) operator in JS is often used as an optimization technique to perform integer division by a power of 2, effectively achieving the same result as dividing by 2 (or any power of 2).

- The reason this works is because bitwise operators in JS operate on **32-bit signed integers, which are represented in two's complement format**. In two's complement, the leftmost bit (the sign bit) is used to represent the sign of the number, with 0 indicating positive and 1 indicating negative. The remaining 31 bits represent the magnitude of the number.

- When you use the >>> operator to **shift the bits of a positive integer to the right by 1 position**, you are effectively **dividing the number by 2** and **rounding down to the nearest integer**. This is because shifting the bits to the right by 1 position is equivalent to dividing the number by 2, and the >>> operator fills the vacated leftmost bit with 0, which ensures that the result is **always a non-negative integer**.

- Using >>> 1 is effectively equivalent to dividing by 2 and rounding down, providing an optimized way to achieve integer division by a power of 2.

```js
let num = 10;
let result = num >>> 1;
console.log(result); // Output: 5

/**
The binary representation of 10 is 
00000000000000000000000000001010. 

Shifting the bits to the right by 1 position using >>> gives 
00000000000000000000000000000101

which is equivalent to the decimal value 5.
**/
```

### Why is Math.floor() operation inefficient compared to bit shift operation? 

- **Floating-point arithmetic**: Math.floor() operates on floating-point numbers, which are represented with decimal points and can have fractional parts. Performing floating-point arithmetic can be computationally more expensive compared to integer arithmetic, as it involves additional steps for handling the fractional parts and rounding.

- **Type coercion**: Math.floor() returns a floating-point number, which may require type coercion to convert it to an integer if an integer result is desired. Type coercion can introduce additional overhead in terms of performance and code readability.

- **Potential loss of precision**: Floating-point numbers in JavaScript have limited precision, which means that very large or very small numbers may lose precision due to the limitations of the floating-point representation. This can result in subtle rounding errors or inaccuracies when working with large numbers.

### Why is >>> operation more efficient?

- The >>> operator in JavaScript performs bitwise operations on 32-bit signed integers, which do not involve floating-point arithmetic and can operate more efficiently at the binary level. 
- The >>> operator fills the vacated leftmost bit with 0, ensuring that the result is always a non-negative integer, which can provide better accuracy and consistency for integer division.


Also, chatGPT added, saying
```
However, it's worth noting that modern JavaScript
engines are highly optimized and the performance 
difference between these two methods may not be 
significant in most practical scenarios. 

It's always recommended to profile and benchmark 
your code to determine the actual performance 
impact in your specific use case.

```
 
P.S.
I remember learning such bit operations and concepts during college CS classes. I took 'Operating Systems' class in undergrad - a great class taught by Professor [Jason Waterman](https://www.vassar.edu/faculty/jawaterman). In the beginning of the class, it was very tough, especially debugging the assembly code... But at the end, it really helped me to understand why programming languages are made like this and how computers actually work under the hood when I type and compile the programming.

I think I was probably one of the only few junior/senior students who were not majoring/minoring in CS back then. After I got into VR, I realized I wanted to study more computers. Thus, I later wanted to minor in CS, but it was quite late to take all the required classes. While I feel more and more confident with my programming skills and experiences as I work, I kind of wished I minor/majored in CS, especially whenever I see all those JD saying 'computer science degree' :'( But oh well, gotta just keep going !!