力扣-779. 第K个语法符号 && 位运算

题目描述

思路及实现

191.位1的个数

作弊流写法

除了学会一个新方法之外什么都学不到的写法（

class Solution:
    def hammingWeight(self, n: int) -> int:
        return n.bit_count()

循环检查

检查题目所给定的数中1的个数即可，每次检查1位，i从0取到31，每次都用1 << i（1,10,100…）和n作与运算，如果n的二进制表示的当前位是1那么就是1，是0就是0。

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

位运算优化

其实优化的关键就是一个式子：n & (n−1)。大家可以举个例子试一下一个数和它自身减一的数做与运算会发生什么，没错，其运算结果恰为把n的二进制位中的最低位的1变为0之后的结果。
也就是说，我们只需要不断计算这个式子，n最后会变成0，而每次计算，n就少一个1，相应的结果（1的个数）计数加一就好。

class Solution:
    def hammingWeight(self, n: int) -> int:
        ret = 0
        while n:
            n &= n - 1
            ret += 1
        return ret

奇偶校验

额，说实话，翻来覆去看不懂代码，好不容易找到了个有解释的网站，转载一波explanation吧。
先上网站：Count bits set in parallel a.k.a. Population Count
附赠网址：Bit Twiddling Hacks

countBits (line 1 − line 13):
Counting all set bits of an integer was part of many mainframe CPU’s assembler language but somehow
x86 CPUs ignored it for decades. Apparently Intel introduced the POPCNT opcode in its Core i7 design.

Meanwhile, the population count has to be implemented by other means.
The main observations lies in the fact that you can subdivide any bitblock into smaller chunks,
compute their population count and add all intermediate results.

First, the code counts the bits of two adjacent bits:

0b and 0b → 00b
0b and 1b → 01b
1b and 0b → 01b
1b and 1b → 10b

The whole algorithm modifies the input in order to generate the output, that means it works in-place.
Line 4 performs the 2-bit count at once based on the observation:

00b → unchanged, still 00b
01b → unchanged, still 01b
10b → must be converted to 01b
11b → must be converted to 10b

Whenever the higher bit of each 2-bit group is set, subtracting 01b gives the desired outcome.
Looks like branching … but as it turns out, the subtraction can be done always: just subtract the higher bit !
If it is 0, the result remains unchanged, if it is 1, then we get the right numbers, too.
The shift x >> 1 and the following mask of all odd bits (0x55 is 01010101b):

00b → shifted: ?0b → masked: 00b → subtraction: 00b − 00b → 00b
01b → shifted: ?0b → masked: 00b → subtraction: 01b − 00b → 01b
10b → shifted: ?1b → masked: 01b → subtraction: 10b − 01b → 01b
11b → shifted: ?1b → masked: 01b → subtraction: 11b − 01b → 10b

Now the 2-bit count is done. As you can see, there are just three possible decimal results: 0, 1 or 2.

Then, two adjacent 2-bit groups are joined to 4-bit groups (line 6):

00b and 00b → 0000b
00b and 01b → 0001b
00b and 10b → 0010b
01b and 00b → 0001b
01b and 01b → 0010b
01b and 10b → 0011b
10b and 00b → 0010b
10b and 01b → 0011b
10b and 10b → 0100b

This time, the 2-bit groups are masked and shifted to match and then simply added. No overflow is possible.

00b + 00b → 0000b
00b + 01b → 0001b
00b + 10b → 0010b
01b + 00b → 0001b
01b + 01b → 0010b
01b + 10b → 0011b
10b + 00b → 0010b
10b + 01b → 0011b
10b + 10b → 0100b

The same procedure is done for all 4-bit groups yielding the bit counts for each of the four bytes (line 8)
in their lower four bits. That means, each byte contains its bit count, however, the upper four bits may
contain junk and are masked out (line 10).

Multiplying by 0x01010101 has an interesting property if we name the four bytes A, B, C, D:

A, B, C, D → A+B+C+D, B+C+D, C+D, D

Obviously the highest byte is what we are looking for. The right shift (line 12) returns just it.

顺便附上代码里边十六进制数对应的二进制数。
0x55555555 = 01010101 01010101 01010101 01010101
0x33333333 = 00110011 00110011 00110011 00110011
0x0F0F0F0F = 00001111 00001111 00001111 00001111
0x00FF00FF = 00000000 11111111 00000000 11111111
0x0000FFFF = 00000000 00000000 11111111 11111111
0x01010101 = 00000001 00000001 00000001 00000001
0x0000003f = 00000000 00000000 00000000 00111111

class Solution:
    def hammingWeight(self, n: int) -> int:
        n = n - ((n >> 1) & 0x55555555)
        n = (n & 0x33333333) + ((n >> 2) & 0x33333333)
        n = (n + (n >> 4)) & 0x0f0f0f0f
        n = n + (n >> 8)
        n = n + (n >> 16)
        return n & 0x3f

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
		// count bits of each 2-bit chunk
        n = n - ((n >>> 1) & 0x55555555);
		// count bits of each 4-bit chunk
        n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
		// count bits of each 8-bit chunk:	x  = x + (x >> 4);
		// mask out junk:	x &= 0xF0F0F0F;
		// add all four 8-bit chunks:	(x * 0x01010101) >> 24;
        return ((n + (n >>> 4) & 0xF0F0F0F) * 0x1010101) >>> 24;
    }
}

建议还是用第三种循环法，好理解且复杂度不高。

779.第K个语法符号

找规律，然后递归求解

根据题目所给规则，我们先构造出前几个数：
0
0 1
01 10
0110 1001
01101001 10010110
可以看到每一行的后半部分的数都是前半部分数的翻转，即：0变1，1变0。那么对k，如果k在后半部分，我们可以尝试求解上一行前半部分对应位置的数，然后将其翻转；如果k在前半部分，那么直接求上一行对应位置的数即可。

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        if k == 1:
            return 0
        if k > (1 << (n - 2)):  # 1 << (n - 2) = 上一行长度的一半
            return 1 ^ self.kthGrammar(n - 1, k - (1 << (n - 2)))  # k大于当前行长度一半，那么要返回的数就等于镜像位置的数字取反
        return self.kthGrammar(n - 1, k)  # k小于等于当前行长度一半，那么要返回的数就等于上一行当前位置的数字

构造完全二叉树，然后递归求解

这个是看了别人的思路，发现好厉害，居然还有这种操作，还是我思维不行呜呜呜
上链接：大佬的二叉树解题思路
下边是按照思路写的代码

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        if n == 1:  # 第一层，直接返回0
            return 0
        num = self.kthGrammar(n - 1, (k + 1) // 2)  # 找一下父节点是0还是1
        if num == 0:  # 父节点为0
            return 0 if k % 2 else 1  # 如果k是奇数，那就是左子节点；如果k是偶数，那就是右子节点
        else:  # 父节点为1
            return 1 if k % 2 else 0

---

希望本文章能够帮到您~