这个位排序代码中的位操作是如何工作的? [英] How do the bit manipulations in this bit-sorting code work?
问题描述
Jon Bentley 在他的《编程珍珠》一书中的第 1 列中介绍了一种使用位向量对非零正整数序列进行排序的技术.
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
", i);
return 0;
}
我了解 clr、set 和 test 函数的作用，并在下面解释它们:(如果我在这里错了，请纠正我).
I understand what the functions clr, set and test are doing and explain them below: ( please correct me if I am wrong here ).
- clr 清除第 i 位
- set 设置第 i 位
- test 返回第 i 位的值
现在，我不明白这些函数是如何做的.我无法弄清楚这三个函数中发生的所有位操作.
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.
推荐答案
前 3 个常量是相互关联的.BITSPERWORD 是 32.这是你想根据你的编译器+架构来设置的.SHIFT 是 5，因为 2^5 = 32.最后，MASK 是 0x1F，它是二进制的 11111(即:底部 5 位都已设置).等效地，MASK = BITSPERWORD - 1.
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.
bitset 在概念上只是一个位数组.这个实现实际上使用了一个整数数组，并假设每个整数有 32 位.所以每当我们想要设置、清除或测试(读取)一点时，我们需要弄清楚两件事:
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:
- 它在哪个 int(数组的)中
- 我们在谈论哪个 int 位
因为我们假设每个 int 有 32 位，所以我们可以除以 32(并截断)以获得我们想要的数组索引.除以 32 (BITSPERWORD) 与右移 5 (SHIFT) 相同.这就是 a[i>>SHIFT] 位的含义.您也可以将其写为 [i/BITSPERWORD](事实上，假设您的编译器具有合理的优化器，您可能会得到相同或非常相似的代码).
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).
既然我们知道我们想要 a 的哪个元素，我们需要找出哪一位.真的，我们想要剩下的.我们可以用 i%BITSPERWORD 做到这一点，但事实证明 i&MASK 是等价的.这是因为 BITSPERWORD 是 2 的幂(在本例中为 2^5)，而 MASK 是所有设置的底部 5 位.
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屋！
