Recuento de bits activados y desactivados coincidentes en números enteros dados.

Para dos enteros X e Y , la tarea es encontrar el número de bits que son iguales en su representación binaria sin considerar ningún cero inicial después del bit establecido más a la izquierda del número mayor en forma binaria.

Ejemplos:

Entrada : X = 10, Y = 6
Salida : 2
Explicación : La representación binaria de 10 es 10 10 y 6 es 01 10 . Entonces, el número de bits iguales es 2.

Entrada : X = 3, Y = 16
Salida : 2

Acercarse: 

Intuición:

Calcule el bit menos significativo (LSB) usando (i % 2), donde i es cualquier número entero y compruebe si el bit menos significativo (LSB) del número entero dado X, Y es el mismo o no. Si es lo mismo, incremente la respuesta y desplace a la derecha ambos enteros en 1 para verificar que el LSB sea el mismo o no para el siguiente bit.

Algoritmo:

• Siga realizando los siguientes pasos hasta que X o Y no sean 0 .
  • Calcule el LSB de los enteros X e Y dados por X % 2 e Y % 2 y verifique si ambos son iguales o no.
    • Si es igual, entonces incrementa la respuesta.
  • Desplazar a la derecha los dos enteros dados por 1

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number of same bit between
// two integer.
int solve(int X, int Y)
{
    int ans = 0;
 
    while (X != 0 || Y != 0) {
        // Check if both LSB are same or not
        if (X % 2 == Y % 2)
            ans++;
 
        // Right shift the both given integer by 1
        X >>= 1;
        Y >>= 1;
    }
 
    return ans;
}
 
// Driver code
int main()
{
    int X = 10, Y = 6;
 
    // Find number of same bits
    cout << solve(X, Y);
 
    return 0;
}

// Java implementation of the approach
import java.io.*;
 
class GFG
{
 
  // Function to find the number of same bit between
  // two integer.
  public static int solve(int X, int Y)
  {
    int ans = 0;
 
    while (X != 0 || Y != 0)
    {
       
      // Check if both LSB are same or not
      if (X % 2 == Y % 2)
        ans++;
 
      // Right shift the both given integer by 1
      X >>= 1;
      Y >>= 1;
    }
 
    return ans;
  }
 
  public static void main(String[] args)
  {
    int X = 10, Y = 6;
 
    // Find number of same bits
    System.out.print(solve(X, Y));
  }
}
 
// This code is contributed by Rohit Pradhan

# Python3 implementation of the approach
 
# Function to find the number of same bit between
# two integer.
def solve(X, Y):
    ans = 0
    while (X != 0 or Y != 0):
       
        # Check if both LSB are same or not
        if X % 2 == Y % 2:
            ans += 1
 
        # Right shift the both given integer by 1
        X >>= 1
        Y >>= 1
 
    return ans
 
# Driver code
X = 10
Y = 6
 
# function call
print(solve(X, Y))
 
# This code is contributed by phasing17

// C# implementation of the approach
using System;
 
public class GFG{
 
  // Function to find the number of same bit between
  // two integer.
  public static int solve(int X, int Y)
  {
    int ans = 0;
 
    while (X != 0 || Y != 0)
    {
 
      // Check if both LSB are same or not
      if (X % 2 == Y % 2)
        ans++;
 
      // Right shift the both given integer by 1
      X >>= 1;
      Y >>= 1;
    }
 
    return ans;
  }
 
  static public void Main (){
    int X = 10, Y = 6;
 
    // Find number of same bits
    Console.Write(solve(X, Y));
  }
}
 
// This code is contributed by hrithikgarg03188.

<script>
// JS implementation of the approach
 
// Function to find the number of same bit between
// two integer.
function solve(X, Y)
{
    var ans = 0;
 
    while (X != 0 || Y != 0)
    {
     
        // Check if both LSB are same or not
        if (X % 2 == Y % 2)
            ans++;
 
        // Right shift the both given integer by 1
        X >>= 1;
        Y >>= 1;
    }
 
    return ans;
}
 
// Driver code
var X = 10;
var Y = 6;
 
// Find number of same bits
document.write(solve(X, Y));
 
// This code is contributed by phasing17
</script>

2

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

Otro enfoque: contar bits no establecidos en XOR de los números

El XOR de dos bits es 1/activado si no coinciden (es decir, uno está desactivado y el otro activado), y el XOR de dos bits es 0/desactivado si coinciden (es decir, ambos están activados o desactivados).

