Understanding bitwise operation in this example

Question

I'm studying some common algorithms implementations in JavaScript, and found this one while looking for quicksort: https://rawgit.com/escherba/algorithms-in-javascript/master/src/quickmiddle-sort.js

It implements an array partition function as well:

function partition(array, left, right) {
        var pivot = array[(left + right) >>> 1];
        while (left <= right) {
            while (array[left] < pivot) { left++; }
            while (array[right] > pivot) { right--; }
            if (left <= right) {
                var temp = array[left];
                array[left++] = array[right];
                array[right--] = temp;
            }
        }
        return left;
}

I wonder what is the math behind the bitwise operation, I'm quite a newbie with them.

It's not really necessary in JS, probably borrowed from Java code where it *is* necessary — harold, Mar 23 '17 at 11:11
If it is there intentionally, then that's the only thing it can be for. — harold, Mar 23 '17 at 12:03

score 2 · Answer 1 · answered Mar 23 '17 at 10:55

2

shift right by 1 is exactly like divide by 2 you can test it by yourself . right a number in a binary and do a right shift and check the result

answered Mar 23 '17 at 10:55

Mero

622
12
24

Ah, I see. So basically we avoid the usage of a division function to be faster? – MattSom Mar 23 '17 at 11:04
1

Yes 4 in binary is 100 shift right you loose the 0 the least significant bit so we end up with 10 binary which is 2 decimal :) it's faster that normal division – Mero Mar 23 '17 at 11:38

Nina Scholz · Accepted Answer · 2017-03-23T11:08:33.840

2

Suppose, you are asking about this part

(left + right) >>> 1

There is an addition of two operands and a zero-fill shift right >>> operator with one bit.

For example you have the value 9 and shift one bit to right.

      9 (base 10): 00000000000000000000000000001001 (base 2)
                   --------------------------------
9 >>> 1 (base 10): 00000000000000000000000000000100 (base 2) = 4 (base 10)

The result is an integer number of 4.

edited Mar 23 '17 at 11:08

answered Mar 23 '17 at 11:03

Nina Scholz

376,160
25
347
392

Yes, just tried in console now, imagined it something like this. Thank you, clear explanation! – MattSom Mar 23 '17 at 11:07

score 1 · Answer 3 · answered Mar 23 '17 at 10:55

1

Bitwise operation is nothing but dividing the sum of left and right values by 2. if left=2 and right=7 output is 9/2 and truncated to 4.

answered Mar 23 '17 at 10:55

rathna

1,055
2
11
23

Understanding bitwise operation in this example

3 Answers3