Occurrences of a pattern in binary representation of a number | Function to return the count of occurrence of pat in binary representation of n ; To store decimal value of the pattern ; To store a number that has all ones in its binary representation and length of ones equal to length of the pattern ; Find values of pattern_int and all_ones ; If the pattern occurs in the last digits of n ; Right shift n by 1 bit ; Driver code
def countPattern ( n , pat ) : NEW_LINE INDENT pattern_int = 0 NEW_LINE power_two = 1 NEW_LINE all_ones = 0 NEW_LINE i = len ( pat ) - 1 NEW_LINE while ( i >= 0 ) : NEW_LINE INDENT current_bit = ord ( pat [ i ] ) - ord ( '0' ) NEW_LINE pattern_int += ( power_two * current_bit ) NEW_LINE all_ones = all_ones + power_two NEW_LINE power_two = power_two * 2 NEW_LINE i -= 1 NEW_LINE DEDENT count = 0 NEW_LINE while ( n != 0 and n >= pattern_int ) : NEW_LINE INDENT if ( ( n & all_ones ) == pattern_int ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT n = n >> 1 NEW_LINE DEDENT return count NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 500 NEW_LINE pat = "10" NEW_LINE print ( countPattern ( n , pat ) ) NEW_LINE DEDENT