Integer division without using the / or * operator

Teererai Marange Published at Dev

Teererai Marange

I am going through an algorithms and datastructures textbook and came accross this question:

1-28. Write a function to perform integer division without using either the / or * operators. Find a fast way to do it.

How can we come up with a fast way to do it?

mlunoe

I like this solution: https://stackoverflow.com/a/34506599/1008519, but I find it somewhat hard to reason about (especially the |-part). This solution makes a little more sense in my head:

var divide = function (dividend, divisor) {
  // Handle 0 divisor
  if (divisor === 0) {
    return NaN;
  }

  // Handle negative numbers
  var isNegative = false;
  if (dividend < 0) {
    // Change sign
    dividend = ~dividend+1;
    isNegative = !isNegative;
  }

  if (divisor < 0) {
    // Change sign
    divisor = ~divisor+1;
    isNegative = !isNegative;
  }

  /**
   * Main algorithm
   */

  var result = 1;
  var denominator = divisor;
  // Double denominator value with bitwise shift until bigger than dividend
  while (dividend > denominator) {
    denominator <<= 1;
    result <<= 1;
  }

  // Subtract divisor value until denominator is smaller than dividend
  while (denominator > dividend) {
    denominator -= divisor;
    result -= 1;
  }

  // If one of dividend or divisor was negative, change sign of result
  if (isNegative) {
    result = ~result+1;
  }

  return result;
}

We initialize our result to 1 (since we are going to double our denominator until it is bigger than the dividend)
Double our denominator (with bitwise shifts) until it is bigger than the dividend
Since we know our denominator is bigger than our dividend, we can minus our divisor until it is less than our dividend
Return result since denominator is now as close to the result as possible using the divisor

Here are some test runs:

console.log(divide(-16, 3)); // -5
console.log(divide(16, 3)); // 5
console.log(divide(16, 33)); // 0
console.log(divide(16, 0)); // NaN
console.log(divide(384, 15)); // 25

Here is a gist of the solution: https://gist.github.com/mlunoe/e34f14cff4d5c57dd90a5626266c4130

Collected from the Internet

Please contact [email protected] to delete if infringement.