Sum of bitwise AND of all possible subsets of given set | PHP program to calculate sum of Bit - wise and sum of all subsets of an array ; assuming representation of each element is in 32 bit ; iterating array element ; Counting the set bit of array in ith position ; counting subset which produce sum when particular bit position is set . ; multiplying every position subset with 2 ^ i to count the sum . ; Driver code
< ? php $ BITS = 32 ; function andSum ( $ arr , $ n ) { global $ BITS ; $ ans = 0 ; for ( $ i = 0 ; $ i < $ BITS ; $ i ++ ) { $ countSetBits = 0 ; for ( $ j = 0 ; $ j < $ n ; $ j ++ ) { if ( $ arr [ $ j ] & ( 1 << $ i ) ) $ countSetBits ++ ; } $ subset = ( 1 << $ countSetBits ) - 1 ; $ subset = ( $ subset * ( 1 << $ i ) ) ; $ ans += $ subset ; } return $ ans ; } $ arr = array ( 1 , 2 , 3 ) ; $ size = count ( $ arr ) ; echo andSum ( $ arr , $ size ) ; ? >