^ > ^ > ^ > return the time complexity is (log )where is the word size note that we can combine caching with word-level operationse by doing lookup in the xor-based approach once we get to bits the actual runtimes depend on the input datae the refinement of the brute-force algorithm is very fast on sparse inputs howeverfor random inputsthe refinement of the brute-force is roughly faster than the brute-force algorithm the table-based approach is four times faster stilland using associativity reduces run time by another factor of two variantwrite expressions that use bitwise operatorsequality checksand boolean operators to do the following in ( time right propagate the rightmost set bit in xe turns ( ) to ( ) compute modulo power of twoe returns for mod test if is power of evaluates to true for false for all other values