位图的学习

一，位图介绍

位图（Bitmap）是一种用于存储图像的方式，它通过二维矩阵（由像素组成）来表示图像的每一个细节。每个像素通常对应一个特定的颜色值，位图的每个“位”就代表了图像的一个像素。

位图的基本概念

• 像素（Pixel）：位图图像是由无数个像素组成的，每个像素有一个颜色值。像素是图像中最小的显示单元。
• 颜色深度：位图的颜色深度决定了每个像素可以表示的颜色数。常见的颜色深度有8位、16位、24位、32位等。颜色深度越高，每个像素可以表示的颜色种类就越多，图像就越细腻。
• 分辨率：图像的分辨率表示图像的宽度和高度，以像素为单位。例如，1920x1080的分辨率意味着图像宽度为1920像素，高度为1080像素。
• 文件大小：位图的文件大小通常和图像的分辨率、颜色深度以及压缩方式有关。没有压缩的位图（如BMP文件）通常文件较大。

位图文件格式

常见的位图文件格式有：

1. BMP（Bitmap Image File）：最基础的位图格式，不压缩，文件较大，但图像质量保持完好。
2. PNG（Portable Network Graphics）：无损压缩格式，常用于网页和图形应用，支持透明背景。
3. JPEG（Joint Photographic Experts Group）：有损压缩格式，常用于照片和图像，能够显著减少文件大小，但可能牺牲图像质量。
4. GIF（Graphics Interchange Format）：常用于动画，支持256色的图像，支持透明和动画效果。
5. TIFF（Tagged Image File Format）：用于高质量图像存储，支持无损压缩和多页图像。

位图的优缺点

优点：

• 精度高：由于每个像素单独存储，位图能够表现非常详细的图像细节。
• 简单易用：处理位图的算法通常较为简单，适用于需要精确控制图像像素的应用。

缺点：

• 文件大小大：位图不经过压缩时文件非常大，不适合存储高分辨率的图像。
• 不适合缩放：位图图像在缩放时容易失真，特别是放大时，可能会出现模糊或锯齿状。

位图与矢量图的对比

• 位图：图像由像素构成，适合表现细腻的图像（如照片），不适合缩放和改变分辨率。
• 矢量图：图像由路径、点和线构成，适合用于插图和图形设计，放大或缩小时不会失真。

位图的应用

位图广泛应用于：

• 数字摄影：大多数数字相机和手机拍摄的照片都是位图格式。
• 网页设计：许多网页图像和图标使用PNG、JPEG等位图格式。
• 图像编辑：例如Photoshop等图像编辑软件，处理的通常是位图图像。
• 图形显示：例如显示屏、打印机等设备的图像输出通常是位图形式。

总结

位图是一种通过像素矩阵来表达图像的方式，适合存储高质量的图像，广泛应用于数字图像处理、网页设计、摄影等领域。它的文件大小较大，不适合于图像的频繁缩放，而矢量图则在这方面表现得更好。

二，使用位图实现哈希表

1，原理

因为1个int类型含有4个字节，有32个bit，使用每个bit位上0和1的状态来表示该数字是否加入表中，但这就要求哈希表是只能存储连续数字。

2，补充

1）怎么向上取整

已知计算机里只有向下取整，如：2 / 3 = 0；4 / 3 = 1；6 / 3 = 2；

但向下取整是 2 / 3 = 1；3 / 3 = 1；如果想通过a / b + 1来实现是不可能的，因为如果a = b的话就不对了。

所以采用（a + b - 1）/ b ，因为如果a 除 b 后还有余数，b - 1可以让余数升到下一位从而结果加1，如果没有余数也不会影响结果。

三，对数器验证

1，如何随机生成0到1的小数

2，错误展示

else
{
    bitset.flip_num(number);
    if (hashset.find(number) != hashset.end())
    {
        hashset.insert(number);
    }
}

这里if操作错误，找到后应该删去，同时缺少没有找到后插入该数字。

3，代码

#include<iostream>
#include<random>
#include<unordered_set>

using namespace std;
random_device rd;
default_random_engine gen(rd());
uniform_real_distribution<double> probability(0.0, 1.0);

struct Bitset
{
public:
    int* bitset;
    int len;

    Bitset(int x) : len((x + 31) / 32)
    {
        bitset = new int[len];
    }

    void add_num(int n)
    {
        bitset[n / 32] |= 1 << (n % 32);
    }

    void remove_num(int n)
    {
        bitset[n / 32] &= ~(1 << (n % 32));
    }

    void flip_num(int n)
    {
        bitset[n / 32] ^= 1 << (n % 32);
    }
    //翻转的意思是原来数组有就变为没有，如果原来没有现在变为有。

    bool find_num(int n)
    {
        return ( (bitset[n / 32] >> (n % 32)) & 1 ) == 1;
    }

};

void Test_machine(Bitset& bitset,int test_times,int len)
{
    uniform_int_distribution<int> dis(0, len - 1);
    unordered_set<int> hashset;
    double chance;
    int number;

    cout << "测试开始" << endl;

    bitset.add_num(5);
    hashset.insert(5);
    if (bitset.find_num(5) != (hashset.find(5) != hashset.end()))
    {
        cout << "出错了" << endl;
    }

    cout << "调用阶段开始" << endl;
    for (int i = 0; i < test_times; i++)
    {
        chance = probability(gen);
        number = dis(gen);
        if (chance < 0.33)
        {
            bitset.add_num(number);
            hashset.insert(number);
        }
        else if (chance < 0.66)
        {
            bitset.remove_num(number);
            hashset.erase(number);
        }
        else
        {
            bitset.flip_num(number);
            if (hashset.find(number) != hashset.end())
            {
                hashset.erase(number);
            }
            else
            {
                hashset.insert(number);
            }

        }
    }
    cout << "调用阶段结束" << endl;

    cout << "验证阶段开始" << endl;
    for (int i = 0; i < len; i++)
    {
        if (bitset.find_num(i) != (hashset.find(i) != hashset.end()))
        {
            cout<<"出错了"<<endl;
        }
    }

    cout << "验证阶段结束" << endl << "测试结束" << endl;
}

int main()
{
    Bitset bitset(20);
    Test_machine(bitset, 10, 20);
    return 0;
}

四，补充题

题目

代码

#include<iostream>

struct Bitset
{
public:
    int* bitset;
    int size;
    int zeros, ones;
    bool reverse = false;

    Bitset(int n) :size(n) 
    {
        zeros = size;
        ones = 0;
        bitset = new int[(size + 31) / 32];
    }

    void fix(int i)
    {
        int index = i / 32;
        int bit = i % 32;
        if (!reverse)
            //在bitset未被翻转时，reverse是false。
            //此时0代表不存在，1代表存在。
        {
            if ((bitset[index] & 1 << bit) == 0)
            {
                zeros--;
                ones++;
                bitset[index] ^= 1 << bit;
            }
        }
        else
            //如果bitset被翻转，则reverse是true
            //此时0代表存在，1代表不存在。
            //使用reverse是为了翻转时不必遍历每一位。
        {
            if ((bitset[index] & 1 << bit) != 0)
            {
                zeros--;
                ones++;
                bitset[index] ^= 1 << bit;
            }
        }
    }

    void flip()
    {
        reverse = !reverse;
        int temp;
        temp = zeros;
        zeros = ones;
        ones = temp;
    }

    bool all()
    {
        return ones == size;
    }

    bool one()
    {
        return ones > 0;
    }

    int count_ones()
    {
        return ones;
    }
};