位向量 [英] bit vector
问题描述
HI.首先，我很抱歉我的英语非常糟糕（拼写和语法）
我有一个问题..需要编写模拟Eratostens的程序
谜语（在C中）使用位向量，但我不知道如何实现位
vector
以及如何使用它。
我有这样的东西：
#define BIT_SET（v，n）（v [（n）>> 3] | = 1U<< （（n）& 7））
#define BIT_CLR（v，n）（v [（n）>> 3]& =〜（1U<<（n ）& 7）））
#define BIT_ISSET（v，n）（v [（n）>>> 3]&（1U<（（n）& 7 ）））
但是我不明白这一点，所以如果你能帮助我，我会很感激
那个......
谢谢你......
si ***** @ inet.hr 写道：HI.首先，我很抱歉我的英语非常糟糕（拼写和语法）
我有一个问题..需要使用位向量来编写模拟Eratostens谜语（在C中）的程序，但我不知道如何实现位
向量
以及如何使用它。
我有这样的事情：
#define BIT_SET（v，n）（v [（n）>> 3] | = 1U<< （（n）& 7））
#define BIT_CLR（v，n）（v [（n）>>>> =〜（1U<（（n）& 7 ）））#define BIT_ISSET（v，n）（v [（n）>>> 3]&（1U<（（n）& 7）））
<但是我不明白这一点，所以如果你能帮助我，我会很感激
那个..
因为这显然是一个功课问题，我我只想回顾一些想法：
我们有一个数组
unsigned char v [MAXNUMBER];
我们标记每个数字我通过将v [i]设置为1，从2..MAXNUMBER-1作为潜在素数
，然后应用筛选方法去掉
非素数。最后，我们知道上面
范围内的所有素数，因为只有他们在v中仍然有一个条目。
作为位数每个字节（CHAR_BIT）至少为8，我们认为
嘿，如果我们按位存储信息，我们可以节省因子8
并且最多可以达到8 * MAXNUMBER-1具有相同的数组。
现在，我们要在v [j]和
$中保存j * 8 + 0..j * 8 + 7的信息b $ b从那里检索它。这就是上面宏的用武之地。
您也可以将它们写成
#define BIT_SET（v，n）（v [（n）/ 8] | = 1U<（（n）％8））
#define BIT_ISSET（v，n）（v [（n）/ 8]&（1U<<（（n）％8）））
其中BIT_SET为n = 8 * j + k设置v [j]
（即整个第n位）的第k位为1， BIT_CLR将其设置为1
，如果未设置则BIT_ISSET为0，如果设置为非零，则为b / b
。
干杯
Michael
-
电子邮箱：我的是一个gmx点地址。
是的，这是我的作业（我是学生），对不起，如果我困扰你
但我没有多少chioce ....
2005年2月15日11:48:23 -0800， si ***** @ inet.hr
< si ***** @ inet.hr>写道：
是的，这是我的作业（我是学生），对不起，如果我打扰你
但我没有多少chioce ....
是的你有选择，你可以问你的导师。如果你在课堂上不理解（你确实去了课堂，
对吧？），那么他们的工作就是b $ b解释。家庭作业的目的是看学生是否理解了b
，而不是看他们是否可以让他人为他们做b
。你已经在这里给出了一个解释：
的宏是什么以及如何解决这个问题...
Chris C
HI.first of all i am sorry on my very bad english(spelling and grammar)
I have one problem.. need to write program that simulates Eratostens
riddle(in C) using bit vector, but I dont know how to implement bit
vector
and how to use it.
I''ve got something like this:
#define BIT_SET(v, n) (v[(n)>>3] |= 1U << ((n) & 7))
#define BIT_CLR(v, n) (v[(n)>>3] &= ~(1U << ((n) & 7)))
#define BIT_ISSET(v, n) (v[(n)>>3] & (1U << ((n) & 7)))
but I dont understand this, so if you can help me i would appreciate
that..
THANK YOU...
si*****@inet.hr wrote:HI.first of all i am sorry on my very bad english(spelling and grammar)
I have one problem.. need to write program that simulates Eratostens
riddle(in C) using bit vector, but I dont know how to implement bit
vector
and how to use it.
I''ve got something like this:
#define BIT_SET(v, n) (v[(n)>>3] |= 1U << ((n) & 7))
#define BIT_CLR(v, n) (v[(n)>>3] &= ~(1U << ((n) & 7)))
#define BIT_ISSET(v, n) (v[(n)>>3] & (1U << ((n) & 7)))
but I dont understand this, so if you can help me i would appreciate
that..
As this is obviously a homework question, I just will recap some ideas:
We have an array
unsigned char v[MAXNUMBER];
We mark every number i from 2..MAXNUMBER-1 as potential prime number
by setting v[i] to 1, then apply the sieve method to get rid of
non-prime numbers. In the end, we know all prime numbers in the above
range as only they will still have a 1 entry in v.
As the number of bits per byte (CHAR_BIT) is at least 8, we think
"Hey, if we store the information bitwise, we can save factor 8
and can get up to 8*MAXNUMBER-1 with the same array".
Now, we want to save the information for j*8+0..j*8+7 in v[j] and
retrieve it from there. This is where the above macros come in.
You could alternatively write them as
#define BIT_SET(v, n) (v[(n)/8] |= 1U << ((n)%8))
#define BIT_CLR(v, n) (v[(n)/8] &= ~(1U << ((n)%8)))
#define BIT_ISSET(v, n) (v[(n)/8] & (1U << ((n)%8)))
where BIT_SET sets for n=8*j+k the k''th bit of v[j]
(i.e. the overall n''th bit) to 1, BIT_CLR sets it to 1
and BIT_ISSET gives you 0 if the bit is not set and non-zero
if it is set.
Cheers
Michael
--
E-Mail: Mine is a gmx dot de address.
yes it is my homework (I am student), and sorry if I bothering you
but i dont have much chioce....
On 15 Feb 2005 11:48:23 -0800, si*****@inet.hr
<si*****@inet.hr> wrote:
yes it is my homework (I am student), and sorry if I bothering you
but i dont have much chioce....
Yes you do have a choice, you can ask your tutor. It''s their job to
explain if you didn''t understand in the class (you did go to the class,
right?). And the purpose of homework is to see whether the student has
understood, not to see whether they can get someone else to do it for
them. You''ve already been given an explanation here of what the macros
are for and how to go avout solving the problem...
Chris C
这篇关于位向量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
