水一篇
32位
c++写的,长得比较丑陋
进入sub-401164函数
V7的数据可以得到
unsigned char ida_chars[] = { 0x62, 0x6C, 0x7F, 0x76, 0x7A, 0x7B, 0x66, 0x73, 0x76, 0x50, 0x52, 0x7D, 0x40, 0x54, 0x55, 0x79, 0x40, 0x49, 0x47, 0x4D, 0x74, 0x19, 0x7B, 0x6A, 0x42, 0x0A, 0x4F, 0x52, 0x7D, 0x69, 0x4F, 0x53, 0x0C, 0x64, 0x10, 0x0F, 0x1E, 0x4A, 0x67, 0x03, 0x7C, 0x67, 0x02, 0x6A, 0x31, 0x67, 0x61, 0x37, 0x7A, 0x62, 0x2C, 0x2C, 0x0F, 0x6E, 0x17, 0x00, 0x16, 0x0F, 0x16, 0x0A, 0x6D, 0x62, 0x73, 0x25, 0x39, 0x76, 0x2E, 0x1C, 0x63, 0x78, 0x2B, 0x74, 0x32, 0x16, 0x20, 0x22, 0x44, 0x19, 0x00, 0x00, 0x00, 0x00, 0x00, 0x4E }; 大概意思应该是异或那里相等
目录
1 -> 位图
1.1 -> 位图的概念
1.2 -> 位图的应用
2 -> 布隆过滤器
2.1 -> 布隆过滤器的提出 2.2 -> 布隆过滤器的概念
2.3 -> 布隆过滤器的插入
2.4 -> 布隆过滤器的查找
2.5 -> 布隆过滤器的删除
2.6 -> 布隆过滤器的优点
2.7 -> 布隆过滤器的缺陷
1 -> 位图 1.1 -> 位图的概念 位图的概念:所谓位图,就是用每一位来存放某种状态,适用于海量数据,数据无重复的场景。通常是用来判断某个数据是否存在的。
下面是一道面试题:
给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。
遍历,时间复杂度O(N)。排序(O(NlogN)),利用二分查找:logN。位图解决:数据是否在给定的整形数据中,结果是在或者不在,刚好是两种状态,那么可以使用一个二进制比特位来代表数据是否存在的信息,如果二进制比特位为1,代表存在,为0代表不存在。比如: #define _CRT_SECURE_NO_WARNINGS 1 #include <iostream> #include <vector> using namespace std; class bitset { public: bitset(size_t bitCount) : _bit((bitCount >> 5) + 1), _bitCount(bitCount) {} // 将which比特位置1 void set(size_t which) { if (which > _bitCount) return; size_t index = (which >> 5); size_t pos = which % 32; _bit[index] |= (1 << pos); } // 将which比特位置0 void reset(size_t which) { if (which > _bitCount) return; size_t index = (which >> 5); size_t pos = which % 32; _bit[index] &= ~(1 << pos); } // 检测位图中which是否为1 bool test(size_t which) { if (which > _bitCount) return false; size_t index = (which >> 5); size_t pos = which % 32; return _bit[index] & (1 << pos); } // 获取位图中比特位的总个数 size_t size()const { return _bitCount; } // 位图中比特为1的个数 size_t Count()const { int bitCnttable[256] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 }; size_t size = _bit.