231. Power of Two #

Problem #

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

Example 1:

Input: 1
Output: true 
Explanation: 2^0 = 1

Example 2:

Input: 16
Output: true
Explanation: 2^4 = 16

Example 3:

Input: 218
Output: false

Problem Summary #

Given an integer, write a function to determine whether it is a power of 2.

Solution Ideas #

Determine whether a number is 2 to the power of n.
The simplest idea for this problem is to use a loop, which can pass. But the problem requires determining it without a loop, so knowledge of number theory is needed. This problem uses the same idea as Problem 326.

Code #


package leetcode

// Solution 1: Binary bit manipulation method
func isPowerOfTwo(num int) bool {
	return (num > 0 && ((num & (num - 1)) == 0))
}

// Solution 2: Number theory
func isPowerOfTwo1(num int) bool {
	return num > 0 && (1073741824%num == 0)
}

// Solution 3: Lookup table method
func isPowerOfTwo2(num int) bool {
	allPowerOfTwoMap := map[int]int{1: 1, 2: 2, 4: 4, 8: 8, 16: 16, 32: 32, 64: 64, 128: 128, 256: 256, 512: 512, 1024: 1024, 2048: 2048, 4096: 4096, 8192: 8192, 16384: 16384, 32768: 32768, 65536: 65536, 131072: 131072, 262144: 262144, 524288: 524288, 1048576: 1048576, 2097152: 2097152, 4194304: 4194304, 8388608: 8388608, 16777216: 16777216, 33554432: 33554432, 67108864: 67108864, 134217728: 134217728, 268435456: 268435456, 536870912: 536870912, 1073741824: 1073741824}
	_, ok := allPowerOfTwoMap[num]
	return ok
}

// Solution 4: Loop
func isPowerOfTwo3(num int) bool {
	for num >= 2 {
		if num%2 == 0 {
			num = num / 2
		} else {
			return false
		}
	}
	return num == 1
}