第13天位运算

231.2的幂

1、按位与注意特判，如果是0先return False。其余情况都是 return not(n & (n-1)) 。

将2的幂次方写成二进制形式后，很容易就会发现有一个特点：二进制中只有一个1，并且1后面跟了n个0；因此问题可以转化为判断1后面是否跟了n个0就可以了。

如果将这个数减去1后会发现，仅有的那个1会变为0，而原来的那n个0会变为1；因此将原来的数与去减去1后的数字进行与运算后会发现值为零。
而负数在计算机中以补码形式表示，最高位始终为1，所以按位与后不可能为0，所以也满足这个方法。

class Solution(object):
    def isPowerOfTwo(self, n):
        """
        :type n: int
        :rtype: bool
        """
        if n == 0:
            return False
        return not(n & (n-1))

# 还有一种判断方法： (n&-n) == n

?2、常规判断。while n%2为0，n除以2，最后看n是否为1，是则为True，否则为False。

class Solution(object):
    def isPowerOfTwo(self, n):
        """
        :type n: int
        :rtype: bool
        """
        if n <= 0:
            return False
        if n==1:
            return True
        while n%2 == 0: 
            n = n // 2
        if n == 1:
            return True
        else:
            return False

191.位1的个数

思路：

1、位运算（1）不断右移跟1做与运算（2）n=n&(n-1)?每次都可以把最低位的1变成0

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        ans = 0
        while(n):
            ans += n&1
            n >>= 1
        return ans

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        ans = 0
        while(n):
            ans += 1
            n = n & (n-1)
        return ans

2、转为字符串

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        s = str(bin(n))
        ans = 0
        for i in s:
            if i == '1':
                ans+=1
        return ans