Hacker's Delight

9-1. Preliminaries

This chapter and the following one give a number of tricks and algorithms involving “computer division” of integers. In mathematical formulas we use the expression x/y to denote ordinary rational division, x ÷ y to denote signed computer division of integers (truncating toward 0), and to denote unsigned computer division of integers. Within C code, x/y of course denotes computer division, unsigned if either operand is unsigned, and signed if both operands are signed.

Division is a complex process, and the algorithms involving it are often not very elegant. It is even a matter of judgment as to just how signed integer division ...