Recuento de pares que tienen un tamaño de bit como máximo X y Bitwise O igual a X

Dado un número X , calcule el número de pares posibles (a, b) de modo que bit a bit o de a y b sea igual a X y el número de bits tanto en a como en b sea menor que el número de bits en X.

Ejemplos: 
 

Entrada: X = 6 
Salida: 9 
Explicación: 
Los posibles pares de (a, b) son (4, 6), (6, 4), (6, 6), (6, 2), (4, 2), (6, 0), (2, 6), (2, 4), (0, 6).
Entrada: X = 21 
Salida: 27 
Explicación: 
En total hay 27 pares posibles.

Enfoque: Para resolver el problema mencionado anteriormente, siga los pasos que se detallan a continuación:

• Iterar a través de cada bit del número X dado.
• Si el bit es 1 , entonces de la tabla de verdad de Bitwise O sabemos que hay 3 combinaciones posibles para ese bit dado en el número a y b que es (0, 1), (1, 0), (1, 1) que son 3 formas posibles.
• Si el bit es 0 , entonces de la tabla de verdad de Bitwise O sabemos que solo hay 1 combinación posible para ese bit dado en el número a y b que es (0, 0).
• Entonces nuestra respuesta será 3 ^ (número de bits en X).

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

// C++ implementation to Count number of
// possible pairs of (a, b) such that
// their Bitwise OR gives the value X
 
#include <iostream>
using namespace std;
 
// Function to count the pairs
int count_pairs(int x)
{
    // Initializing answer with 1
    int ans = 1;
 
    // Iterating through bits of x
    while (x > 0) {
 
        // check if bit is 1
        if (x % 2 == 1)
 
            // multiplying ans by 3
            // if bit is 1
            ans = ans * 3;
 
        x = x / 2;
    }
    return ans;
}
 
// Driver code
int main()
{
    int X = 6;
 
    cout << count_pairs(X)
         << endl;
 
    return 0;
}

// Java implementation to count number of
// possible pairs of (a, b) such that
// their Bitwise OR gives the value X
class GFG{
 
// Function to count the pairs
static int count_pairs(int x)
{
     
    // Initializing answer with 1
    int ans = 1;
 
    // Iterating through bits of x
    while (x > 0)
    {
         
        // Check if bit is 1
        if (x % 2 == 1)
 
            // Multiplying ans by 3
            // if bit is 1
            ans = ans * 3;
 
        x = x / 2;
    }
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    int X = 6;
 
    System.out.print(count_pairs(X) + "\n");
}
}
 
// This code is contributed by amal kumar choubey

# Python3 implementation to count number of
# possible pairs of (a, b) such that
# their Bitwise OR gives the value X
 
# Function to count the pairs
def count_pairs(x):
 
    # Initializing answer with 1
    ans = 1;
 
    # Iterating through bits of x
    while (x > 0):
 
        # Check if bit is 1
        if (x % 2 == 1):
 
            # Multiplying ans by 3
            # if bit is 1
            ans = ans * 3;
 
        x = x // 2;
     
    return ans;
 
# Driver code
if __name__ == '__main__':
     
    X = 6;
 
    print(count_pairs(X));
 
# This code is contributed by amal kumar choubey

// C# implementation to count number of
// possible pairs of (a, b) such that
// their Bitwise OR gives the value X
using System;
class GFG{
 
  // Function to count the pairs
  static int count_pairs(int x)
  {
 
    // Initializing answer with 1
    int ans = 1;
 
    // Iterating through bits of x
    while (x > 0)
    {
 
      // Check if bit is 1
      if (x % 2 == 1)
 
        // Multiplying ans by 3
        // if bit is 1
        ans = ans * 3;
 
      x = x / 2;
    }
    return ans;
  }
 
  // Driver code
  public static void Main(String[] args)
  {
    int X = 6;
 
    Console.Write(count_pairs(X) + "\n");
  }
}
 
// This code is contributed by sapnasingh4991

<script>
 
// javascript implementation to count number of
// possible pairs of (a, b) such that
// their Bitwise OR gives the value X   
// Function to count the pairs
    function count_pairs(x) {
 
        // Initializing answer with 1
        var ans = 1;
 
        // Iterating through bits of x
        while (x > 0) {
 
            // Check if bit is 1
            if (x % 2 == 1)
 
                // Multiplying ans by 3
                // if bit is 1
                ans = ans * 3;
 
            x = parseInt(x / 2);
        }
        return ans;
    }
 
    // Driver code
     
        var X = 6;
 
        document.write(count_pairs(X) + "\n");
 
// This code contributed by Rajput-Ji
 
</script>

9

Complejidad del tiempo: O(log(X))