【刷题笔记】位运算：从人脑到电子脑的演变

2024-03-15 23:12:36

【刷题笔记】位运算: 从人脑到电子脑的演变

理解位运算对于非计算机科学专业的选手需要一个思考的过程

然而对于计算机科学的选手来说，从理解简单的位运算到复杂的复合位运算

仍然是一个过程

这里就实用主义的角度出发，总结一下做到的题目用到的复合位运算

2的幂

n&(n-1) 这个操作可以将一个二进制数 n n n 最右边的1归零

>>> x=0b100101010100
>>> bin(x&(x-1))
'0b100101010000'

在二进制数中，任何2的幂都是

首位数字为1，其余为0

因此，我们只需要打掉一次末尾的1，如果结果不是0，则一定不是2的幂

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n>0&&(n&(n-1))==0;
    }
};

位1的个数

位1的个数实际上就是汉明重量

它在通信、密码学、计算机科学等领域都有相当重要的地位

本题与上题实际上可以用同一招解决

看代码

递归

class Solution {
public:
    int hammingWeight(uint32_t n) {
        return n ? 1 + hammingWeight(n & (n - 1)) : 0;
    }
};

迭代

class Solution {
public:
    int hammingWeight(uint32_t n) {
      int count =0;
        while(n) {
          count++;
          n = n&(n-1);
      }
        return count;
    }
};

uint32_t 表示C语言中的32位整型

只要每次循环判断整数是否为0，

我们就不必遍历全部32位就可以得出结论

颠倒二进制位

n&1：取得二进制数 n n n 的最后一位

具体的思路，即 将最后一位放到第一位

以此类推

我们开辟一个新的二进制数res=0

每次左移一位res 放入此时n的最后一位

n 右移一位

看代码：

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t  res=0;
        for(int i=0; i<32; i++) {
                res = (res<<1) + (n&1);
                n = n >> 1;
        }
        return res;
    }
};

（经典）N皇后II

回溯算法已经做过，这里不在赘述

我们用位运算来加速这个过程

苍白的文字和苍白的代码无法讲清楚，我就结合代码与注释讲解

前提是读者已经理解了回溯方法

class Solution:
    def totalNQueens(self, n: int) -> int:
        if n < 1: return []
        self.count = 0
        self.DFS(n,0,0,0,0)
        return self.count
    def DFS(self, n, row, cols, pie, na):
        # recursion terminator
        if row >= n:
            self.count +=1
            return
         '''
        假设当前 n = 4,
        1层：
        row, col , pie, na = 0,0,0,0
        bits = 0b1111
        while循环：(判断bits是否全为0）
            p = 1 , 最低1位在第1位
            bits = bits & (bit -1)
            bits = 0b1110, 在最低位试探一个皇后
        ----drill down----
        2层：
        row = 1, col = 0b0001, pie = 0b0010, na = 0b0000
        bits = (~(0011)) & (1111)  # num&mask
             = 1100
        得到此时的可用位置
        while循环：
            p=0100
            bit = 1000 # 打掉p位的Q
        ----drill down----
        以此类推
        ...
        
        '''
        bits = (~(cols | pie | na)) & ((1 << n)-1 ) # 得到本层的空位
    while bits:
        p = bits & -bits # 取得最低位的1的位置
        bits = bits & (bit - 1) # 在最低的1位放上皇后，即p位
        # 下探一层，往可行的位置放上皇后
        self.DFS(n, row + 1, cols | p, (pie | p) << 1, (na | p)>>1)

如果你想要学习验证位运算的结果

推荐打开你的shell

然后python开一个CLI 交互命令行

把位运算全部打一遍

应用：Bloom Filter 布隆过滤器

为何在位运算的地方讲布隆过滤器？
请继续往下看：

哈希表可以依照KV存取一个对象

布隆过滤器的效用，只是检测某元素是否存在
布隆过滤器具有极高的查询效率与空间效率
布隆过滤器的缺点：存在一定的误判别率

不存在（0）布隆过滤器的元素一定不存在，存在的（1）不一定存在

工作过程

插入元素
1. 对要插入的元素做多次hash（原元素），hash函数的输出值为布隆数组下标
2. 我们将相应下标的布隆数组元素置为1
查询元素
1. 对要查询的元素多次hash，看每一位的下标是否为1
  1. 出现0，一定不存在这个元素
  2. 全1，可能存在这个元素（通过hash设计降低误判率）

解答疑问

为何在位运算的地方讲布隆过滤器？
因为布隆过滤器的实现会涉及大量的位运算思想，
由于我们利用01比特来表示某个对象的存在，就会节省大量空间
为什么？
比如java 的char类型占16bit,
我们可以把布隆过滤器设置成char数组，每种char都是唯一一个01表示

应用

布隆过滤器高效且存在误判的特性，使得其能够很好地作为系统外部的缓存来使用

这样可以做到fail fast，快速判断不存在，就不需要进入db低效查询了

码农公寓