Sum of Bitwise | C ++ program to find sum of Bitwise - OR of all submatrices ; Function to find prefix - count for each row from right to left ; Function to create a boolean matrix set_bit which stores a 1 aTM at an index ( R , C ) if ith bit of arr [ R ] [ C ] is set . ; array to store prefix count of zeros from right to left for boolean array ; variable to store the count of submatrices with OR value 0 ; For each index of a column we will try to determine the number of sub - matrices starting from that index and has all 1 s ; stack to store elements and the count of the numbers they popped First part of pair will be the value of inserted element . Second part will be the count of the number of elements pushed before with a greater value ; variable to store the number of submatrices with all 0 s ; Function to find sum of Bitwise - OR of all submatrices ; matrix to store the status of ith bit of each element of matrix arr ; Driver Code
#include <iostream> NEW_LINE #include <stack> NEW_LINE using namespace std ; #define n  3 NEW_LINE void findPrefixCount ( int p_arr [ ] [ n ] , bool set_bit [ ] [ n ] ) { for ( int i = 0 ; i < n ; i ++ ) { for ( int j = n - 1 ; j >= 0 ; j -- ) { if ( set_bit [ i ] [ j ] ) continue ; if ( j != n - 1 ) p_arr [ i ] [ j ] += p_arr [ i ] [ j + 1 ] ; p_arr [ i ] [ j ] += ( int ) ( ! set_bit [ i ] [ j ] ) ; } } } int matrixOrValueOne ( bool set_bit [ ] [ n ] ) { int p_arr [ n ] [ n ] = { 0 } ; findPrefixCount ( p_arr , set_bit ) ; int count_zero_submatrices = 0 ; for ( int j = 0 ; j < n ; j ++ ) { int i = n - 1 ; stack < pair < int , int > > q ; int to_sum = 0 ; while ( i >= 0 ) { int c = 0 ; while ( q . size ( ) != 0 and q . top ( ) . first > p_arr [ i ] [ j ] ) { to_sum -= ( q . top ( ) . second + 1 ) * ( q . top ( ) . first - p_arr [ i ] [ j ] ) ; c += q . top ( ) . second + 1 ; q . pop ( ) ; } to_sum += p_arr [ i ] [ j ] ; count_zero_submatrices += to_sum ; q . push ( { p_arr [ i ] [ j ] , c } ) ; i -- ; } } return ( n * ( n + 1 ) * n * ( n + 1 ) ) / 4 - count_zero_submatrices ; } int sumOrMatrix ( int arr [ ] [ n ] ) { int sum = 0 ; int mul = 1 ; for ( int i = 0 ; i < 30 ; i ++ ) { bool set_bit [ n ] [ n ] ; for ( int R = 0 ; R < n ; R ++ ) for ( int C = 0 ; C < n ; C ++ ) set_bit [ R ] [ C ] = ( ( arr [ R ] [ C ] & ( 1 << i ) ) != 0 ) ; sum += ( mul * matrixOrValueOne ( set_bit ) ) ; mul *= 2 ; } return sum ; } int main ( ) { int arr [ ] [ n ] = { { 9 , 7 , 4 } , { 8 , 9 , 2 } , { 11 , 11 , 5 } } ; cout << sumOrMatrix ( arr ) ; return 0 ; }