Por lo tanto, la cantidad total de bits coincidentes en dos números es igual a la cantidad de bits no coincidentes en su XOR, o la diferencia entre los bits totales y los bits no coincidentes en su XOR.

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
  
// compute number of matching bits
int countUnmatchedBits(int A, int B)
{
    //calculate XOR
    int XOR = (A ^ B);
    //count total number of bits using log2(XOR) + 1
    int totalBits = (int)log2(XOR) + 1;
    // Check for 1's in the binary form using
    // Brian Kerninghan's Algorithm
    int setCount = 0;
    while (XOR) {
        XOR = XOR & (XOR - 1);
        setCount++;
    }
    //the number of unset bits is equal to
    //the difference between total bits
    //and the set bits count
    return totalBits - setCount;
}
  
// Driver code
int main()
{
    int A = 10, B = 6;
    int result = countUnmatchedBits(A, B);
    cout << "Number of matching bits : " << result;
  
    return 0;
}
 
//this code is contributed by phasing17

import java.util.*;
import java.io.*;
 
// Java program for the above approach
class GFG{
 
    // compute number of matching bits
    static int countUnmatchedBits(int A, int B)
    {
        //calculate XOR
        int XOR = (A ^ B);
        //count total number of bits using log2(XOR) + 1
        int totalBits = (int)Math.floor(Math.log(XOR)/Math.log(2)) + 1;
        // Check for 1's in the binary form using
        // Brian Kerninghan's Algorithm
        int setCount = 0;
        while (XOR > 0) {
            XOR = XOR & (XOR - 1);
            setCount++;
        }
        //the number of unset bits is equal to
        //the difference between total bits
        //and the set bits count
        return totalBits - setCount;
    }
 
    // Driver code
    public static void main(String args[])
    {
        int A = 10, B = 6;
        int result = countUnmatchedBits(A, B);
        System.out.println("Number of matching bits : " + result);
    }
}
 
// This code is contributed by subhamgoyal2014.

# Python program for the above approach
import math
# compute number of matching bits
 
 
def countUnmatchedBits(A, B):
    # calculate XOR
    XOR = (A ^ B)
    # count total number of bits using log2(XOR) + 1
    totalBits = int(math.floor(math.log(XOR) / math.log(2)) + 1)
    # Check for 1's in the binary form using Brian Kerninghan's Algorithm
    setCount = 0
    while XOR > 0:
        XOR = XOR & (XOR - 1)
        setCount += 1
    # the number of unset bits is equal to the difference between
    # total bits and the set bits count
    return totalBits - setCount
 
 
A, B = 10, 6
result = countUnmatchedBits(A, B)
print 'Number of matching bits : ', result
# This code is contributed by KaaL-EL.

// C# program for the above approach
 
using System;
 
class GFG {
 
    // compute number of matching bits
    static int countUnmatchedBits(int A, int B)
    {
        // calculate XOR
        int XOR = (A ^ B);
        // count total number of bits using log2(XOR) + 1
        int totalBits
            = (int)Math.Floor(Math.Log(XOR) / Math.Log(2))
              + 1;
        // Check for 1's in the binary form using
        // Brian Kerninghan's Algorithm
        int setCount = 0;
        while (XOR > 0) {
            XOR = XOR & (XOR - 1);
            setCount++;
        }
        // the number of unset bits is equal to
        // the difference between total bits
        // and the set bits count
        return totalBits - setCount;
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        int A = 10, B = 6;
        // Function call
        int result = countUnmatchedBits(A, B);
        Console.WriteLine("Number of matching bits : "
                          + result);
    }
}
 
// This code is contributed by phasing17

// JavaScript implementation of the approach
  
// compute number of matching bits
function countUnmatchedBits(A, B)
{
    // calculate XOR
    let XOR = (A ^ B);
     
    // count total number of bits using log2(XOR) + 1
    let totalBits = Math.floor(Math.log2(XOR)) + 1;
     
    // Check for 1's in the binary form using
    // Brian Kerninghan's Algorithm
    let setCount = 0;
    while (XOR) {
        XOR = XOR & (XOR - 1);
        setCount++;
    }
     
    // the number of unset bits is equal to
    // the difference between total bits
    // and the set bits count
    return totalBits - setCount;
}
  
// Driver code
let A = 10;
let B = 6;
 
// Function Call
let result = countUnmatchedBits(A, B);
console.log("Number of matching bits :", result);
 
// this code is contributed by phasing17

Number of matching bits : 2

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)