该位排序代码中的位操作如何工作？ [英] How do the bit manipulations in this bit-sorting code work?
问题描述
乔恩·本特利（Jon Bentley）在他的《编程Pearls》一书中介绍了一种使用位向量对非零正整数序列进行排序的技术。
我从此处并粘贴到下面：
/ *版权所有（C）1999 Lucent Technologies * /
/ *摘自Jon Bentley的'Programming Pearls'* /
/ * bitsort.c-位列1中的位图排序
*对[0..N-1]范围内的不同整数进行排序* /
#include< stdio.h>
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a [1 + N / BITSPERWORD];
无效集合（int i）
{
int sh = i>>< SHIFT;
a [i> SHIFT] | =（1<（i& MASK））;
}
void clr（int i）{a [i> SHIFT]& =〜（1<（i& MASK））; }
int test（int i）{返回a [i>> SHIFT]& （1<<（i& MASK））； }
int main（）
{int i;
for（i = 0; i
/ *对于单词并行初始化
int top = 1 + N / BITSPERWORD;将2行以上替换为3以下
for（i = 0; i< top; i ++）
a [i] = 0;
* /
而（scanf（％d，& i）！= EOF）
set（i）;
for（i = 0; i
printf（％d\n，i）;
返回0；
}
我了解clr，set和test函数的作用，并在下面进行解释：（如果我在这里错了，请纠正我）。
- clr清除ith位
- set设置第i位
- test返回第i位的值
现在，我不了解功能如何执行功能。我无法弄清楚这三个函数中发生的所有位操作。
前三个常量是相互关联的。 BITSPERWORD为32。您要根据编译器+体系结构进行设置。 SHIFT为5，因为2 ^ 5 =32。最后，MASK为0x1F，二进制格式为11111（即：最低位全部置1）。等效地，MASK = BITSPERWORD-1。
从概念上讲，位集只是位数组。此实现实际上使用一个整数数组，并假定每个整数32位。因此，每当我们想要进行设置，清除或测试（读取）时，我们都需要弄清楚两件事：
- 数组）中是否是
- 我们正在谈论哪个int位？
因为我们假设每个int为32位，我们可以除以32（然后截断）以获得所需的数组索引。除以32（BITSPERWORD）与向右移5（SHIFT）相同。这就是a [i >> SHIFT]位的含义。您也可以将其写为a [i / BITSPERWORD]（实际上，假设您的编译器具有合理的优化程序，您可能会获得相同或非常相似的代码）。
<现在我们知道我们想要哪个元素，我们需要找出哪个位。真的，我们要剩下的。我们可以使用i％BITSPERWORD来完成此操作，但事实证明i& MASK是等效的。这是因为BITSPERWORD是2的幂（在这种情况下为2 ^ 5），而MASK是所有设置的后5位。
Jon Bentley in Column 1 of his book programming pearls introduces a technique for sorting a sequence of non-zero positive integers using bit vectors.
I have taken the program bitsort.c from here and pasted it below:
/* Copyright (C) 1999 Lucent Technologies */
/* From 'Programming Pearls' by Jon Bentley */
/* bitsort.c -- bitmap sort from Column 1
* Sort distinct integers in the range [0..N-1]
*/
#include <stdio.h>
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];
void set(int i)
{
int sh = i>>SHIFT;
a[i>>SHIFT] |= (1<<(i & MASK));
}
void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int test(int i){ return a[i>>SHIFT] & (1<<(i & MASK)); }
int main()
{ int i;
for (i = 0; i < N; i++)
clr(i);
/*Replace above 2 lines with below 3 for word-parallel init
int top = 1 + N/BITSPERWORD;
for (i = 0; i < top; i++)
a[i] = 0;
*/
while (scanf("%d", &i) != EOF)
set(i);
for (i = 0; i < N; i++)
if (test(i))
printf("%d\n", i);
return 0;
}
I understand what the functions clr, set and test are doing and explain them below: ( please correct me if I am wrong here ).
- clr clears the ith bit
- set sets the ith bit
- test returns the value at the ith bit
Now, I don't understand how the functions do what they do. I am unable to figure out all the bit manipulation happening in those three functions.
The first 3 constants are inter-related. BITSPERWORD is 32. This you'd want to set based on your compiler+architecture. SHIFT is 5, because 2^5 = 32. Finally, MASK is 0x1F which is 11111 in binary (ie: the bottom 5 bits are all set). Equivalently, MASK = BITSPERWORD - 1.
The bitset is conceptually just an array of bits. This implementation actually uses an array of ints, and assumes 32 bits per int. So whenever we want to set, clear or test (read) a bit we need to figure out two things:
- which int (of the array) is it in
- which of that int's bits are we talking about
Because we're assuming 32 bits per int, we can just divide by 32 (and truncate) to get the array index we want. Dividing by 32 (BITSPERWORD) is the same as shifting to the right by 5 (SHIFT). So that's what the a[i>>SHIFT] bit is about. You could also write this as a[i/BITSPERWORD] (and in fact, you'd probably get the same or very similar code assuming your compiler has a reasonable optimizer).
Now that we know which element of a we want, we need to figure out which bit. Really, we want the remainder. We could do this with i%BITSPERWORD, but it turns out that i&MASK is equivalent. This is because BITSPERWORD is a power of 2 (2^5 in this case) and MASK is the bottom 5 bits all set.
这篇关于该位排序代码中的位操作如何工作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
