Re: bit vector
From: Michael Mair (Michael.Mair_at_invalid.invalid)
Date: 02/15/05
- Next message: Keith Thompson: "Re: Making C better (by borrowing from C++)"
- Previous message: sipetar_at_inet.hr: "bit vector"
- In reply to: sipetar_at_inet.hr: "bit vector"
- Next in thread: sipetar_at_inet.hr: "Re: bit vector"
- Reply: sipetar_at_inet.hr: "Re: bit vector"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Tue, 15 Feb 2005 19:22:38 +0100
sipetar@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.
- Next message: Keith Thompson: "Re: Making C better (by borrowing from C++)"
- Previous message: sipetar_at_inet.hr: "bit vector"
- In reply to: sipetar_at_inet.hr: "bit vector"
- Next in thread: sipetar_at_inet.hr: "Re: bit vector"
- Reply: sipetar_at_inet.hr: "Re: bit vector"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
