c - 需要帮助理解位图、位运算和 C

Question

免责声明:我问的这些问题与作业有关。作业本身要求实现一个位图并对其进行一些操作，但这不是我要问的。我只想了解这些概念，以便自己尝试实现。

我需要帮助来理解位图/位数组和按位运算。我了解二进制的基础知识以及左移/右移的工作原理，但我不确切知道这种使用有何好处。

基本上，我需要实现一个位图来存储(Eratosthenes 的)质筛的结果。这是针对不同 IPC 方法的较大作业的一小部分，但要完成该部分，我需要获得先筛完。我从未使用过按位运算，也从未了解过位图，所以我有点靠自己来学习。

据我所知，位图是具有一定大小的数组，对吧？我的意思是你可以有一个 8 位数组或一个 32 位数组(在我的例子中，我需要找到一个 32 位无符号整数的素数，所以我需要 32 位数组。)所以如果这是一个位数组，具体来说是 32 个位，那么我们基本上是在谈论一个由 32 个 1 和 0 组成的字符串。这如何转化为素数列表？我认为一种方法会评估二进制数并将其作为十进制数保存到一个新数组中，因此所有十进制素数都存在于一个数组中，但这似乎使用了太多数据。

我有位图的要点吗？还是我缺少什么？我试过在互联网上阅读有关此内容的信息，但找不到对我来说足够清楚的来源...

Answer 1

假设您有一个素数列表:{3, 5, 7}。您可以将这些数字存储为字符数组:char c[] = {3, 5, 7}，这需要 3 个字节。

相反，让我们使用单个字节，这样每个设置位都表示该数字在集合中。例如，01010100。如果我们可以设置我们想要的字节并稍后对其进行测试，我们可以使用它在单个字节中存储相同的信息。设置它:

char b = 0;
// want to set `3` so shift 1 twice to the left
b = b | (1 << 2); 
// also set `5`
b = b | (1 << 4);
// and 7
b = b | (1 << 6);    

并测试这些数字:

// is 3 in the map:
if (b & (1 << 2)) {
  // it is in...