Suma de diferencias de bits entre todos los pares

Dada una array de n enteros, encuentre la suma de las diferencias de bits en todos los pares que se pueden formar a partir de los elementos de la array. La diferencia de bits de un par (x, y) es el recuento de diferentes bits en las mismas posiciones en representaciones binarias de x e y. 

Por ejemplo, la diferencia de bits para 2 y 7 es 2. La representación binaria de 2 es 010 y 7 es 111 (el primer y el último bit difieren en dos números). 

C++

// C++ program to compute sum of pairwise bit differences
#include <bits/stdc++.h>
using namespace std;
 
int sum_bit_diff(vector<int> a)
{
    int n = a.size();
    int ans = 0;
 
    for (int i = 0; i < n - 1; i++) {
        int count = 0;
 
        for (int j = i; j < n; j++) {
            // Bitwise and of pair (a[i], a[j])
            int x = a[i] & a[j];
            // Bitwise or of pair (a[i], a[j])
            int y = a[i] | a[j];
 
            bitset<32> b1(x);
            bitset<32> b2(y);
 
            // to count set bits in and of two numbers
            int r1 = b1.count();
            // to count set bits in or of two numbers
            int r2 = b2.count();
 
            // Absolute differences at individual bit positions of two
            // numbers is contributed by pair (a[i], a[j]) in count
            count = abs(r1 - r2);
 
            // each pair adds twice of contributed count
            // as both (a, b) and (b, a) are considered
            // two separate pairs.
            ans = ans + (2 * count);
        }
    }
    return ans;
}
 
int main()
{
 
    vector<int> nums{ 10, 5 };
    int ans = sum_bit_diff(nums);
 
    cout << ans;
}

Java

/*package whatever //do not write package name here */
 
import java.io.*;
 
class GFG {
   
    static int sumBitDiff(int[] arr){
        int diff = 0;                                //hold the ans
           
          for(int i=0; i<arr.length; i++){
            for(int j=i; j<arr.length; j++){
               
              //XOR toggles the bits and will form a number that will have
              //set bits at the places where the numbers bits differ
              //eg: 010 ^ 111 = 101...diff of bits = count of 1's = 2
               
                 int xor = arr[i]^arr[j];
                  int count = countSetBits(xor);        //Integer.bitCount() can also be used
                   
                  //when i == j (same numbers) the xor would be 0,
                  //thus our ans will remain unaffected as (2*0 = 0)
                  diff += 2*count;
            }
        }
       
          return diff;
    }
   
    //Kernighan algo
      static int countSetBits(int n){
        int count = 0;            // `count` stores the total bits set in `n`
  
        while (n != 0) {
            n = n & (n - 1);    // clear the least significant bit set
            count++;
        }
  
        return count;
    }
   
    public static void main (String[] args) {
        int[] arr = {5,10};
          int ans  = sumBitDiff(arr);
        System.out.println(ans);
    }
}

Python3

# Python3 program for the above approach
def sumBitDiff(arr):
    diff = 0    #hold the ans
       
    for i in range(len(arr)):
        for j in range(i, len(arr)):
               
        # XOR toggles the bits and will form a number that will have
        # set bits at the places where the numbers bits differ
        # eg: 010 ^ 111 = 101...diff of bits = count of 1's = 2          
            xor = arr[i]^arr[j]
            count = countSetBits(xor)        #Integer.bitCount() can also be used
                   
            # when i == j (same numbers) the xor would be 0,
            # thus our ans will remain unaffected as (2*0 = 0)
            diff += (2*count)
       
    return diff
     
# Kernighan algo
def countSetBits(n):
    count = 0            # `count` stores the total bits set in `n`
  
    while (n != 0) :
        n = n & (n - 1)    # clear the least significant bit set
        count += 1
         
    return count
     
# Driver code
if __name__ == "__main__":
     
    arr = [5,10]
    ans  = sumBitDiff(arr)
    print(ans)
 
    # This code is contributed by sanjoy_62.

