C++ O(1) solution, no loop or recursion


  • 0
    L

    the trick is in this line int tmp = num & (-num); If there is n trailing zeros in num, then tmp equals 2 ^ n. If num is power of four, it must include only one of 1-bit, so tmp must equals num. Numbers that satisfy this term might also be power of two, that's why we add another term that tmp | 0x55555555) == 0x55555555

    bool isPowerOfFour(int num) {
        if(num <= 0)
            return false;
        int tmp = num & (-num);
        if(tmp == num && (tmp | 0x55555555) == 0x55555555)
        	return true;
        else
        	return false;
    }

Log in to reply
 

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