Given an integer n, return true if it is a power of two. For example, 1, 2, 4, 8 and 16 are powers of two.
DSA Animator › DSA Revision › Bit Manipulation › Power of Two
Remember: a power of two has exactly one set bit. n greater than 0 and n AND n minus 1 equal to 0. The video solves Power of Two (LeetCode 231, Easy) with the Single Set Bit pattern from the Bit Manipulation topic, and you can replay every step in the interactive Power of Two animation.
Given an integer n, return true if it is a power of two. For example, 1, 2, 4, 8 and 16 are powers of two.
16 is a power of two, so the answer is true. 12 is not, so the answer is false.
You can keep dividing by 2 while the number is even, and check if you reach 1. That takes O of log n steps.
In binary, a power of two has exactly one 1 bit. Removing the lowest set bit, with n AND n minus 1, leaves 0 only in that case. Also require n to be positive, because 0 and negative numbers are not powers of two.
16 is 10000 in binary, with a single 1 bit. 15 is 01111. 10000 AND 01111 is 0, so 16 is a power of two. 12 is 1100, and 11 is 1011. 1100 AND 1011 is 1000, which is not 0, so 12 is not a power of two.
In code, return false if n is at most 0. Otherwise return whether n AND n minus 1 equals 0. It's O of 1 time.
Remember: a power of two has exactly one set bit. n greater than 0 and n AND n minus 1 equal to 0.