Suma igual y XOR de tres números

Dado un número entero N . La tarea es contar el número de pares de enteros A y B tales que A + B + N = A ^ B ^ N y A y B son menores que N.
Ejemplos: 
 

Entrada: N = 2 
Salida: 3 
Explicación:- 
Para N = 2 
2 XOR 0 XOR 0 = 2+0+0 
2 XOR 0 XOR 1 = 2+0+1 
2 XOR 0 XOR 2 != 2+0+2 
2 XOR 1 XOR 0 = 2+1+0 
2 XOR 1 XOR 1 != 2+1+1 
2 XOR 1 XOR 2 != 2+1+2 
2 XOR 2 XOR 0 != 2+2+0 
2 XOR 2 XOR 1 != 2+2+1 
2 XOR 2 XOR 2 != 2+2+2
Entonces (0, 0), (0, 1) y (1, 0) son los pares requeridos. Entonces la salida es 3.
Entrada: N = 4 
Salida: 9 
 

Enfoque : 
para hacer que la suma de tres números sea igual a la xor de tres números con uno de los números dados, podemos hacer lo siguiente: 
 

1. Representa el número fijo en forma binaria.
2. Recorre la expansión binaria del número fijo. 
   • Si encuentra un 1, solo hay una condición, es decir, toma los bits binarios de los otros dos números como 0 y 0.
   • Si encuentra un 0, habrá tres condiciones, es decir, puede tener bits binarios como (0, 0), (1, 0) 
     o (0, 1).
3. Los siguientes tripletes de bits nunca se llevarán a cabo, por lo que son válidos.
4. Entonces la respuesta será 3^( número de ceros en representación binaria ) .

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

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Defining ull to unsigned long long int
typedef unsigned long long int ull;
 
// Function to calculate power of 3
ull calculate(int bit_cnt)
{
    ull res = 1;
    while (bit_cnt--) {
        res = res * 3;
    }
 
    return res;
}
 
// Function to return the count of the
// unset bit ( zeros )
int unset_bit_count(ull n)
{
    int count = 0;
    while (n) {
 
        // Check the bit is 0 or not
        if ((n & 1) == 0)
            count++;
        // Right shifting ( dividing by 2 )
        n = n >> 1;
    }
    return count;
}
 
// Driver Code
int main()
{
    ull n;
    n = 2;
 
    int count = unset_bit_count(n);
 
    ull ans = calculate(count);
 
    cout << ans << endl;
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function to calculate power of 3
static long calculate(int bit_cnt)
{
    long res = 1;
    while (bit_cnt-- > 0)
    {
        res = res * 3;
    }
 
    return res;
}
 
// Function to return the count of the
// unset bit ( zeros )
static int unset_bit_count(long n)
{
    int count = 0;
    while (n > 0)
    {
 
        // Check the bit is 0 or not
        if ((n & 1) == 0)
            count++;
             
        // Right shifting ( dividing by 2 )
        n = n >> 1;
    }
    return count;
}
 
// Driver Code
public static void main(String[] args)
{
    long n;
    n = 2;
 
    int count = unset_bit_count(n);
 
    long ans = calculate(count);
 
    System.out.println(ans);
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 implementation of the approach
 
# Function to calculate power of 3
def calculate(bit_cnt):
 
    res = 1;
    while (bit_cnt > 0):
        bit_cnt -= 1;
        res = res * 3;
    return res;
 
# Function to return the count of the
# unset bit ( zeros )
def unset_bit_count(n):
 
    count = 0;
    while (n > 0):
         
        # Check the bit is 0 or not
        if ((n & 1) == 0):
            count += 1;
             
        # Right shifting ( dividing by 2 )
        n = n >> 1;
     
    return count;
 
# Driver Code
if __name__ == '__main__':
 
    n = 2;
 
    count = unset_bit_count(n);
 
    ans = calculate(count);
 
    print(ans);
 
# This code contributed by Rajput-Ji

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to calculate power of 3
static long calculate(int bit_cnt)
{
    long res = 1;
    while (bit_cnt-- > 0)
    {
        res = res * 3;
    }
 
    return res;
}
 
// Function to return the count of the
// unset bit (zeros)
static int unset_bit_count(long n)
{
    int count = 0;
    while (n > 0)
    {
 
        // Check the bit is 0 or not
        if ((n & 1) == 0)
            count++;
             
        // Right shifting ( dividing by 2 )
        n = n >> 1;
    }
    return count;
}
 
// Driver Code
public static void Main(String[] args)
{
    long n;
    n = 2;
 
    int count = unset_bit_count(n);
 
    long ans = calculate(count);
 
    Console.WriteLine(ans);
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript implementation of
// the above approach
 
// Function to calculate power of 3
function calculate(bit_cnt)
{
    let res = 1;
    while (bit_cnt--) {
        res = res * 3;
    }
 
    return res;
}
 
// Function to return the count of the
// unset bit ( zeros )
function unset_bit_count(n)
{
    let count = 0;
    while (n) {
 
        // Check the bit is 0 or not
        if ((n & 1) == 0)
            count++;
        // Right shifting ( dividing by 2 )
        n = n >> 1;
    }
    return count;
}
 
// Driver Code
    let n;
    n = 2;
 
    let count = unset_bit_count(n);
 
    let ans = calculate(count);
 
    document.write(ans);
 
</script>

3

Complejidad de tiempo : O (Número de unset_bits). 
Espacio Auxiliar : O(1).