LeetCode-算法-位运算-第13天

二进制学习

231. 2 的幂

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。 如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

示例 1：
输入：n = 1
输出：true
解释：20 = 1
示例 2：
输入：n = 16
输出：true
解释：24 = 16
示例 3：
输入：n = 3
输出：false
示例 4：
输入：n = 4
输出：true
示例 5：
输入：n = 5
输出：false

Python

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n>0 and(n&(n-1))==0

思路：二进制同一位只有两种形式0或1。很显然当n=2的二进制是10,n=4的是100。而n-1的则是1=01,3=011。规律很明显，因为2的次幂只有最左侧才会使1其余全是0，而n-1的则除了首位（这里规定和n的二进制同位数）为0其余全部为1,因此n&(n-1)必定为0。所以以此来决定是否为2的次幂。

GO

func isPowerOfTwo(n int) bool {
    return n>0 &&(n&(-n)==n)
}

思路：目前采用的二进制方法为补码，正整数的二进制补码是源码，而负整数的二进制补码是其反码+1（这只是好记忆，其原理并不是反码+1）,反码又是原码各，除符号位以外，每一位取反（源码规定 正数符号为0，负数为1）。现在举例：4，4的二进制为0100（最左面为符号位）,-4的原码为1100，反码为1011，补码为1100。 同理：3的原码0011，-3的原码为1011，反码为1100，补码为1101。 我们可以看出，当是2的次幂时，其-n的补码会出现除符号位全部相同，因此在取&时结果仍等于n，利用此规律我们可以得出 (n&(-n)==n)

191. 位1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。

示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

Python

class Solution:
    def hammingWeight(self, n: int) -> int:
        return sum([1 for i in range(32) if n&(1<<i)])

思路：二进制1的个数，我们可以从最右侧开始来进行，例如当n=5，二进制位110，从最右侧开始与&1操作，则110&001=0，则最右侧无1，之后右侧第二位与10取&，则110&010=1，则证明此处有1，记录下来，同理可得出全部。

GO

func hammingWeight(num uint32) int {
    ones:=0
    for ; num > 0; num &= num - 1 {
        ones++
    }
    return ones
}

思路：n&(n-1)除了可以检验是否2的次幂，还可以用作检验1的个数。例如7二进制111，6二进制位110，5的二进制位101，4则是100，3二进制位011。可以看出n-1比n最低少1。7&6=110，6&5=101，5&4=100，4&3=0可以看出每次n&n-1都会将距离右侧最近的1变为0，直到全部为0则停止。因此可以利用此规律，每次循环都可与n-1进行取&,个数+1，直到n为0停止。