ReZero's Utopia.

Power of Two

Word count: 141Reading time: 1 min
2019/07/30 Share

Given an integer, write a function to determine if it is a power of two.

1
2
3
bool isPowerOfTwo(int n) {
return n > 0 && !(n&(n-1));
}

Explain: 100 & 011 = 0

Try think about power of 4: return num > 0 && (num & (num - 1)) == 0 && (num - 1) % 3 == 0;

(4^n - 1) % 3 == 0
proof:
(1) 4^n - 1 = (2^n + 1) * (2^n - 1)
(2) among any 3 consecutive numbers, there must be one that is a multiple of 3
among (2^n-1), (2^n), (2^n+1), one of them must be a multiple of 3, and (2^n) cannot be the one, therefore either (2^n-1) or (2^n+1) must be a multiple of 3, and 4^n-1 must be a multiple of 3 as well.

CATALOG