Help with JavaME Function

Question

Could anyone explain to me how this MIDP Java function works? I'm particularly curious about the operators being used.

public static final int smoothDivide(int numerator, int denominator) {
    return (int) ((numerator << 16) / denominator + 32768L) >> 16;
}

Thanks a lot

Answer 1

This is a division algorithm that rounds to the closest integer. It is equivalent to

Math.round((float) numerator / denominator)

for a large range of the integers, but cleaverly implemented without floating point operations.

The operators << and >> are bitwise shift left and shift right operators.

---

Here is the intuition for how it works

First note that << 16 and >> 16 are equivalent to * 65536 and / 65536 respectively. So what the algorithm computes is the folowing:

            / numerator * 65536           \
result  =  ( ------------------  +  32768  )  /  65536
            \   denominator               /

That is, it scales up the numerator, divides it, adds half of the scale, and then scales it down again.

It is similar to the expression (int) ((numerator + 0.5) / denominator) which is a more common way to do "rounded" division (but it relies on floating point arithmetic).