C#

/*package whatever //do not write package name here */
 
using System;
 
public class GFG {
   
    static int sumBitDiff(int[] arr){
        int diff = 0;                                //hold the ans
           
          for(int i=0; i<arr.Length; i++){
            for(int j=i; j<arr.Length; j++){
               
              //XOR toggles the bits and will form a number that will have
              //set bits at the places where the numbers bits differ
              //eg: 010 ^ 111 = 101...diff of bits = count of 1's = 2
               
                 int xor = arr[i]^arr[j];
                  int count = countSetBits(xor);        //int.bitCount() can also be used
                   
                  //when i == j (same numbers) the xor would be 0,
                  //thus our ans will remain unaffected as (2*0 = 0)
                  diff += 2*count;
            }
        }
       
          return diff;
    }
   
    //Kernighan algo
      static int countSetBits(int n){
        int count = 0;            // `count` stores the total bits set in `n`
  
        while (n != 0) {
            n = n & (n - 1);    // clear the least significant bit set
            count++;
        }
  
        return count;
    }
   
    public static void Main(String[] args) {
        int[] arr = {5,10};
          int ans  = sumBitDiff(arr);
        Console.WriteLine(ans);
    }
}
 
// This code contributed by umadevi9616

Javascript

<script>
 
// javascript program for above approach
    function sumBitDiff(arr)
    {
        let diff = 0;                               
        // hold the ans
           
          for(let i = 0; i < arr.length; i++){
            for(let j = i; j < arr.length; j++){
               
              // XOR toggles the bits and will form a number that will have
              // set bits at the places where the numbers bits differ
              // eg: 010 ^ 111 = 101...diff of bits = count of 1's = 2
               
                 let xor = arr[i]^arr[j];
                  let count = countSetBits(xor);       
                  // Integer.bitCount() can also be used
                   
                  // when i == j (same numbers) the xor would be 0,
                  // thus our ans will remain unaffected as (2*0 = 0)
                  diff += 2*count;
            }
        }
       
          return diff;
    }
   
    // Kernighan algo
      function countSetBits(n){
        let count = 0;            // `count` stores the total bits set in `n`
  
        while (n != 0) {
            n = n & (n - 1);    // clear the least significant bit set
            count++;
        }
  
        return count;
    }
 
 
// Driver code
    let arr = [5,10];
    let ans  = sumBitDiff(arr);
    document.write(ans);
     
    // This code is contributed by splevel62.
</script>

C++

// C++ program to compute sum of pairwise bit differences
#include <bits/stdc++.h>
using namespace std;
 
int sumBitDifferences(int arr[], int n)
{
    int ans = 0; // Initialize result
    // traverse over all bits
    for (int i = 0; i < 32; i++) {
        // count number of elements with i'th bit set
        int count = 0;
        for (int j = 0; j < n; j++)
            if ((arr[j] & (1 << i)))
                count++;
        // Add "count * (n - count) * 2" to the answer
        ans += (count * (n - count) * 2);
    }
    return ans;
}
 
