1-line C++ solution without <<, >>, ~, for, while (with explanation and example)


  • 0

    Key Observation: The complement number of a positive int x is given by mask ^ x, where mask is the bit mask:

    • mask = 2(int) log2 x+1 - 1.

    E.g., bit mask for x = 5 = (101) is mask = 23-1 = (111) = 7.

        int findComplement(int x) {      
          return ((int)pow(2,(int)log2(x)+1)-1)^x;
        }
    

    Or you can use ">>" and "<<" to construct the bit mask for x:

        int findComplement(int x) {
          int n = (int)log2(x)+1;
          return ~(~0 >> n << n)^x;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.