Contar números cuya diferencia con N es igual a XOR con N

Dado un número N. La tarea es contar todos los valores posibles de x tales que n x sea igual a (Nx), donde  denota la operación XOR bit a bit.
Ejemplos: 
 

Input: N = 3
Output: 4
The all possible values of x are respectively 0, 1, 2, 3.

Input: N = 6
Output: 4
The all possible values of x are respectively 0, 2, 4, 6.

Enfoque: el valor XOR de dos bits será 1 si ambos bits tienen signo opuesto y 0 cuando ambos bits son iguales. Entonces, sobre la base de la propiedad de XOR, podemos decir que n  x siempre es mayor o igual que nx. La única condición cuando su valor es igual a nx es que los bits de x formen un subconjunto de bits de n. Porque si en la i-ésima posición, tanto x como n tienen bits establecidos, luego de xor el valor disminuirá, y el valor disminuido será  , donde i es una posición basada en 0. 
Entonces, la respuesta es el recuento total de subconjuntos de bits del número n  , donde k es el recuento de bits establecidos en n.
A continuación se muestra la implementación del enfoque anterior: 
 

#include <bits/stdc++.h>
using namespace std;
 
// function to Count all values of x
void count_values(int n)
{
    // Count set bits in n
    // by using stl function
    int set_bits = __builtin_popcount(n);
 
    // count all subset of set bits
    cout << pow(2, set_bits) << "\n";
}
 
// Driver code
int main()
{
 
    int n = 27;
    count_values(n);
 
    return 0;
}

import java.util.*;
 
class Solution
{
//count number of set bits
static int __builtin_popcount(int n)
{
    //count variable
    int count=0;
     
    while(n>0)
    {
        //if the bit is 1
        if(n%2==1)
        count++;
         
        n=n/2;
    }
    return count;
}
     
// function to Count all values of x
static void count_values(int n)
{
    // Count set bits in n
    // by using stl function
    int set_bits = __builtin_popcount(n);
   
    // count all subset of set bits
    System.out.println((int)Math.pow(2, set_bits));
}
   
// Driver code
public static void main(String args[])
{
   
    int n = 27;
    count_values(n);
   
 
}
}
 
// This code is contributed
// by Arnab Kundu

# Python3 program to implement
# above approach
 
# from math import pow method
from math import pow
 
# count number of set bits
def __builtin_popcount(n) :
 
    # count variable
    count = 0
 
    while n > 0 :
 
        # if the bit is 1
        if n % 2 == 1 :
            count += 1
 
        n = n//2
         
    return count
 
 
# function to Count all values of x
def count_values(n) :
 
    set_bits = __builtin_popcount(n)
 
    # count all subset of set bits
    print(int(pow(2, set_bits)))
 
 
# Driver code
if __name__ == "__main__" :
 
    n = 27
    count_values(n)
 
# This code is contributed by
# ANKITRAI1

using System;
class GFG
{
// count number of set bits
static int __builtin_popcount(int n)
{
    // count variable
    int count = 0;
     
    while(n > 0)
    {
        //if the bit is 1
        if(n % 2 == 1)
        count++;
         
        n = n / 2;
    }
    return count;
}
     
// function to Count all values of x
static void count_values(int n)
{
    // Count set bits in n
    // by using stl function
    int set_bits = __builtin_popcount(n);
     
    // count all subset of set bits
    Console.Write((int)Math.Pow(2, set_bits));
}
     
// Driver code
public static void Main()
{
    int n = 27;
    count_values(n);
}
}
 
// This code is contributed by Smitha

<?php
// count number of set bits
function __builtin_popcount($n)
{
    // count variable
    $count = 0;
     
    while($n > 0)
    {
        //if the bit is 1
        if($n % 2 == 1)
            $count++;
         
        $n = $n / 2;
    }
    return $count;
}
     
// function to Count all values of x
function count_values($n)
{
    // Count set bits in n
    // by using stl function
    $set_bits = __builtin_popcount($n);
 
    // count all subset of set bits
    echo (int)pow(2, $set_bits);
}
 
// Driver code
$n = 27;
count_values($n);
 
// This code is contributed
// by Akanksha Rai(Abby_akku)
?>

<script>
 
// count number of set bits
function __builtin_popcount(n)
{
    // count variable
    let count = 0;
     
    while(n > 0)
    {
        //if the bit is 1
        if(n % 2 == 1)
        count++;
         
        n = parseInt(n / 2);
    }
    return count;
}
 
// function to Count all values of x
function count_values(n)
{
    // Count set bits in n
    // by using stl function
    let set_bits = __builtin_popcount(n);
 
    // count all subset of set bits
    document.write(Math.pow(2, set_bits) + "<br>");
}
 
// Driver code
 
    let n = 27;
    count_values(n);
 
</script>

16

Complejidad de tiempo: O(k), donde k es el número de bits establecidos en N.