皮皮网

1.位向量工作原理
2.size_t的介绍
3.谁能编一个把PCM（自然码）转成为二进制的源码C++程序
4.BitMap原理与实现

位向量工作原理

       位向量，也叫位图，源码是源码一个我们经常可以用到的数据结构，在使用小空间来处理大量数据方面有着得天独厚的源码优势；位向量的定义就是一串由0.1组成的序列。

       Java中对位向量的源码java计算素数源码实现类时Java.util.BitSet;C++标准库中也有相应的实现，原理都是源码aide源码运行一样的； BitSet源码也很简单，很容易看懂 ，源码如果读者在对位向量有一定的源码了解后，可以通过读源码来了解BitSet的源码具体实现。

       一个bit上有两个值，源码正好可以用来判断某些是源码非状态的场景，在针对大数据场景下判断存在性，源码BitSet是源码python deque源码相比其他数据结构比如HashMap更好的选择，在Java中，源码位向量是源码用一个叫words的long型数组实现的，一个long型变量有位，可以保存个数字；比如我们有[2,varnish源码安装8,6,,]这5个数要保存，一般存储需要 5*4 = 字节的存储空间。但是如果我们使用Java.util.BitSet进行存储则可以节省很多的空间只需要一个long型数字就够了。BitSet只面向数字只面向数字使用，对于string类型的多站源码数据，可以通过hashcode值来使用BitSet。

       由于，1 << , 1<<, 1<< 这些数字的结果都为1，BitSet内部，long[]数组的大小由BitSet接收的最大数字决定，这个数组将数字分段表示[0,],[,],[,]...。即long[0]用来存储[0,]这个范围的数字的“存在性”，long用来存储[,]，依次轮推，这样就避免了位运算导致的冲突。原理如下：

       |------------|----------|----------|----------|----------| |

       Java的BitSet每次申请空间，申请位，即一个long型变量所占的位数；

size_t的介绍

       size_t 类型定义在cstddef头文件中，该文件是C标准库的头文件stddef.h的C++版。它是一个与机器相关的unsigned类型，其大小足以保证存储内存中对象的大小。例如：bitset的size操作返回bitset对象中二进制位中的个数，返回值类型是size_t。例如：在用下标访问元素时，vector使用vector::size_type作为下标类型，而数组下标的正确类型则是size_t。vector使用的下标实际也是size_t，源码是typedef size_t size_type。

谁能编一个把PCM（自然码）转成为二进制的C++程序

       自然码是带权值的二进制码 权值从左至右分别为8 4 2 1

       程序检测数据：输入自然码 输出二进制码

       希望对你有帮助

       ==================================================================

       #include<iostream>

       #include<string>

       using namespace std;

       int main()

       {

        //接收输入的4位自然码字符串 转化为整形

        //temp为每位的权值8 4 2 1

        //result[]为要输出的二进制结果的数组

        int c[4]={ 0},SUM=0,temp[4]={ 8,4,2,1},result[];

       for(int i=0;i<4;++i)

        {

        c[i]=(int)getchar()-;

        SUM+=c[i]*temp[i]; //利用权值得到自然码所表示的进制的值SUM

       }

       //再将十进制数SUM 转化为二进制

        int k=0;

       while(SUM>0)

        {

        result[k]=SUM%2;

        SUM=(SUM-result[k])/2; //每次得到的商

        ++k;

        }

        for(int t=k-1;t>=0;--t)

        cout<<result[t];

        return 0;

       }

BitMap原理与实现

        比较经典的问题是： 在只能够使用2G的内存中，如何完成以下操作：

        ①：对亿个不重复的整数进行排序。

        ②：找出亿个数字中重复的数字。

        无论是排序还是找重复的数字都需要将这亿个数字加入到内存中在去进行操作，很明显，题目给出的2G内存限制说明了在这样的场景下是不能够将所有数都加入到内存中的

        * 4/（* * ） = 3.G

        那么这时候就需要用到 BitMap结构了

        bitMap使用一个bit为0/1作为map的value来标记一个数字是否存在,而map的key值正是这个数字本身。

        相比于一般的数据结构需要用4个byte去存储数值本身，相当于是节省了 4*8：1 = 倍的内存空间

        bitMap不一定要用bit数组,可以使用 int,long等等的基本数据类型实现，因为其实质都是在bit位上存数据，用哪种类型只是决定了最终实现出来的BitMap的内置数组中单个元素存放数据的多少

            例如：java中的BitSet使用Long数组

        BitMap的实现当然少不了位运算，先来明确几个常见位运算，这是实现BitMap的基础：

        set(bitIndex): 添加操作

            1 .确定该数处于数组中的哪个元素的位上

             int wordIndex = bitIndex >> 5;

        因为我用的是int[]实现，所以这里右移 5 位（2^5 = ）

            2 .确定相对于该元素中的位置偏移

             int bitPosition = bitIndex & ((1 << 5) - 1);

        这里相当于是 bitIndex % （1<<5）的取模运算，因为当取模运算的除数是2的次幂，所以可以使用以下的位运算来计算，提升效率（对比HashMap的容量为什么总是2的幂次方的问题，HashMap求下标时也是使用 hash&(n-1)）

        tips: 位运算的优先级是低于+,-等等的，所以要加上括号,防止发生不可描述的错误

            3 .将该位置1

             bits[wordIndex] |= 1 << bitPosition;

        相当于是将指定位置处的bit值置1，其他位置保持不变，也就是将以这个bitIndex为key的位置为1

        tips: 这里是参考了网上的各位大佬的文章,取余 + 按位或，又对比了下BitSet的源码：

             words[wordIndex] |= (1L << bitIndex);

        没有取余操作，直接|，这两个一样吗？答案当然是一样的

        举个栗子：

             1 << == 1<<     

             1L << ==1L<<

        即对于int和long型数据，直接左移其位数相当于是附带了对其的取模操作

        总结：使用Bit-map的思想，我们可以将存储空间进行压缩，而且可以对数字进行快速排序、去重和查询的操作。

        Bloom Fliter是Bit-map思想的一种扩展，它可以在允许低错误率的场景下，大大地进行空间压缩，是一种拿错误率换取空间的数据结构

        当一个元素加入布隆过滤器中的时候，会进行哪些操作：

        当我们需要判断一个元素是否存在于布隆过滤器的时候，会进行哪些操作：

        然后，一定会出现这样一种情况：不同的字符串可能哈希出来的位置相同（可以适当增加位数组大小或者调整我们的哈希函数来降低概率）,因此：布隆过滤器可能会存在误判的情况

        总结来说就是： 布隆过滤器说某个元素存在，小概率会误判。布隆过滤器说某个元素不在，那么这个元素一定不在。

        Bloom Filter的应用: 常用于解决缓存穿透等场景。