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