Divide dos números enteros sin usar multiplicación, división y operador mod – Part 1

Dados dos números enteros, digamos a y b. Encuentre el cociente después de dividir a por b sin usar la multiplicación, la división y el operador mod.

Ejemplo: 

Entrada: a = 10, b = 3
Salida: 3

Entrada: a = 43, b = -8
Salida:  -5 

Método: siga restando el divisor del dividendo hasta que el dividendo sea menor que el divisor. El dividendo se convierte en el resto y el número de veces que se resta se convierte en el cociente. A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation to Divide two
// integers without using multiplication,
// division and mod operator
#include <bits/stdc++.h>
using namespace std;
 
// Function to divide a by b and
// return floor value of the result
long long divide(long long dividend, long long int divisor)
{
 
    // Calculate sign of divisor i.e.,
    // sign will be negative only if
    // either one of them is negative
    // otherwise it will be positive
    long long sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
 
    // Update both divisor and
    // dividend positive
    dividend = abs(dividend);
    divisor = abs(divisor);
 
    // Initialize the quotient
    long long quotient = 0;
    while (dividend >= divisor) {
        dividend -= divisor;
        ++quotient;
    }
 
    // Return the value of quotient with the appropriate
    // sign.
    return quotient * sign;
}
 
// Driver code
int main()
{
    int a = -2147483648, b = -1;
    cout << divide(a, b) << "\n";
 
    a = 43, b = -8;
    cout << divide(a, b);
 
    return 0;
}

/*Java implementation to Divide two
integers without using multiplication,
division and mod operator*/
 
import java.io.*;
 
class GFG {
 
    // Function to divide a by b and
    // return floor value it
    static long divide(long dividend, long divisor)
    {
 
        // Calculate sign of divisor i.e.,
        // sign will be negative only if
        // either one of them is negative
        // otherwise it will be positive
        long sign
            = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
 
        // Update both divisor and
        // dividend positive
        dividend = Math.abs(dividend);
        divisor = Math.abs(divisor);
 
        // Initialize the quotient
        long quotient = 0;
 
        while (dividend >= divisor) {
            dividend -= divisor;
            ++quotient;
        }
        // if the sign value computed earlier is -1 then
        // negate the value of quotient
        if (sign == -1)
            quotient = -quotient;
 
        return quotient;
    }
 
    public static void main(String[] args)
    {
        int a = -2147483648;
        int b = -1;
 
        System.out.println(divide(a, b));
 
        a = 43;
        b = -8;
 
        System.out.println(divide(a, b));
    }
}
 
// This code is contributed by upendra singh bartwal.

# Python 3 implementation to Divide two
# integers without using multiplication,
# division and mod operator
 
# Function to divide a by b and
# return floor value it
 
 
def divide(dividend, divisor):
 
    # Calculate sign of divisor i.e.,
    # sign will be negative only if
    # either one of them is negative
    # otherwise it will be positive
    sign = -1 if ((dividend < 0) ^ (divisor < 0)) else 1
 
    # Update both divisor and
    # dividend positive
    dividend = abs(dividend)
    divisor = abs(divisor)
 
    # Initialize the quotient
    quotient = 0
    while (dividend >= divisor):
        dividend -= divisor
        quotient += 1
 
     # if the sign value computed earlier is -1 then negate the value of quotient
 
    if sign == -1:
        quotient = -quotient
 
    return quotient
 
 
# Driver code
a = 10
b = 3
print(divide(a, b))
a = 43
b = -8
print(divide(a, b))
 
# This code is contributed by
# Smitha Dinesh Semwal

// C# implementation to Divide two without
// using multiplication, division and mod
// operator
using System;
 
class GFG {
 
    // Function to divide a by b and
    // return floor value it
    static int divide(int dividend, int divisor)
    {
 
        // Calculate sign of divisor i.e.,
        // sign will be negative only if
        // either one of them is negative
        // otherwise it will be positive
        int sign
            = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
 
        // Update both divisor and
        // dividend positive
        dividend = Math.Abs(dividend);
        divisor = Math.Abs(divisor);
 
        // Initialize the quotient
        int quotient = 0;
 
        while (dividend >= divisor) {
            dividend -= divisor;
            ++quotient;
        }
 
        // if the sign value computed earlier is -1 then
        // negate the value of quotient
        if (sign == -1)
            quotient = -quotient;
        return quotient;
    }
 
