Campesino Ruso (Multiplica dos números usando operadores bit a bit) – Part 1

Dados dos enteros, escribe una función para multiplicarlos sin usar el operador de multiplicación.
Hay muchas otras formas de multiplicar dos números (por ejemplo, vea esto ). Un método interesante es el algoritmo campesino ruso . La idea es duplicar el primer número y reducir a la mitad el segundo repetidamente hasta que el segundo número no se convierta en 1. En el proceso, cada vez que el segundo número se vuelve impar, agregamos el primer número al resultado (el resultado se inicializa como 0) 
El siguiente es un algoritmo simple. 

Let the two given numbers be 'a' and 'b'
1) Initialize result 'res' as 0.
2) Do following while 'b' is greater than 0
   a) If 'b' is odd, add 'a' to 'res'
   b) Double 'a' and halve 'b'
3) Return 'res'. 

#include <iostream>
using namespace std;
 
// A method to multiply two numbers using Russian Peasant method
unsigned int russianPeasant(unsigned int a, unsigned int b)
{
    int res = 0; // initialize result
 
    // While second number doesn't become 1
    while (b > 0)
    {
        // If second number becomes odd, add the first number to result
        if (b & 1)
            res = res + a;
 
        // Double the first number and halve the second number
        a = a << 1;
        b = b >> 1;
    }
    return res;
}
 
// Driver program to test above function
int main()
{
    cout << russianPeasant(18, 1) << endl;
    cout << russianPeasant(20, 12) << endl;
    return 0;
}

// Java program for Russian Peasant Multiplication
import java.io.*;
 
class GFG
{
    // Function to multiply two
    // numbers using Russian Peasant method
    static int russianPeasant(int a, int b)
    {
        // initialize result
        int res = 0; 
  
        // While second number doesn't become 1
        while (b > 0)
        {
             // If second number becomes odd,
             // add the first number to result
             if ((b & 1) != 0)
                 res = res + a;
  
            // Double the first number
            // and halve the second number
            a = a << 1;
            b = b >> 1;
        }
        return res;
    }
     
    // driver program
    public static void main (String[] args)
    {
        System.out.println(russianPeasant(18, 1));
        System.out.println(russianPeasant(20, 12));
    }
}
 
// Contributed by Pramod Kumar

# A method to multiply two numbers
# using Russian Peasant method
 
# Function to multiply two numbers
# using Russian Peasant method
def russianPeasant(a, b):
 
    res = 0 # initialize result
 
    # While second number doesn't
    # become 1
    while (b > 0):
     
        # If second number becomes
        # odd, add the first number
        # to result
        if (b & 1):
            res = res + a
 
        # Double the first number
        # and halve the second
        # number
        a = a << 1
        b = b >> 1
     
    return res
 
# Driver program to test
# above function
print(russianPeasant(18, 1))
print(russianPeasant(20, 12))
# This code is contributed by
# Smitha Dinesh Semwal

// C# program for Russian Peasant Multiplication
using System;
 
class GFG {
     
    // Function to multiply two
    // numbers using Russian Peasant method
    static int russianPeasant(int a, int b)
    {
        // initialize result
        int res = 0;
 
        // While second number doesn't become 1
        while (b > 0) {
             
            // If second number becomes odd,
            // add the first number to result
            if ((b & 1) != 0)
                res = res + a;
 
            // Double the first number
            // and halve the second number
            a = a << 1;
            b = b >> 1;
        }
        return res;
    }
 
    // driver program
    public static void Main()
    {
        Console.WriteLine(russianPeasant(18, 1));
        Console.WriteLine(russianPeasant(20, 12));
    }
}
 
// This code is contributed by Sam007.

<?php
// PHP Code to multiply two numbers
// using Russian Peasant method
 
// function returns the result
function russianPeasant($a, $b)
{
     
    // initialize result
    $res = 0;
 
    // While second number
    // doesn't become 1
    while ($b > 0)
    {
         
        // If second number becomes odd,
        // add the first number to result
        if ($b & 1)
            $res = $res + $a;
 
        // Double the first number and
        // halve the second number
        $a = $a << 1;
        $b = $b >> 1;
    }
    return $res;
}
 
    // Driver Code
    echo russianPeasant(18, 1), "\n";
    echo russianPeasant(20, 12), "\n";
     
// This code is contributed by Ajit
?>

<script>
 
// A method to multiply two numbers using Russian Peasant method
function russianPeasant(a, b)
{
    var res = 0; // initialize result
 
    // While second number doesn't become 1
    while (b > 0)
    {
     
        // If second number becomes odd, add the first number to result
        if (b & 1)
            res = res + a;
 
        // Double the first number and halve the second number
        a = a << 1;
        b = b >> 1;
    }
    return res;
}
 
// Driver program to test above function
document.write(russianPeasant(18, 1)+"<br>");
document.write(russianPeasant(20, 12));
     
    // This code is contributed by noob2000.
</script>

Producción: 

18
240

Complejidad del tiempo: O(log ₂ b)

Espacio Auxiliar: O(1)

¿Como funciona esto?  
El valor de a*b es el mismo que (a*2)*(b/2) si b es par; de lo contrario, el valor es el mismo que ((a*2)*(b/2) + a). En el bucle while, seguimos multiplicando ‘a’ por 2 y dividiendo ‘b’ entre 2. Si ‘b’ se vuelve impar en el bucle, sumamos ‘a’ a ‘res’. Cuando el valor de ‘b’ se convierte en 1, el valor de ‘res’ + ‘a’ nos da el resultado. 
Tenga en cuenta que cuando ‘b’ es una potencia de 2, la ‘res’ permanecería en 0 y ‘a’ tendría la multiplicación. Consulte la referencia para obtener más información.
Referencia:  
http://mathforum.org/dr.math/faq/faq.peasant.html
Este artículo fue compilado por Shalki Agarwal . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.