Рубрики

Русский крестьянин (умножить два числа с помощью побитовых операторов)

Учитывая два целых числа, напишите функцию, чтобы умножить их без использования оператора умножения.

Есть много других способов умножения двух чисел (например, см. Это ). Один интересный метод — русский крестьянский алгоритм . Идея состоит в том, чтобы удвоить первое число и несколько раз вдвое увеличить второе число, пока второе число не станет равным 1. В процессе, когда второе число становится нечетным, мы добавляем первое число к результату (результат инициализируется как 0)
Ниже приведен простой алгоритм.

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'. 

C / C ++

#include <iostream>

using namespace std;

  
// Метод умножения двух чисел методом русского крестьянина

unsigned int russianPeasant(unsigned int a, unsigned int b)

{

    int res = 0;  // инициализировать результат

  

    // Пока второе число не становится 1

    while (b > 0)

    {

         // Если второе число становится нечетным, добавьте первое число к результату

         if (b & 1)

             res = res + a;

  

         // Удваиваем первое число и делим пополам второе число

         a = a << 1;

         b = b >> 1;

     }

     return res;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    cout << russianPeasant(18, 1) << endl;

    cout << russianPeasant(20, 12) << endl;

    return 0;

}

Джава

// Java программа для умножения русского крестьянина

import java.io.*;

  

class GFG 

{

    // Функция умножения двух

    // числа с использованием русского крестьянского метода

    static int russianPeasant(int a, int b)

    {

        // инициализировать результат

        int res = 0;  

   

        // Пока второе число не становится 1

        while (b > 0)

        {

             // Если второе число становится нечетным,

             // добавляем первое число к результату

             if ((b & 1) != 0)

                 res = res + a;

   

            // Удваиваем первое число

            // и делим пополам второе число

            a = a << 1;

            b = b >> 1;

        }

        return res;

    }

      

    // драйверная программа

    public static void main (String[] args) 

    {

        System.out.println(russianPeasant(18, 1));

        System.out.println(russianPeasant(20, 12));

    }

}

  
// Предоставлено Прамод Кумар

Python 3

# Способ умножения двух чисел
# используя русский крестьянский метод

  
# Функция умножения двух чисел
# используя русский крестьянский метод

def russianPeasant(a, b):

  

    res = 0 # инициализировать результат

  

    # В то время как второй номер не

    # стать 1

    while (b > 0):

      

        # Если второй номер становится

        # нечетно, добавьте первый номер

        # результат

        if (b & 1):

            res = res + a

  

        # Удвойте первое число

        # и наполовину второй

        # число

        a = a << 1

        b = b >> 1

      

    return res

  
# Драйвер программы для тестирования
# выше функция

print(russianPeasant(18, 1))

print(russianPeasant(20, 12))

# Этот код предоставлен
# Смита Динеш Семвал

C #

// C # программа для умножения русского крестьянина

using System;

  

class GFG {

      

    // Функция умножения двух

    // числа с использованием русского крестьянского метода

    static int russianPeasant(int a, int b)

    {

        // инициализировать результат

        int res = 0;

  

        // Пока второе число не становится 1

        while (b > 0) {

              

            // Если второе число становится нечетным,

            // добавляем первое число к результату

            if ((b & 1) != 0)

                res = res + a;

  

            // Удваиваем первое число

            // и делим пополам второе число

            a = a << 1;

            b = b >> 1;

        }

        return res;

    }

  

    // драйверная программа

    public static void Main()

    {

        Console.WriteLine(russianPeasant(18, 1));

        Console.WriteLine(russianPeasant(20, 12));

    }

}

  
// Этот код предоставлен Sam007.

PHP

<?php
// PHP код для умножения двух чисел
// используя русский крестьянский метод

  
// функция возвращает результат

function russianPeasant($a, $b)

{

      

    // инициализировать результат

    $res = 0; 

  

    // пока второе число

    // не становится 1

    while ($b > 0)

    {

          

        // Если второе число становится нечетным,

        // добавляем первое число к результату

        if ($b & 1)

            $res = $res + $a;

  

        // Удваиваем первое число и

        // делим второе число пополам

        $a = $a << 1;

        $b = $b >> 1;

    }

    return $res;

}

  

    // Код драйвера

    echo russianPeasant(18, 1), "\n";

    echo russianPeasant(20, 12), "\n";

      
// Этот код предоставлен Ajit
?>


Выход:

18
240

Как это работает?
Значение a * b такое же, как (a * 2) * (b / 2), если b четное, в противном случае значение такое же, как ((a * 2) * (b / 2) + a). В цикле while мы продолжаем умножать «a» на 2 и делим «b» на 2. Если «b» становится нечетным в цикле, мы добавляем «a» к «res». Когда значение «b» становится равным 1, значение «res» + «a» дает нам результат.
Обратите внимание, что когда «b» является степенью 2, «res» останется 0, а «a» будет иметь умножение. Смотрите ссылку для получения дополнительной информации.

Ссылка:
http://mathforum.org/dr.math/faq/faq.peasant.html

Эта статья составлена Шалки Агарвал . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Русский крестьянин (умножить два числа с помощью побитовых операторов)

0.00 (0%) 0 votes