// Driver program
int main()
{
    int arr[] = { 1, 3, 5 };
    int n = sizeof arr / sizeof arr[0];
    cout << sumBitDifferences(arr, n) << endl;
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta (kriSania804)

C

// C program to compute sum of pairwise bit differences
#include <stdio.h>
 
int sumBitDifferences(int arr[], int n)
{
    int ans = 0; // Initialize result
    // traverse over all bits
    for (int i = 0; i < 32; i++) {
        // count number of elements with i'th bit set
        int count = 0;
        for (int j = 0; j < n; j++)
            if ((arr[j] & (1 << i)))
                count++;
        // Add "count * (n - count) * 2" to the answer
        ans += (count * (n - count) * 2);
    }
    return ans;
}
 
// Driver program
int main()
{
    int arr[] = { 1, 3, 5 };
    int n = sizeof arr / sizeof arr[0];
    printf("%d\n", sumBitDifferences(arr, n));
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta (kriSania804)

Java

// Java program to compute sum of pairwise
// bit differences
 
import java.io.*;
class GFG {
    static int sumBitDifferences(int arr[], int n)
    {
        int ans = 0; // Initialize result
        // traverse over all bits
        for (int i = 0; i < 32; i++) {
            // count number of elements with i'th bit set
            int count = 0;
            for (int j = 0; j < n; j++)
                if ((arr[j] & (1 << i)) != 0)
                    count++;
            // Add "count * (n - count) * 2"
            // to the answer...(n - count = unset bit count)
            ans += (count * (n - count) * 2);
        }
        return ans;
    }
 
    // Driver program
    public static void main(String args[])
    {
        int arr[] = { 1, 3, 5 };
        int n = arr.length;
        System.out.println(sumBitDifferences(arr, n));
    }
}
 
// This code is contributed by Sania Kumari Gupta (kriSania804)

Python3

# Python program to compute sum of pairwise bit differences
 
def sumBitDifferences(arr, n):
 
    ans = 0  # Initialize result
 
    # traverse over all bits
    for i in range(0, 32):
     
        # count number of elements with i'th bit set
        count = 0
        for j in range(0, n):
            if ( (arr[j] & (1 << i)) ):
                count+= 1
 
        # Add "count * (n - count) * 2" to the answer
        ans += (count * (n - count) * 2);
     
    return ans
 
# Driver program
arr = [1, 3, 5]
n = len(arr )
print(sumBitDifferences(arr, n))
 
# This code is contributed by
# Smitha Dinesh Semwal   

C#

// C# program to compute sum
// of pairwise bit differences
using System;
 
class GFG {
    static int sumBitDifferences(int[] arr,
                                 int n)
    {
        int ans = 0; // Initialize result
 
        // traverse over all bits
        for (int i = 0; i < 32; i++) {
 
            // count number of elements
            // with i'th bit set
            int count = 0;
            for (int j = 0; j < n; j++)
                if ((arr[j] & (1 << i)) != 0)
                    count++;
 
            // Add "count * (n - count) * 2"
            // to the answer
            ans += (count * (n - count) * 2);
        }
 
        return ans;
    }
    // Driver Code
    public static void Main()
    {
 
        int[] arr = { 1, 3, 5 };
        int n = arr.Length;
 
        Console.Write(sumBitDifferences(arr, n));
    }
}
 
// This code is contributed by ajit

PHP

<?php
// PHP program to compute sum
// of pairwise bit differences
 
function sumBitDifferences($arr, $n)
{
    // Initialize result
    $ans = 0;
 
    // traverse over all bits
    for ($i = 0; $i < 32; $i++)
    {
        // count number of elements
        // with i'th bit set
        $count = 0;
        for ($j = 0; $j < $n; $j++)
            if (($arr[$j] & (1 << $i)))
                $count++;
 
        // Add "count * (n - count) * 2"
        // to the answer
        $ans += ($count * ($n -
                           $count) * 2);
    }
 
    return $ans;
}
 
// Driver Code
$arr = array(1, 3, 5);
$n = sizeof($arr);
echo sumBitDifferences($arr, $n), "\n";
 
// This code is contributed by m_kit
?>

Javascript

<script>
 
// Javascript program to compute sum
// of pairwise bit differences
function sumBitDifferences(arr, n)
{
     
    // Initialize result
    let ans = 0;
 
    // Traverse over all bits
    for(let i = 0; i < 32; i++)
    {
         
        // count number of elements with i'th bit set
        let count = 0;
        for(let j = 0; j < n; j++)
            if ((arr[j] & (1 << i)))
                count++;
 
        // Add "count * (n - count) * 2" to the answer
        ans += (count * (n - count) * 2);
    }
    return ans;
}
 
// Driver code
let arr = [ 1, 3, 5 ];
let n = arr.length;
 
document.write(sumBitDifferences(arr, n));
 
// This code is contributed by subhammahato348
 
</script>

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *