Recuento de operaciones de acarreo al sumar dos números binarios

Dados dos números decimales num1 y num2 , la tarea es contar el número de veces que se requiere la operación de acarreo mientras se suman los dos números dados en forma binaria .

Ejemplos:

Entrada: num1 = 15, num2 = 10
Salida: 3
Explicación:
Los números se agregan como:
15 -> 1 1 1 1
10 -> 1 0 1 0
llevar -> 1 1 1 – –
———————— ——
25 -> 1 1 0 0 1

Entrada:  num1 = 14 num2 = 4
Salida: 2
Explicación:
Dar los números se suman como:
14 -> 1 1 1 0
 4 -> 0 1 0 0
llevar -> 1 1 – – –
————————— —
18 -> 1 0 0 1 0
 

Enfoque ingenuo: la idea ingenua es convertir los números en binarios y agregar un bit uno por uno a partir del bit menos significativo y verificar si se genera un acarreo o no. Siempre que se genere un acarreo, aumente la cuenta en 1. Imprima la cuenta de acarreo después de todos los pasos.

Complejidad de tiempo: O(K), donde K es un conteo del número de dígitos en la representación binaria de X.
Espacio auxiliar: O(log N)

Enfoque eficiente: la idea es usar Bitwise XOR y AND. A continuación se muestran los pasos:

• Sume los dos números binarios usando XOR y AND .
• Ahora, el número de 1 en Bitwise AND de dos números muestra el número de bits de acarreo en ese paso.
• Sume el número de unos en cada etapa en el paso anterior para obtener el conteo final de la operación de acarreo .

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

// C++ Program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the number of carry
// operations to add two binary numbers
int carryCount(int num1, int num2)
{
    // To Store the carry count
    int count = 0;
 
    // Iterate till there is no carry
    while (num2 != 0) {
 
        // Carry now contains common
        // set bits of x and y
        int carry = num1 & num2;
 
        // Sum of bits of x and y where at
        // least one of the bits is not set
        num1 = num1 ^ num2;
 
        // Carry is shifted by one
        // so that adding it to x
        // gives the required sum
        num2 = carry << 1;
 
        // Adding number of 1's of
        // carry to final count
        count += __builtin_popcount(num2);
    }
 
    // Return the final count
    return count;
}
 
// Driver Code
int main()
{
    // Given two numbers
    int A = 15, B = 10;
 
    // Function Call
    cout << carryCount(15, 10);
 
    return 0;
}

// Java program for the above approach
class GFG{
 
// Function to count the number of carry
// operations to add two binary numbers
static int carryCount(int num1, int num2)
{
     
    // To Store the carry count
    int count = 0;
 
    // Iterate till there is no carry
    while (num2 != 0)
    {
         
        // Carry now contains common
        // set bits of x and y
        int carry = num1 & num2;
 
        // Sum of bits of x and y where at
        // least one of the bits is not set
        num1 = num1 ^ num2;
 
        // Carry is shifted by one
        // so that adding it to x
        // gives the required sum
        num2 = carry << 1;
 
        // Adding number of 1's of
        // carry to final count
        count += Integer.bitCount(num2);
    }
 
    // Return the final count
    return count;
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given two numbers
    int A = 15, B = 10;
 
    // Function call
    System.out.print(carryCount(A, B));
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program for the above approach
 
# Function to count the number of carry
# operations to add two binary numbers
def carryCount(num1, num2):
 
    # To Store the carry count
    count = 0
 
    # Iterate till there is no carry
    while(num2 != 0):
 
        # Carry now contains common
        # set bits of x and y
        carry = num1 & num2
 
        # Sum of bits of x and y where at
        # least one of the bits is not set
        num1 = num1 ^ num2
 
        # Carry is shifted by one
        # so that adding it to x
        # gives the required sum
        num2 = carry << 1
 
        # Adding number of 1's of
        # carry to final count
        count += bin(num2).count('1')
 
    # Return the final count
    return count
 
# Driver Code
 
# Given two numbers
A = 15
B = 10
 
# Function call
print(carryCount(A, B))
 
# This code is contributed by Shivam Singh

// C# program for the above approach
using System;
class GFG{
   
static int countSetBits(int x)
{
    int setBits = 0;
    while (x != 0)
    {
        x = x & (x - 1);
        setBits++;
    }
    return setBits;
}
// Function to count the number of carry
// operations to add two binary numbers
static int carryCount(int num1, int num2)
{
     
    // To Store the carry count
    int count = 0;
 
    // Iterate till there is no carry
    while (num2 != 0)
    {
         
        // Carry now contains common
        // set bits of x and y
        int carry = num1 & num2;
 
        // Sum of bits of x and y where at
        // least one of the bits is not set
        num1 = num1 ^ num2;
 
        // Carry is shifted by one
        // so that adding it to x
        // gives the required sum
        num2 = carry << 1;
 
        // Adding number of 1's of
        // carry to readonly count
        count += countSetBits(num2);
    }
 
    // Return the readonly count
    return count;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given two numbers
    int A = 15, B = 10;
 
    // Function call
    Console.Write(carryCount(A, B));
}
}
 
// This code is contributed by Rohit_ranjan

<script>
// JavaScript program for the
// above approach
  
function countSetBits(x)
{
    let setBits = 0;
    while (x != 0)
    {
        x = x & (x - 1);
        setBits++;
    }
    return setBits;
}
 
// Function to count the number of carry
// operations to add two binary numbers
function carryCount(num1, num2)
{
      
    // To Store the carry count
    let count = 0;
  
    // Iterate till there is no carry
    while (num2 != 0)
    {
          
        // Carry now contains common
        // set bits of x and y
        let carry = num1 & num2;
  
        // Sum of bits of x and y where at
        // least one of the bits is not set
        num1 = num1 ^ num2;
  
        // Carry is shifted by one
        // so that adding it to x
        // gives the required sum
        num2 = carry << 1;
  
        // Adding number of 1's of
        // carry to readonly count
        count += countSetBits(num2);
    }
  
    // Return the readonly count
    return count;
}
 
// Driver Code
 
     
    // Given two numbers
    let A = 15, B = 10;
  
    // Function call
    document.write(carryCount(A, B));
 
</script>

3

Complejidad de Tiempo: O(log ₂ (N))
Espacio Auxiliar: O(1)