Check if bitwise AND of any subset is power of two | Check for power of 2 or not ; Check if there exist a subset whose bitwise AND is power of 2. ; if there is only one element in the set . ; Finding a number with all bit sets . ; check all the positions at which the bit is set . ; include all those elements whose i - th bit is set ; check for the set contains elements make a power of 2 or not ; Driver Code
< ? php function isPowerOf2 ( $ num ) { return ( $ num && ! ( $ num & ( $ num - 1 ) ) ) ; } function checkSubsequence ( $ arr , $ n ) { $ NUM_BITS = 32 ; if ( $ n == 1 ) return isPowerOf2 ( $ arr [ 0 ] ) ; $ total = 0 ; for ( $ i = 0 ; $ i < $ NUM_BITS ; $ i ++ ) $ total = $ total | ( 1 << $ i ) ; for ( $ i = 0 ; $ i < $ NUM_BITS ; $ i ++ ) { $ ans = $ total ; for ( $ j = 0 ; $ j < $ n ; $ j ++ ) { if ( $ arr [ $ j ] & ( 1 << $ i ) ) $ ans = $ ans & $ arr [ $ j ] ; } if ( isPowerOf2 ( $ ans ) ) return true ; } return false ; } $ arr = array ( 12 , 13 , 7 ) ; $ n = sizeof ( $ arr ) / sizeof ( $ arr [ 0 ] ) ; if ( checkSubsequence ( $ arr , $ n ) ) echo " YES " ; else echo " NO " ; ? >