Рубрики

Битовое рекурсивное сложение двух целых

При добавлении двух двоичных чисел вручную мы учитываем биты переноса и добавляем их одновременно. Но чтобы сделать то же самое в программе, нам нужно много проверок. Рекурсивное решение можно представить как сложение переноса и a ^ b (два входа), пока перенос не станет равным 0.

Примеры :

Input : int x = 45, y = 45
Output : 90

Input : int x = 4, y = 78
Output : 82

Сумма двух битов может быть получена путем выполнения XOR (^) двух битов. Несущий бит может быть получен путем выполнения И (&) двух битов.
Выше приведена простая логика Half Adder, которую можно использовать для добавления двух отдельных битов. Мы можем расширить эту логику для целых чисел. Если x и y не имеют установленных битов в одной и той же позиции (ях), то побитовое значение XOR (^) для x и y дает сумму x и y. Для включения общих битов также используется побитовое И (&). Побитовое И х и у дает все биты переноса. Мы вычисляем (x & y) << 1 и добавляем его к x ^ y, чтобы получить требуемый результат.

Одно важное наблюдение состоит в том, что если (x & y) становится 0, то результатом является x ^ y.

С

// Программа CPP для рекурсивного сложения
// из двух целых
#include <stdio.h>

  

int add(int x, int y) { 

    int keep = (x & y) << 1;

    int res = x^y;

  

    // Если поразрядно & равно 0, тогда

    // не будет никакого переноса.

    // Следовательно, результатом XOR является сложение.

    if (keep == 0)

        return res;

  

    add(keep, res);

}

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

int main(){

    printf("%d", add(15, 38));

    return 0;

Джава

// Java-программа для рекурсивного сложения
// из двух целых

import java.io.*;

  

class GFG {

      

    static int add(int x, int y)

    

        int keep = (x & y) << 1;

        int res = x^y;

      

        // Если поразрядно & равно 0, тогда

        // не будет никакого переноса.

        // Следовательно, результатом XOR является сложение.

        if (keep == 0)

            return res;

              

        return add(keep, res);

    }

  

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

    public static void main (String[] args)

    {

        System.out.println(add(15, 38));

    }

}

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

python3

      
# Python программа для рекурсивного сложения
# из двух целых

   

def add(x, y): 

    keep = (x & y) << 1;

    res = x^y;

   

    # Если поразрядно & равно 0, тогда

    # не будет никакого переноса.

    # Следовательно, результатом XOR является сложение.

    if (keep == 0):

        return res;

   

    return add(keep, res);

  

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

  

print(add(15, 38));

  
# Этот код предоставлен Принчи Сингхом

C #

// C # программа для рекурсии
// сложение двух целых

using System;

  

class GFG {

      

    static int add(int x, int y)

    

        int keep = (x & y) << 1;

        int res = x^y;

      

        // Если поразрядно & равно 0, тогда

        // не будет никакого переноса.

        // Следовательно, результатом XOR является сложение.

        if (keep == 0)

            return res;

              

        return add(keep, res);

    }

  

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

    public static void Main ()

    {

        Console.Write(add(15, 38));

    }

}

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

PHP

<?php
// php программа для рекурсивного сложения
// из двух целых

  

function add($x, $y) { 

    $keep = ($x & $y) << 1;

    $res = $x^$y;

  

    // Если поразрядно & равно 0, тогда

    // не будет никакого переноса.

    // Следовательно, результатом XOR является сложение.

    if ($keep == 0)

    {

        echo $res;

        exit(0);

    }

  

    add($keep, $res);

}

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

$k= add(15, 38);

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

Выход:

53

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

Битовое рекурсивное сложение двух целых

0.00 (0%) 0 votes