[LeetCode] 231. Power of Two

轉自LeetCode

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

<Solution>
判斷 int 是否為 2 的次方數，想法如下

• 如果是 2 的次方數，那麼此 int 的 binary 表示裡面，只會有一個 bit 為 1。運用 Number of 1 Bits 的概念即可

code如下

	class Solution {
	public:
	bool isPowerOfTwo(int n) {
	int cnt = 0;
	while(n > 0) {
	cnt += (n & 1);
	n >>= 1;
	}
	return (cnt == 1);
	}
	};

view raw isIntPowerOfTwo_1.cpp hosted with ❤ by GitHub

還有另外一種想法

• 如果是 2 的次方數，MSB 會是 1，其餘會是 0。假設 n 是 2 的次方數，那麼 n & (n-1) 一定會是 0

code 如下

	class Solution {
	public:
	bool isPowerOfTwo(int n) {
	return n > 0 && !(n & (n-1));
	}
	};

view raw isIntPowerOfTwo_2.cpp hosted with ❤ by GitHub