    public static void Main()
    {
 
        int a = 10;
        int b = 3;
        Console.WriteLine(divide(a, b));
 
        a = 43;
        b = -8;
        Console.WriteLine(divide(a, b));
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP implementation to Divide two
// integers without using multiplication,
// division and mod operator
 
// Function to divide a by b and
// return floor value it
function divide($dividend, $divisor) {
 
    // Calculate sign of divisor i.e.,
    // sign will be negative only if
    // either one of them is negative
    // otherwise it will be positive
    $sign = (($dividend < 0) ^
             ($divisor < 0)) ? -1 : 1;
     
    // Update both divisor and
    // dividend positive
    $dividend = abs($dividend);
    $divisor = abs($divisor);
     
    // Initialize the quotient
    $quotient = 0;
    while ($dividend >= $divisor)
    {
        $dividend -= $divisor;
        ++$quotient;
    }
    //if the sign value computed earlier is -1 then negate the value of quotient
    if($sign==-1) $quotient=-$quotient;
    return $quotient;
}
 
// Driver code
$a = 10;
$b = 3;
echo divide($a, $b)."\n";
 
$a = 43;
$b = -8;
echo divide($a, $b);
 
// This code is contributed by Sam007
?>

<script>
 
// Javascript implementation to Divide two
// integers without using multiplication,
// division and mod operator
 
// Function to divide a by b and
// return floor value it
function divide(dividend, divisor) {
 
// Calculate sign of divisor i.e.,
// sign will be negative only if
// either one of them is negative
// otherwise it will be positive
let sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
 
// Update both divisor and
// dividend positive
dividend = Math.abs(dividend);
divisor = Math.abs(divisor);
 
// Initialize the quotient
let quotient = 0;
while (dividend >= divisor) {
    dividend -= divisor;
    ++quotient;
}
//if the sign value computed earlier is -1 then negate the value of quotient
if(sign==-1) quotient=-quotient;
return quotient;
}
 
// Driver code
let a = 10, b = 3;
document.write(divide(a, b) + "<br>");
 
a = 43, b = -8;
document.write(divide(a, b));
 
// This code is contributed by Surbhi Tyagi.
 
</script>

3
-5

Complejidad temporal : O(a/b) 
Espacio auxiliar : O(1)

Enfoque eficiente: utilice la manipulación de bits para encontrar el cociente. El divisor y el dividendo se pueden escribir como 

dividendo = cociente * divisor + resto

Como cada número se puede representar en base 2 (0 o 1), represente el cociente en forma binaria usando el operador de cambio como se indica a continuación: 

1. Determine el bit más significativo en el divisor. Esto se puede calcular fácilmente iterando en la posición del bit i de 31 a 1.
2. Encuentre el primer bit para el cual el  divisor << i es menor que el dividendo y siga actualizando la i ^-ésima posición del bit para el cual es verdadero.
3. Agregue el resultado en la variable temporal para verificar la siguiente posición de modo que (temp + (divisor << i)) sea menor que el dividendo .
4. Devuelve la respuesta final del cociente después de actualizar con el signo correspondiente.

A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation to Divide two
// integers without using multiplication,
// division and mod operator
#include <bits/stdc++.h>
using namespace std;
 
// Function to divide a by b and
// return floor value it
long long divide(long long dividend, long long divisor) {
 
  // Calculate sign of divisor i.e.,
  // sign will be negative only if
  // either one of them is negative
  // otherwise it will be positive
  int sign = ((dividend < 0) ^
              (divisor < 0)) ? -1 : 1;
 
  // remove sign of operands
  dividend = abs(dividend);
  divisor = abs(divisor);
 
  // Initialize the quotient
  long long quotient = 0, temp = 0;
 
  // test down from the highest bit and
  // accumulate the tentative value for
  // valid bit
  for (int i = 31; i >= 0; --i) {
 
    if (temp + (divisor << i) <= dividend) {
      temp += divisor << i;
      quotient |= 1LL << i;
    }
  }
  //if the sign value computed earlier is -1 then negate the value of quotient
  if(sign==-1) quotient=-quotient;
   
  return quotient;
}
 
// Driver code
int main() {
  int a = -2147483648, b = -1;
  cout << divide(a, b) << "\n";
 
  a = 43, b = -8;
  cout << divide(a, b);
 
  return 0;
}

// Java implementation to Divide
// two integers without using
// multiplication, division
// and mod operator
import java.io.*;
import java.util.*;
 
// Function to divide a by b
// and return floor value it
class GFG
{
public static long divide(long dividend,
                        long divisor)
{
 
// Calculate sign of divisor
// i.e., sign will be negative
// only if either one of them
// is negative otherwise it
// will be positive
long sign = ((dividend < 0) ^
            (divisor < 0)) ? -1 : 1;
 
// remove sign of operands
dividend = Math.abs(dividend);
divisor = Math.abs(divisor);
 
// Initialize the quotient
long quotient = 0, temp = 0;
 
// test down from the highest
// bit and accumulate the
// tentative value for
// valid bit
// 1<<31 behaves incorrectly and gives Integer
// Min Value which should not be the case, instead
  // 1L<<31 works correctly.
for (int i = 31; i >= 0; --i)
{
 
    if (temp + (divisor << i) <= dividend)
    {
        temp += divisor << i;
        quotient |= 1L << i;
    }
}
 
//if the sign value computed earlier is -1 then negate the value of quotient
if(sign==-1)
  quotient=-quotient;
return quotient;
}
 
// Driver code
public static void main(String args[])
{
int a = 10, b = 3;
System.out.println(divide(a, b));
 
int a1 = 43, b1 = -8;
System.out.println(divide(a1, b1));
 
 
}
}
 
// This code is contributed
// by Akanksha Rai(Abby_akku)

# Python3 implementation to
# Divide two integers
# without using multiplication,
# division and mod operator
 
# Function to divide a by
# b and return floor value it
def divide(dividend, divisor):
     
    # Calculate sign of divisor
    # i.e., sign will be negative
    # either one of them is negative
    # only if otherwise it will be
    # positive
     
    sign = (-1 if((dividend < 0) ^
                  (divisor < 0)) else 1);
     
    # remove sign of operands
    dividend = abs(dividend);
    divisor = abs(divisor);
     
    # Initialize
    # the quotient
    quotient = 0;
    temp = 0;
     
    # test down from the highest
    # bit and accumulate the
    # tentative value for valid bit
    for i in range(31, -1, -1):
        if (temp + (divisor << i) <= dividend):
            temp += divisor << i;
            quotient |= 1 << i;
    #if the sign value computed earlier is -1 then negate the value of quotient
    if sign ==-1 :
      quotient=-quotient;
    return quotient;
 
# Driver code
a = 10;
b = 3;
print(divide(a, b));
 
a = 43;
b = -8;
print(divide(a, b));
 
# This code is contributed by mits

// C# implementation to Divide
// two integers without using
// multiplication, division
// and mod operator
using System;
 
// Function to divide a by b
// and return floor value it
class GFG
{
public static long divide(long dividend,
                          long divisor)
{
 
// Calculate sign of divisor
// i.e., sign will be negative
// only if either one of them
// is negative otherwise it
// will be positive
long sign = ((dividend < 0) ^
             (divisor < 0)) ? -1 : 1;
 
// remove sign of operands
dividend = Math.Abs(dividend);
divisor = Math.Abs(divisor);
 
// Initialize the quotient
long quotient = 0, temp = 0;
 
// test down from the highest
// bit and accumulate the
// tentative value for
// valid bit
for (int i = 31; i >= 0; --i)
{
 
    if (temp + (divisor << i) <= dividend)
    {
        temp += divisor << i;
        quotient |= 1LL << i;
    }
}
//if the sign value computed earlier is -1 then negate the value of quotient
  if(sign==-1)
    quotient=-quotient;
return quotient;
}
 
// Driver code
public static void Main()
{
int a = 10, b = 3;
Console.WriteLine(divide(a, b));
 
int a1 = 43, b1 = -8;
Console.WriteLine(divide(a1, b1));
 
}
}
 
// This code is contributed by mits

<?php
// PHP implementation to
// Divide two integers
// without using multiplication,
// division and mod operator
 
// Function to divide a by
// b and return floor value it
function divide($dividend,
                $divisor)
{
 
// Calculate sign of divisor
// i.e., sign will be negative
// either one of them is negative
// only if otherwise it will be
// positive
$sign = (($dividend < 0) ^
         ($divisor < 0)) ? -1 : 1;
 
// remove sign of operands
$dividend = abs($dividend);
$divisor = abs($divisor);
 
// Initialize
// the quotient
$quotient = 0;
$temp = 0;
 
// test down from the highest
// bit and accumulate the
// tentative value for valid bit
for ($i = 31; $i >= 0; --$i)
{
 
    if ($temp + ($divisor << $i) <= $dividend)
    {
        $temp += $divisor << $i;
        $quotient |= (double)(1) << $i;
    }
}
//if the sign value computed earlier is -1 then negate the value of quotient
if($sign==-1)
  $quotient=-$quotient;
return $quotient;
}
 
// Driver code
$a = 10;
$b = 3;
echo divide($a, $b). "\n";
 
$a = 43;
$b = -8;
echo divide($a, $b);
 
// This code is contributed by mits
?>

<script>
 
// JavaScript implementation to Divide
// two integers without using
// multiplication, division
// and mod operator
 
// Function to divide a by b
// and return floor value it
 
function divide(dividend, divisor)
{
 
// Calculate sign of divisor
// i.e., sign will be negative
// only if either one of them
// is negative otherwise it
// will be positive
var sign = ((dividend < 0)?1:0 ^
             (divisor < 0)?1:0) ? -1 : 1;
 
// remove sign of operands
dividend = Math.abs(dividend);
divisor = Math.abs(divisor);
 
// Initialize the quotient
var quotient = 0, temp = 0;
 
// test down from the highest
// bit and accumulate the
// tentative value for
// valid bit
while (dividend >= divisor) {
    dividend -= divisor;
    ++quotient;
}
//if the sign value computed earlier is -1 then negate the value of quotient
if(sign==-1) quotient=-quotient;
return quotient;
}
 
// Driver code
 
var a = 10, b = 3;
document.write(divide(a, b) + "<br>");
 
var a1 = 43, b1 = -8;
document.write(divide(a1, b1) + "<br>");
 
 
 
</script>

3
-5

Complejidad temporal : O(log(a)) 
Espacio auxiliar : O(1)