Integer division without using the / or * operator

Question

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?

Answer 1

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;
}

1. We initialize our result to 1 (since we are going to double our denominator until it is bigger than the dividend)
2. Double our denominator (with bitwise shifts) until it is bigger than the dividend
3. Since we know our denominator is bigger than our dividend, we can minus our divisor until it is less than our dividend
4. 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