LeetCode#231 Power of Two

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

class Solution:
    # @param {integer} n
    # @return {boolean}
    def isPowerOfTwo(self, n):
        if n<1:
            return False
        while n!=0:
            if n==1:
                return True
            b=n%2
            if b==1:
                return False
            n=n/2

上の余剰演算はビット演算で代用でき、より効率的です.
Power of 2の数のバイナリ形式を見てみましょう.
1-->0b0001
2-->0b0010
4-->0b0100
8-->0b1000
これらの数のバイナリ形式には、1つの数字'1'しかないことがわかります.それで、

1 def isPowerOfTwo(n):
2         if n<1:
3             return False
4         n=((n & 0xAAAAAAAA)>>1)+(n & 0x55555555)
5         n=((n & 0xCCCCCCCC)>>2)+(n & 0x33333333)
6         n=((n & 0xF0F0F0F0)>>4)+(n & 0x0F0F0F0F)
7         n=((n & 0xFF00FF00)>>8)+(n & 0x00FF00FF)
8         n=((n & 0xFFFF0000)>>16)+(n & 0x0000FFFF)
9         return n==1

再観察:
1-->0b0001     1-1=0-->0b0000　　0b0001 & 0b0000=0
2-->0b0010　　2-1=1-->0b0001　　0b0010 & 0b0001=0
4-->0b0100　　4-1=3-->0b0011　　0b0100 & 0b0011=0
8-->0b1000　　8-1=7-->0b0111　　0b1000 & 0b0111=0
7-->0b0111　　7-1=6-->0b0110　　0b0111 & 0b0110=0b0110 !=0
...
So we have:

1 def isPowerOfTwo(n):
2         return False if n<1 else 0==((n-1)&n)