Sum of Bitwise AND of sum of pairs and their Bitwise AND from a given array | C ++ program for the above approach ; Function to find the sum of Bitwise AND of sum of pairs and their Bitwise AND from a given array ; Stores the total sum ; Check if jth bit is set ; Stores the right shifted element by ( i + 1 ) ; Update the value of X ; Push in vector vec ; Sort the vector in ascending order ; Traverse the vector vec ; Stores the value 2 ^ ( i + 1 ) - 2 ^ ( i ) - vec [ j ] ; Stores count of numbers whose value > Y ; Update the ans ; Return the ans ; Driver Code
#include <bits/stdc++.h> NEW_LINE #define M  1000000007 NEW_LINE using namespace std ; void findSum ( int A [ ] , int N ) { long long ans = 0 ; for ( int i = 0 ; i < 30 ; i ++ ) { vector < long long > vec ; for ( int j = 0 ; j < N ; j ++ ) { if ( ( A [ j ] >> i ) & 1 ) { long long X = ( A [ j ] >> ( i + 1 ) ) ; X = X * ( 1 << ( i + 1 ) ) ; X %= M ; vec . push_back ( A [ j ] - X ) ; } } sort ( vec . begin ( ) , vec . end ( ) ) ; for ( int j = 0 ; j < vec . size ( ) ; j ++ ) { int Y = ( 1 << ( i + 1 ) ) + ( 1 << i ) - vec [ j ] ; int idx = lower_bound ( vec . begin ( ) + j + 1 , vec . end ( ) , Y ) - vec . begin ( ) ; ans += ( vec . size ( ) - idx ) * 1ll * ( 1 << i ) ; ans %= M ; } } cout << ans % M << endl ; } int main ( ) { int arr [ ] = { 1 , 3 , 3 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; findSum ( arr , N ) ; return 0 ; }