您的位置:首页 > 新闻 > 资讯 > 北京推广优化公司_动漫制作专业简历_渠道推广有哪些方式_一个完整的营销策划方案范文

北京推广优化公司_动漫制作专业简历_渠道推广有哪些方式_一个完整的营销策划方案范文

2025/1/12 7:52:51 来源:https://blog.csdn.net/2202_75924820/article/details/143209994  浏览:    关键词:北京推广优化公司_动漫制作专业简历_渠道推广有哪些方式_一个完整的营销策划方案范文
北京推广优化公司_动漫制作专业简历_渠道推广有哪些方式_一个完整的营销策划方案范文

#1024程序员节 | 征文#

位图概念

位图(bitmap),又称位数组或位向量,是一种数据结构。它利用连续的位(bit)来高效地表示一组布尔值(即0和1)。在位图中,每一位都对应一个可能的元素或状态,通过将该位设置为1或0来表示该元素是否存在或某个状态是否激活。

适用于海量数据,数据无重复的场景。通常是用来判断某个数据存不存在的。

面试题:

给40亿个不重复的无符号整数,未排过序。给一个无符号整数,如何快速判断这个数是否在这40亿个数中?

给出以下方法:

  • 遍历O(N)。
  • 排序O(N log_2 N)+二分查找O(log_2 N)。
  • set O(log_2 N)、unordered_set O(1)。

以上方法都有一个问题,数据量太大,放不到内存中。40亿个无符号整数,约占用16G内存

位图解决思路:

将数据使用直接定址法映射到数组相应的位置。时间复杂度O(1)。

数组要开多大的空间呢?

开数据范围大小的空间,才能满足所有的数据都能映射到相应的位置。

无符号整数的取值范围为0~4294967295(2^32-1)。所以要开2^32个空间。

开2^32个整型大小的空间(约16G)吗?空间还是不够。数据是否在给定的整型数据中,结果是在或不在,正好是两种状态,使用标志位来表示数据的状态即可,每一位都对应一个元素的状态,此时,只需要开2^32个位大小的空间(约16G/4*32=500MB)

实现位图

bitmap()

  • 给所有整数开空间

数组可以定义的最小单位是Byte,并不是bit位。我们数组中依旧存放int类型,一个int占4个Byte,32个bit位。

namespace zxa
{class bitmap{public:bitmap(size_t N){_bits.resize(N, 0);//error_num = 0;}private:std::vector<int> _bits;size_t _num;//映射存储了多少个数据};
}
_bits.resize(N, 0);//error

这样并不是开N个位大小的空间,而是开了N个整型大小的空间。比如N=100时,我们是想开100个bit位来表示这100个整数在不在的状态,此时,却开了100个int,3200bit的大小。

_bits.resize(N / 32, 0);//error

这样也不对,比如N在0~32个之间(不包括32),那么一个Byte都没有开出来。比如,N=100时,开了100/32=3个int、3*4*8=96bit位的大小,但是,如果整数为97~99,要映射哪个位置?就越界了。

_bits.resize(N / 32 + 1, 0);

永远多开1个int、32bit大小的空间。 

set()

  • 将整数x映射的位置置为1

注意:数组中存放的是一个一个整型,而不是一个位一个位存的。

//将x映射的位置置为1
void set(size_t x)
{size_t index = x / 32;//计算x映射的位在第几个整型size_t pos = x % 32;//计算x在这个整型的第几位_bits[index] |= (1 << pos);//将该位置为1
}

reset()

  • 将整数x映射的位置置为0。 

注意:不排除删除了x之后,又删除x。(也就是x映射的位置本来就为0,又将x映射位置置为0)

//将x映射的位置置为0
void reset(size_t x)
{size_t index = x / 32;size_t pos = x % 32;_bits[index] &= ~(1 << pos);//_bits[index] = (_bits[index]|(1 << pos))^(1 << pos);也可以
}

test()

  • 判断整数x在不在。(也就是判断x映射的位置是否为1) 
//判断x在不在(x映射的位置是否为1)
bool test(size_t x)
{size_t index = x / 32;size_t pos = x % 32;return _bits[index] & (1 << pos);
}

完整代码+测试

bitmap.hpp:

#pragma once
#include<vector>namespace zxa
{class bitmap{public://给N个整数开空间bitmap(size_t N){//_bits.resize(N, 0);//_bits.resize(N / 32, 0);_bits.resize(N / 32 + 1, 0);_num = 0;}//将x映射的位置置为1void set(size_t x){size_t index = x / 32;//计算x映射的位在第几个整型size_t pos = x % 32;//计算x在这个整型的第几位_bits[index] |= (1 << pos);//将将该位置为1}//将x映射的位置置为0void reset(size_t x){size_t index = x / 32;size_t pos = x % 32;_bits[index] &= ~(1 << pos);//_bits[index] = (_bits[index]|(1 << pos))^(1 << pos);也可以}//判断x在不在(x所在位是否为1)bool test(size_t x){size_t index = x / 32;size_t pos = x % 32;return _bits[index] & (1 << pos);}private:std::vector<int> _bits;size_t _num;//映射存储了多少个数据};void test_bitmap();
}

test.cpp:

#define _CRT_SECURE_NO_WARNINGS 
#include"bitmap.hpp"//测试,以100个无符号整数为例
void zxa::test_bitmap()
{bitmap bm(100);bm.set(99);bm.set(98);bm.set(95);bm.reset(98);for (size_t i = 0; i < 100; i++){printf("[%d]:%d\n", i, bm.test(i));}
}
int main()
{zxa::test_bitmap();return 0;
}

结果:

对于一开始的面试题,40亿个整数理论都存在文件中,然后从文件中读取,这里不是很好做演示。

补充

表示整数2^32

表示整数 2^32 (4,294,967,296)的方式。

unsigned long long x = 1;
for (size_t i = 0; i < 32; ++i)
{x *= 2;
}
bitmap bm(x);
bitmap bm(-1);
bitmap bm(0Xffffffff);
bitmap bm(pow(2, 32));

位运算基本运算规则

  • 按位与 &:   全1为1,有0则0。
  • 按位或 |:     有1则1,全0为0。
  • 按位异或 ^: 相同为0,相异为1。
  • 按位取反 ~:1取反为0,0取反为1。
  • 左移 <<:      将一个二进制数的所有位向高位移动指定的位数。
  • 右移 >>:      将一个二进制数的所有位向低位移动指定的位数。

位运算都是针对的二进制位,左移右移不是左右方向移位,而是向高位移动。

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com