2025年zcy算法入门笔记002-位图

大家好，我是讯享网，很高兴认识大家。

引入：位图是什么？

位图（Bitmap）是一种数据结构，用于表示和处理二进制图像或图形。它的作用是在有限的空间中表示和存储图像或图形的像素信息。每个像素都用一个位或几个位来表示其颜色或其他属性。

应用场景：

图像处理：位图广泛用于图像处理和计算机图形学领域。它可以表示真彩色图像、灰度图像或黑白图像，以及透明度、图层和特定效果等。

图像压缩：位图可以通过压缩算法来减小文件大小。一些常见的位图压缩算法包括JPEG和PNG。压缩后的位图在网络传输和存储方面更具效率。

图像编辑和绘图软件：许多图像编辑和绘图软件使用位图作为内部数据结构。用户可以对位图进行编辑、绘制、调整和处理，以创建或修改图像。

扫描仪和打印机：扫描仪用位图来捕捉图像或文档，并将其转换为数字形式。打印机则使用位图来生成图像或文档的输出。

图形界面（GUI）：在计算机图形用户界面中，位图用于绘制图标、按钮、窗口等界面元素。位图还用于绘制和渲染图形效果，如过渡、阴影和纹理等。

游戏开发：位图在游戏开发中扮演重要角色。它可以表示游戏中的角色、场景、纹理、动画等图像元素。

需要注意的是，位图相对于矢量图形（Vector Graphics）具有一些限制，例如在放大时可能失去清晰度，文件大小可能较大等。因此，在选择使用位图还是矢量图形时，需要根据具体的应用场景和需求进行权衡。

一、前置知识点：左移、右移、无符号右移

<<:左移左边最高位丢弃，右边补0（高位向左移动，低位补零）

若左移时舍弃的高位不包含1，则每左移一位，相当于该数乘以2。

>>:右移最高位是0，左边补0；最高为是1，左边补1 ，即高位补符号位

为非负数时，>> 1和/ 2的结果是一样的

为负数且还是偶数时，>> 1和/ 2的结果是一样的

为负数且还是奇数时，>> 1和/ 2的结果是不一样的

>>>:无符号右移无论最高位是0还是1，左边补0

二、位图的功能和实现

引入：假设有一个集合可以帮我们收集数字，既可以add，也可以去contains。但是存在空间问题：每个整型数字(起码)占4Byte(字节)。若集合中此时只有一个整数，而一个整数有32位(4Byte*8bit)，足以表示0~31之间的数字在集合中有没有。

初始是：0000...00000000 --> 一共32位

把5位置标为1即可以表示集合中有5：0000...00

讯享网

结论：只需要4个字节即32个bit即可表示0~31之间数字是否出现过。

推广：则int[32]-> 可以表示32*32=1024个数。

功能：位图可以做出一个集合，在数字范围(最大值)确定情况下，可使用位图收集数字并判断某个数存不存在。优点就在于它可以极大压缩空间。

实现：

public static class BitMap { private long[] bits; //一个long类型可表示64个数 public BitMap(int max) {//在数字范围确定情况下传入最大值 //(max + 64) >> 6 -> (max + 64) / 64 即一共需要几位存数字 bits = new long[(max + 64) >> 6]; } public void add(int num) { /* 1.首先num/64可以定位到是哪个整数 num >> 6 -> num/64 -->找到第几个整数 2.(num & 63) -> (num % 64) 63即000..，&操作把前面全变成0了，剩下的等同于num%64 -->找到第几位用于描述num 3.why? 因为+ - * / %比位运算>> << & | ^慢多了 4. 1L<<(num & 63) -> 把1移到描述num的位置通过或运算标到位图里 例如170: 170/64=2,170%64=42, 1L<<42然后和000...0000进行或运算来完成num的add操作 */ bits[num >> 6] |= (1L << (num & 63)); } public void delete(int num) { /* 例如删170,先170/64=2再170%64=42,然后到bit[2]中描述num的位置改成0; 不管描述num的位置是0还是1,和0进行&操作都会变成0->等同于删掉 */ bits[num >> 6] &= ~(1L << (num & 63)); } public boolean contains(int num) { //描述num的位置和1进行&操作-> 若是1: 1&1->1 !=0 返回true即存在 return (bits[num >> 6] & (1L << (num & 63))) != 0; } }

讯享网

三、使用位运算实现加法

两数相加思路：

int a = 46; //0

int b = 20; //0010100

1.异或运算也叫无进位相加

0 ^ 0010100 -> 0

2.得到a、b的进位信息:先&再左移1位

0 & 0010100 -> 0000100 -> 0001000

3. a+b=a^b+进位信息

0 + 0001000 = -> 66

代码

讯享网public static int add(int a, int b) { int sum = a; while (b != 0) { sum = a ^ b; //无进位相加的信息 b = (a & b) << 1; //然后计算进位信息 -> b->b'(进位信息) a = sum; //a -> a' 无进位相加信息 } return sum; }

四、使用位运算实现减法

a-b即a+b的相反数

代码

public static int negNum(int n) { return add(~n, 1); } public static int minus(int a, int b) { return add(a, negNum(b)); }

五、使用位运算实现乘法

a=0110

b=0111

则a*b=ans=0110+01100+011000

代码

讯享网public static int multi(int a, int b) { //支持正负 int res = 0; while (b != 0) { if ((b & 1) != 0) { //等于0则不加此数 res = add(res, a); //结果接收a } a <<= 1; //左移右边补0 b >>>= 1; //无符号右移左边补0 } return res; }

六、使用位运算实现除法

小例：正数除以正数

a:0 b:00001100