位运算

异或运算:相同为0，不同为1
0^0 = 0
1^1 = 0
1^0 = 1
0^1 = 1

涉及到python中 内置函数：

异或：x^y
转换成二进制：bin()
计算字符串中某个字符的个数：str.count('1')

自己实现内置函数的功能

  1. 计算二进制中1的个数(时间复杂度为O(k),k大多数为32)

    count = 0
    while t:
        count += 1
        t = t & (t-1)
    print(count)

  2. 下降到

LeetCode中相关的题目：

  • 461.汉明距离 ：异或、统计1的个数
  • 136.只出现一次的数字：异或、相同的可以抵消，唯一不同的就可以留下
  • 338.比特位计数：原来方法（O(k*N)）动态规划+(最高有效位、最低有效位、最低设置位)（O(N)）
  • 169.多数元素:可以使用，但是最优方法最好使用摩尔投票法
  • 78.子集: 可以使用二进制作为标记数组，来确定当前的位置是否会被选中。时间复杂度为O(n*2^n),空间复杂度为O(n)。也可以使用回溯法