Iterative division apparatus, system and method employing left most one's detection and left most one's detection with exclusive OR

摘要

An iterative technique for division having a divisor of N bits and a numerator of more than N bits. Each iteration includes initial detection of the position of a left most one bit (1011, 1035) of N most significant bits of the numerator. If this L is not zero, then the numerator is left shifted by L places (1016, 1039), the next L quotient bits are set to zero and the number of completed iterations is incremented by L. An alternative embodiment detects bit position of the left most one of an exclusive OR of the N most significant bits of the numerator and the divisor. Next the divisor is subtracted from the N most significant bits of the numerator. If the difference is greater than or equal to zero, then the next quotient bit is "1" and the difference is substituted for the N most significant bits of the numerator. If the difference is less than zero, then the next quotient bit is "0". Then the numerator is left shifted one place. These iterations repeat until they exceed N. The last numerator is the remainder of the division. This technique eliminates useless data manipulation for the cases where this technique determines the quotient bits are "0".