Mailing List Archive: 49091 messages

## [REBOL] Re: bitset help

### From: brett:codeconscious at: 28-Sep-2002 0:24

```
Hi Romano,

> I do not understand how can be used all this new stuff from the new betas.
Can
> someone make an useful example to me? I knows only how to use bitset in
parse
> rule for char, but this seems something different.

A number inserted into a bitset is turns on a bit in the position indicated
by that number. Starting with zero. So if you have a set of things and to
each thing you assign an integer, you could encode the presence of each
thing in a bitset

people: [{Romano} {Anton} {Allen} {Gabriele} {Petr}]

0 will represent Romano
1 will represent Anton
etc.

Now I can use a bitset to represent set membership. My first set will be
people that have Italian email addresses:

I can query the set - does Petr have an Italian email address?

== none

I can create another set this time of people that have a name in which the
first letter falls into the A-K range.

a-k-names: make bitset! 8
repeat n [1 2 3] [insert a-k-names n]

Now if I can calculate the set of people that belong to both sets.

But there does not seem to a function to enumerate a bitset - so I do it
myself and find that Gabriele is a member of both sets:

>> repeat i subtract length? resulting-set 1 [if find resulting-set i
[print i]]
3
== none

Bitset lengths are always a multiple of 8. If you have 18 possible values
you will need a bitset of length 24

make bitset! 24

length? returns the capacity of the bitset

>> length? make bitset! 24
== 24

empty? will show you if any bits are set:

>> empty? make bitset! 2000
== true

Clear resets all the bits:

>> clear probe insert make bitset! 8 5
make bitset! #{20}
== make bitset! #{00}

On my machine and with this version a bitset seems to have a maximum size of
2040.

Here's a little function to represent the bits of a bitset:

stringbits: func [bitset [bitset!]][
{ } 2
]

This nicely shows how each number is mapped to a bit position:

>> stringbits insert make bitset! 8 0
== "00000001"
>> stringbits insert make bitset! 8 1
== "00000010"
>> stringbits insert make bitset! 8 2
== "00000100"
>> stringbits insert make bitset! 8 3
== "00001000"
>> stringbits insert insert make bitset! 8 0 3
== "00001001"

Don't know if that was what you wanted.

I found this article when looking at what bitsets can be used for. Quite
interesting I thought:

http://www.flipcode.com/tutorials/tut_bloomfilter.shtml

Regards,
Brett.
```