1

免责声明：我问这些与作业有关的问题。任务本身要求实现一个位图并用它做一些操作，但这不是我要问的。我只是想了解这些概念，以便我可以自己尝试实现。

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

基本上，我需要实现一个位图来存储（Eratosthenes 的）素筛的结果。这是专注于不同 IPC 方法的大型作业的一小部分，但要到达那部分，我需要先完成筛子. 我从来不需要使用按位运算，也从来没有学过位图，所以我有点靠自己来学习这个。

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

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

4

3 回答 3

3

假设您有一个素数列表：{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...
于 2013-03-15T23:57:31.840 回答
1

位图允许您在您感兴趣的数字范围内构造一个大型谓词函数。如果您只有一个 8 位字符，则可以为八个值中的每一个存储布尔值。如果你有 2 个字符，它会使你的范围加倍。

因此，假设您有一个已存储此信息的位图，您的测试函数可能如下所示：

bool num_in_bitmap (int num, char *bitmap, size_t sz) {
    if (num/8 >= sz) return 0;
    return (bitmap[num/8] >> (num%8)) & 1;
}
于 2013-03-15T23:50:57.807 回答
1

您将需要比 32 位多得多的数据。

您需要一个最多 2^32 个数字的筛子，因此每个数字都需要一点。每个位将代表一个数字，如果数字是素数，则为 0，如果是合数，则为 1。（您可以通过注意第一位必须是 2 来节省一位，因为 1 既不是素数也不是复合数。浪费那一位更容易。）

2^32 = 4,294,967,296

除以 8

536,870,912 字节，或 1/2 GB。

因此，您将需要一个 2^29 字节或 2^27 个 4 字节字的数组，或任何您认为最好的数组，以及一种用于操作存储在数组中的字符（整数）中的各个位的方法。

听起来最终，您将有多个线程或进程在此共享内存上运行。如果您无法将所有内存分配给自己，您可能需要将它们全部存储在一个文件中。

假设您想找到 x 的位。然后让 a = x / 8 和 b = x - 8 * a。然后该位位于 arr[a] & (1 << b)。（尽可能避免使用模数运算符 %。）

//mark composite
a = x / 8;
b = x - 8 * a;
arr[a] |= 1 << b;

这听起来像是一个有趣的任务！

于 2013-03-16T01:15:12.660 回答