When I encountered Leetcode's Divide Two Integers problem, I immediately remembered the MIPS architecture and various ALU implementations I did in verilog for my CS classes. I heavily referenced this document on ALU Division Design, and used it to guide my C++ implementation.
This turned out to be a really straightforward solution to implement, and somewhat different than the solution recommended on Leetcode's "Editorial" tab. Let's see how it works.
Lets say we are doing this division on a system that uses 5-bit integers:
dividend = 20; // 0b10100
divisor = 2; // 0b00010
; 20/2 = 10; // 0b01010In this case, we'd need a 10-bit container ("remainder") to do the division. We also need a quotient, set to zero. Our loop would take 5 iterations to complete.
; Before loop:
Quotient = 0b00000;
Remainder = dividend = 0b00000 10100;
hi = 0b00000;
lo = 0b01000;Each iteration of loop:
- Shifts "Remainder" left by 1
- Shifts "Quotient" left by 1
- Reads the top 5 bits of "Remainder" into
hias an integer - If
hi>=divisor, then A: add 1 to quotient, B: subtract divisor from hi, C: set the top 5 bits ofremainderto the new value ofhi.
A breakdown of how each loop iterates shows how this yields the quotient of 10, or 0b01010:
;Iteration 1:
;Divisor: 0b00010
; LAST ITER THIS ITER
Quotient = 0 << 1 = 0b00000
Remainder = 0b00000 10100 << 1 = 0b00001 01000
; hi = 0b00001
; lo = 0b01000
; hi >= divisor?
; 0b00001 is not >= 0b00010; take no action ;Iteration 2:
;Divisor: 0b00010
; LAST ITER THIS ITER
Quotient = 0 << 1 = 0b00000
Remainder = 0b00001 01000 << 1 = 0b00010 10000
; hi = 0b00010
; lo = 0b10000
; hi IS >= divisor, so:
quotient +1 = 0b00001 ; = 1
hi = hi - divisor ; 0b00010 - 0b00010 = 0
; now set remainder as the concatenation of
; hi and lo:
; hi lo
remainder = 0b 00000 10000;Iteration 3:
;Divisor = 0b00010
; LAST ITER THIS ITER
Quotient = 0b00001 << 1 = 0b00010 ; = 2
Remainder = 0b00000 10000 << 1 = 0b00001 00000
; hi = 0b00001
; lo = 0b00000
; hi is not >= divisor, so no further action;Iteration 4:
;Divisor = 0b00010
; LAST ITER THIS ITER
Quotient = 0b00010 << 1 = 0b00100 ; = 4
Remainder = 0b00001 00000 << 1 = 0b00010 00000
; hi = 0b00010
; lo = 0b00000
; hi is >= divisor, so:
quotient +1 = 0b00101 ; = 5
hi = hi - divisor ; 0b00010 - 0b00010 = 0
; now set remainder as the concatenation of
; hi and lo:
; hi lo
remainder = 0b 00000 00000;Iteration 5:
;Divisor = 0b00010
; LAST ITER THIS ITER
Quotient = 0b00101 << 1 = 0b01010 ; = 10
Remainder = 0b00000 00000 << 1 = 0b00000 00000
; hi = 0b00000
; lo = 0b00000
; hi is >= divisor, so take no actionThus, after five iterations of the loop, we're left with the binary string '01010', or 10, correctly finding the answer for 20/2.
Now that we understand how ALU division works, we can tackle the LeetCode problem easily.
class Solution {
public:
// Easy aliases for the boundaries of int values
static const int MAX = numeric_limits<int>::max();
static const int MIN = numeric_limits<int>::min();
// Zeroes out the left half of a 64-bit int when
// bitwise-and'd (`a &get_right`) with it
static const uint64_t get_right = 0x00000000FFFFFFFF;
int divide(int dividend, int divisor) {
// Determine if output should be positive or negative
// We're going to need to know later, since we're going
// to force everything to the same sign.
bool opp_signs = (
((dividend > 0) && (divisor < 0)) ||
((dividend < 0) && (divisor > 0))
);
// Variables
// -
// Hex 0's provided to visualize relative length
// of each variable in bits
// -
// We have two 64-bit containers for working through the division,
// as well as two 32-bit containers for reading the left and right
// halves of "remainder" as binary strings.
uint64_t remainder = 0x0000000000000000;
uint64_t tmp = 0x0000000000000000;
uint32_t hi = 0x00000000;
uint32_t lo = 0x00000000;
int quotient = 0x00000000;
// Step 1:
// Force all values to same sign
// -
// The WHY:
// To do division, we're going to count how many times we can take
// `divisor` out of `dividend` (using subtraction) before the
// result is 0. We need the signs to be the same to know that
// subtraction is taking us in the direction of 0.
int64_t dividend_64 = dividend;
dividend_64 = abs(dividend_64);
int64_t divisor_64 = divisor;
divisor_64 = abs(divisor_64);
// Step 2:
// Set the remainder value.
remainder = dividend_64;
// Doing Division:
// Again, division is just a matter of counting how many
// times we can subtract the divisor from the remainder.
//
// We are going to move each of the 32 bits of "dividend"
// into the left-hand side of "remainder" one at a time. Whenever
// the first 32 bits of "remainder" have a value that's greater
// or equal to divisor, we'll do a subtraction and add 1 to the
// quotient. The quotient (starting at 0) is multiplied by 2
// for each iteration of the loop.
//
// If we repeat this 32 times, "quotient" will contain the
// correct value, aside from any necessary positive/negative
// conversion based on the value of `opp_signs`.
for (int n = 0; n < 32; n++) {
// Shift remainder and quotient values left 1 bit.
// This is the same as multiplying their values by 2.
remainder = remainder << 1;
quotient = quotient << 1;
// Update hi and lo values
tmp = remainder;
lo = tmp&get_right; // Lo is the right side of remainder
tmp = tmp >> 32; // remove the right side of remainder from tmp,
// leaving only the left side
hi = tmp; // hi is the left side of remainder
// If the left-hand side of "remainder" is larger than or equal to
// "divisor", we handle it similarly to long division. We add 1 to
// our quotient and subtract divisor from remainder.
if (hi >= divisor_64) {
// Add "1" to the quotient value.
quotient += 1;
// Subtract from the remainder
hi -= divisor_64;
// Remember that "hi" is the left-most 32 bits of "remainder":
// if we want the result of our subtraction to be remembered at
// the start of the next loop, we need to update "remainder"
// to contain our updated 32-bit value.
//
// We preserved the lower 32 bits in "lo" at the start of the loop
// iteration, so hi + lo, concatenated, is the 64-bit remainder
// value we want.
//
// To concatenate them, we need 3 steps:
remainder = hi;
// 1. This sets the lower 32 bits to "hi" and the rest to 0.
remainder = remainder << 32;
// 2. This moves those 32 bits from "hi" into the upper 32 bits,
// and makes the right side all 0's.
remainder = remainder | lo;
// 3. This sets the lower 32 bits to "lo".
}
}
// Fix signs on quotient:
// ----------------------
// If the signs were opposite, we need to negate quotient.
//
// There are two special cases:
// 1: If signs are opposite and quotient == min, return min
// 2: If signs are the same and quotient == min, return max
// You could return the value on each of those, if you wanted.
// For legibility, I use a single return statement.
if (opp_signs)
if (quotient == MIN)
quotient = MIN;
else
quotient = -quotient;
else if (quotient == MIN)
quotient = MAX;
return quotient;
}
};I find this to be a fantastic educational solution to the problem. However, it technically cheats, since the problem says:
Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range:
[−231, 231 − 1].
It's worth studying the "binary long division" algorithm, in the "Editorial" tab, as well; it's based on the ALU bit-manipulation approach, but a bit more clever.