Voltear bits de la suma de conteo de bits establecidos de dos números dados

Dados dos números A y B , la tarea es contar el número de bits establecidos en A y B y voltear los bits de la suma obtenida.

Ejemplos:

Entrada: A = 5, B = 7
Salida: 2
Explicación:
La representación binaria de A es 101. La
representación binaria de B es 111.
Conteo de bits establecidos en A y B = 2 + 3 = 5.
Representación binaria de la suma obtenida = 101
Volteando los bits de la suma, el número obtenido es (010) ₂ = 2. 
Por lo tanto, la salida requerida es 2.

Entrada: A = 76, B = 35
Salida: 1
Explicación: 
La representación binaria de A es 1001100 La
representación binaria de B es 100011
Recuento de bits establecidos en A y B = 3 + 3 = 6
Representación binaria de la suma obtenida = 110
Volteando la bits de la suma, el número obtenido es (001) ₂ = 1. 
Por lo tanto, la salida requerida es 1.

Enfoque ingenuo: la idea para resolver este problema es primero atravesar la representación binaria de ambos números y contar el número de bits establecidos en ambos números. Finalmente, súmalos e invierte los bits del número resultante.

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 number of
// set bits in integer
int countSetBits(int n)
{
    // Variable for counting set bits
    int count = 0;
    while (n) {
        n &= (n - 1);
        count++;
    }
    return count;
}
 
// Function to invert bits of a number
int invertBits(int n)
{
    // Calculate number of bits of N-1;
    int x = log2(n);
 
    int m = 1 << x;
    m = m | m - 1;
    n = n ^ m;
 
    return n;
}
 
// Function to invert the sum
// of set bits in A and B
void invertSum(int A, int B)
{
 
    // Stores sum of set bits
    int temp = countSetBits(A)
               + countSetBits(B);
    cout << invertBits(temp) << endl;
}
 
// Driver Code
int main()
{
    int A = 5;
    int B = 7;
 
    invertSum(A, B);
    return 0;
}

// Java program for the above approach
import java.util.*;
   
class GFG{
  
// Function to count number of
// set bits in integer
static int countSetBits(int n)
{
     
    // Variable for counting set bits
    int count = 0;
     
    while (n != 0)
    {
        n &= (n - 1);
        count++;
    }
    return count;
}
  
// Function to invert bits of a number
static int invertBits(int n)
{
     
    // Calculate number of bits of N-1;
    int x = (int)(Math.log(n) / Math.log(2));
      
    int m = 1 << x;
    m = m | m - 1;
    n = n ^ m;
      
    return n;
}
  
// Function to invert the sum
// of set bits in A and B
static void invertSum(int A, int B)
{
     
    // Stores sum of set bits
    int temp = countSetBits(A) +
               countSetBits(B);
                 
    System.out.print(invertBits(temp));
}
   
// Driver Code
static public void main(String args[])
{
    int A = 5;
    int B = 7;
      
    invertSum(A, B);
}
}
 
// This code is contributed by susmitakundugoaldanga

# Python3 program for the above approach
import math
 
# Function to count number of
# set bits in integer
def countSetBits(n):
     
    # Variable for counting set bits
    count = 0
 
    while (n != 0):
        n &= (n - 1)
        count += 1
 
    return count
 
# Function to invert bits of a number
def invertBits(n):
     
    # Calculate number of bits of N-1;
    x = (int)(math.log(n) / math.log(2))
 
    m = 1 << x
    m = m | m - 1
    n = n ^ m
 
    return n
 
# Function to invert the sum
# of set bits in A and B
def invertSum(A, B):
     
    # Stores sum of set bits
    temp = countSetBits(A) + countSetBits(B)
 
    print(invertBits(temp))
 
# Driver Code
A = 5
B = 7
 
invertSum(A, B)
 
# This code is contributed by shikhasingrajput

// C# program for the above approach
using System;
 
class GFG{
     
// Function to count number of
// set bits in integer
static int countSetBits(int n)
{
     
    // Variable for counting set bits
    int count = 0;
    while (n != 0)
    {
        n &= (n - 1);
        count++;
    }
    return count;
}
 
// Function to invert bits of a number
static int invertBits(int n)
{
     
    // Calculate number of bits of N-1;
    int x = (int)Math.Log(n, 2);
     
    int m = 1 << x;
    m = m | m - 1;
    n = n ^ m;
     
    return n;
}
 
// Function to invert the sum
// of set bits in A and B
static void invertSum(int A, int B)
{
     
    // Stores sum of set bits
    int temp = countSetBits(A) +
               countSetBits(B);
                
    Console.WriteLine(invertBits(temp));
}
 
// Driver Code
static void Main()
{
    int A = 5;
    int B = 7;
     
    invertSum(A, B);
}
}
 
// This code is contributed by divyesh072019

<script>
 
// Javascript program for the above approach
 
// Function to count number of
// set bits in integer
function countSetBits(n)
{
     
    // Variable for counting set bits
    var count = 0;
     
    while (n != 0)
    {
        n &= (n - 1);
        count++;
    }
    return count;
}
  
// Function to invert bits of a number
function invertBits(n)
{
     
    // Calculate number of bits of N-1;
    var x = parseInt((Math.log(n) /
                      Math.log(2)));
      
    var m = 1 << x;
    m = m | m - 1;
    n = n ^ m;
      
    return n;
}
  
// Function to invert the sum
// of set bits in A and B
function invertSum(A, B)
{
     
    // Stores sum of set bits
    var temp = countSetBits(A) +
               countSetBits(B);
                 
    document.write(invertBits(temp));
}
   
// Driver Code
var A = 5;
var B = 7;
  
invertSum(A, B);
 
// This code is contributed by Rajput-Ji
 
</script>

2

Complejidad temporal: O(logN)
Espacio auxiliar: O(1)