logoalt Hacker News

adrian_byesterday at 11:01 PM0 repliesview on HN

It works fine when the value is negative.

However, there is a quirk of the hardware of most CPUs that has been inherited by the C language and by other languages.

There are multiple ways of defining integer division when the dividend is not a multiple of the divisor, depending on the rounding rule used for the quotient.

The 2 most frequently used definitions is to have a positive remainder, which corresponds to rounding the quotient by using the floor function, and to have a remainder of the same sign with the quotient, which corresponds to rounding the quotient by truncation.

In most CPUs, the hardware is designed such that for signed integers the division instruction uses the second definition, while the right shift uses the first definition.

This means that when the dividend is a multiple of the divisor, division and right shift are the same, but otherwise the quotient may differ by one unit due to different rounding rules.

Because of this, compilers will not replace automatically divisions with right shifts, because there are operands where the result is different.

Nevertheless, the programmer can always replace a division by a power of two with a right shift. In all the programs that I have ever seen, either the rounding rule for the quotient does not matter or the desired definition for the division is the one with positive remainder, i.e. the definition implemented by right shift.

In those cases when the rounding rule matters, the worrisome case is when you must use division not when you can use right shift, so you must correct the result to correspond to rounding by floor, instead of the rounding by truncation provided by the hardware. For this, you must not use the "/" operator of the C language, but one of the "div" functions from "stdlib.h", or you may use "/" but divide the absolute values of the operands, after which you compute the correct signed results.