- "$vec2 = $vec1->new($bits);"
"@veclist =
$vec->new($bits);"
This is an alternative way of calling the bit vector
constructor method.
Vector "$vec1" (or
"$vec") is not affected by this, it
just serves as an anchor for the method invocation mechanism.
In fact ALL class methods in this module can be called
this way, even though this is probably considered to be
"politically incorrect" by OO ("object-orientation")
aficionados. ;-)
So even if you are too lazy to type
""Bit::Vector->"" instead
of ""$vec1->"" (and even
though laziness is - allegedly - a programmer's virtue
":-)"), maybe it is better not to use
this feature if you don't want to get booed at. ;-)
- "$vec2 = $vec1->Shadow();"
Creates a NEW bit vector
"$vec2" of the SAME SIZE as
"$vec1" but which is EMPTY.
Just like a shadow that has the same shape as the object it
originates from, but is flat and has no volume, i.e., contains
nothing.
- "$vec2 = $vec1->Clone();"
Creates a NEW bit vector
"$vec2" of the SAME SIZE as
"$vec1" which is an EXACT COPY
of "$vec1".
- "$vector = $vec1->Concat($vec2);"
This method returns a new bit vector object which is the
result of the concatenation of the contents of
"$vec1" and
"$vec2".
Note that the contents of
"$vec1" become the MOST
significant part of the resulting bit vector, and
"$vec2" the LEAST significant
part.
If both bit vector arguments have length zero, the resulting
bit vector will also have length zero.
- "$vector =
$vec1->Concat_List($vec2,$vec3,...);"
This is an alternative way of calling this (class) method as
an object method.
The method returns a new bit vector object which is the result
of the concatenation of the contents of "$vec1 .
$vec2 . $vec3 . ..."
See the section "class methods" above for a detailed
description of this method.
Note that the argument list may be empty and that all
arguments must be bit vectors if it isn't.
- "$bits = $vector->Size();"
Returns the size (number of bits) the given vector was created
with (or ""Resize()""d
to).
- "$vector->Resize($bits);"
Changes the size of the given vector to the specified number
of bits.
This method allows you to change the size of an existing bit
vector, preserving as many bits from the old vector as will fit into the
new one (i.e., all bits with indices smaller than the minimum of the
sizes of both vectors, old and new).
If the number of machine words needed to store the new vector
is smaller than or equal to the number of words needed to store the old
vector, the memory allocated for the old vector is reused for the new
one, and only the relevant book-keeping information is adjusted
accordingly.
This means that even if the number of bits increases, new
memory is not necessarily being allocated (i.e., if the old and the new
number of bits fit into the same number of machine words).
If the number of machine words needed to store the new vector
is greater than the number of words needed to store the old vector, new
memory is allocated for the new vector, the old vector is copied to the
new one, the remaining bits in the new vector are cleared (turned off)
and the old vector is deleted, i.e., the memory that was allocated for
it is released.
(An exception will be raised if the method is unable to
allocate the necessary memory for the new vector.)
As a consequence, if you decrease the size of a given vector
so that it will use fewer machine words, and increase it again later so
that it will use more words than immediately before but still less than
the original vector, new memory will be allocated anyway because the
information about the size of the original vector is lost whenever you
resize it.
Note also that if you specify a negative number for
"$bits" it will be interpreted as a
large positive number due to its internal two's complement binary
representation.
In such a case, "Resize()" will obediently
attempt to create a bit vector of that size, probably resulting in an
exception, as explained above.
Finally, note that - in contrast to previous versions -
resizing a bit vector to a size of zero bits (length zero) is now
permitted.
- "$vec2->Copy($vec1);"
Copies the contents of bit vector
"$vec1" to bit vector
"$vec2".
The previous contents of bit vector
"$vec2" get overwritten, i.e., are
lost.
Both vectors must exist beforehand, i.e., this method does not
CREATE any new bit vector object.
The two vectors may be of any size.
If the source bit vector is larger than the target, this
method will copy as much of the least significant bits of the source
vector as will fit into the target vector, thereby discarding any
extraneous most significant bits.
BEWARE that this causes a brutal cutoff in the middle of your
data, and it will also leave you with an almost unpredictable sign if
subsequently the number in the target vector is going to be interpreted
as a number! (You have been warned!)
If the target bit vector is larger than the source, this
method fills up the remaining most significant bits in the target bit
vector with either 0's or 1's, depending on the sign (= the most
significant bit) of the source bit vector. This is also known as
"sign extension".
This makes it possible to copy numbers from a smaller bit
vector into a larger one while preserving the number's absolute value as
well as its sign (due to the two's complement binary representation of
numbers).
- "$vector->Empty();"
Clears all bits in the given vector.
- "$vector->Fill();"
Sets all bits in the given vector.
- "$vector->Flip();"
Flips (i.e., complements) all bits in the given vector.
- "$vector->Primes();"
Clears the given bit vector and sets all bits whose indices
are prime numbers.
This method uses the algorithm known as the "Sieve of
Erathostenes" internally.
- "$vec2->Reverse($vec1);"
This method copies the given vector
"$vec1" to the vector
"$vec2", thereby reversing the order
of all bits.
I.e., the least significant bit of
"$vec1" becomes the most significant
bit of "$vec2", whereas the most
significant bit of "$vec1" becomes the
least significant bit of "$vec2", and
so forth for all bits in between.
Note that in-place processing is also possible, i.e.,
"$vec1" and
"$vec2" may be identical.
(Internally, this is the same as
"$vec1->Interval_Reverse(0,$vec1->Size()-1);".)
- "$vector->Interval_Empty($min,$max);"
Clears all bits in the interval
"[$min..$max]" (including both limits)
in the given vector.
"$min" and
"$max" may have the same value; this
is the same as clearing a single bit with
""Bit_Off()"" (but less
efficient).
Note that
"$vector->Interval_Empty(0,$vector->Size()-1);"
is the same as "$vector->Empty();"
(but less efficient).
- "$vector->Interval_Fill($min,$max);"
Sets all bits in the interval
"[$min..$max]" (including both limits)
in the given vector.
"$min" and
"$max" may have the same value; this
is the same as setting a single bit with
""Bit_On()"" (but less
efficient).
Note that
"$vector->Interval_Fill(0,$vector->Size()-1);"
is the same as "$vector->Fill();"
(but less efficient).
- "$vector->Interval_Flip($min,$max);"
Flips (i.e., complements) all bits in the interval
"[$min..$max]" (including both limits)
in the given vector.
"$min" and
"$max" may have the same value; this
is the same as flipping a single bit with
""bit_flip()"" (but less
efficient).
Note that
"$vector->Interval_Flip(0,$vector->Size()-1);"
is the same as "$vector->Flip();"
and "$vector->Complement($vector);"
(but less efficient).
- "$vector->Interval_Reverse($min,$max);"
Reverses the order of all bits in the interval
"[$min..$max]" (including both limits)
in the given vector.
I.e., bits "$min" and
"$max" swap places, and so forth for
all bits in between.
"$min" and
"$max" may have the same value; this
has no effect whatsoever, though.
- "if (($min,$max) =
$vector->Interval_Scan_inc($start))"
Returns the minimum and maximum indices of the next contiguous
block of set bits (i.e., bits in the "on" state).
The search starts at index
"$start" (i.e.,
"$min" >= "$start") and
proceeds upwards (i.e., "$max" >=
"$min"), thus repeatedly increments the search pointer
"$start" (internally).
Note though that the contents of the variable (or scalar
literal value) "$start" is NOT
altered. I.e., you have to set it to the desired value yourself prior to
each call to
""Interval_Scan_inc()"" (see
also the example given below).
Actually, the bit vector is not searched bit by bit, but one
machine word at a time, in order to speed up execution (which means that
this method is quite efficient).
An empty list is returned if no such block can be found.
Note that a single set bit (surrounded by cleared bits) is a
valid block by this definition. In that case the return values for
"$min" and
"$max" are the same.
Typical use:
$start = 0;
while (($start < $vector->Size()) &&
(($min,$max) = $vector->Interval_Scan_inc($start)))
{
$start = $max + 2;
# do something with $min and $max
}
- "if (($min,$max) =
$vector->Interval_Scan_dec($start))"
Returns the minimum and maximum indices of the next contiguous
block of set bits (i.e., bits in the "on" state).
The search starts at index
"$start" (i.e.,
"$max" <= "$start") and
proceeds downwards (i.e., "$min" <=
"$max"), thus repeatedly decrements the search pointer
"$start" (internally).
Note though that the contents of the variable (or scalar
literal value) "$start" is NOT
altered. I.e., you have to set it to the desired value yourself prior to
each call to
""Interval_Scan_dec()"" (see
also the example given below).
Actually, the bit vector is not searched bit by bit, but one
machine word at a time, in order to speed up execution (which means that
this method is quite efficient).
An empty list is returned if no such block can be found.
Note that a single set bit (surrounded by cleared bits) is a
valid block by this definition. In that case the return values for
"$min" and
"$max" are the same.
Typical use:
$start = $vector->Size() - 1;
while (($start >= 0) &&
(($min,$max) = $vector->Interval_Scan_dec($start)))
{
$start = $min - 2;
# do something with $min and $max
}
- "$vec2->Interval_Copy($vec1,$offset2,$offset1,$length);"
This method allows you to copy a stretch of contiguous bits
(starting at any position "$offset1"
you choose, with a length of "$length"
bits) from a given "source" bit vector
"$vec1" to another position
"$offset2" in a "target" bit
vector "$vec2".
Note that the two bit vectors
"$vec1" and
"$vec2" do NOT need to have the
same (matching) size!
Consequently, any of the two terms
""$offset1 + $length"" and
""$offset2 + $length"" (or
both) may exceed the actual length of its corresponding bit vector
(""$vec1->Size()"" and
""$vec2->Size()"",
respectively).
In such a case, the
"$length" parameter is automatically
reduced internally so that both terms above are bounded by the number of
bits of their corresponding bit vector.
This may even result in a length of zero, in which case
nothing is copied at all.
(Of course the value of the
"$length" parameter, supplied by you
in the initial method call, may also be zero right from the start!)
Note also that "$offset1"
and "$offset2" must lie within the
range "0" and, respectively,
""$vec1->Size()-1"" or
""$vec2->Size()-1"", or a
fatal "offset out of range" error will occur.
Note further that "$vec1"
and "$vec2" may be identical, i.e.,
you may copy a stretch of contiguous bits from one part of a given bit
vector to another part.
The source and the target interval may even overlap, in which
case the copying is automatically performed in ascending or descending
order (depending on the direction of the copy - downwards or upwards in
the bit vector, respectively) to handle this situation correctly, i.e.,
so that no bits are being overwritten before they have been copied
themselves.
- "$vec2->Interval_Substitute($vec1,$off2,$len2,$off1,$len1);"
This method is (roughly) the same for bit vectors (i.e.,
arrays of booleans) as what the "splice" function in Perl is
for lists (i.e., arrays of scalars).
(See "splice" in perlfunc for more details about
this function.)
The method allows you to substitute a stretch of contiguous
bits (defined by a position (offset)
"$off1" and a length of
"$len1" bits) from a given
"source" bit vector "$vec1"
for a different stretch of contiguous bits (defined by a position
(offset) "$off2" and a length of
"$len2" bits) in another,
"target" bit vector
"$vec2".
Note that the two bit vectors
"$vec1" and
"$vec2" do NOT need to have the
same (matching) size!
Note further that "$off1"
and "$off2" must lie within the range
"0" and, respectively,
""$vec1->Size()"" or
""$vec2->Size()"", or a
fatal "offset out of range" error will occur.
Alert readers will have noticed that these upper limits are
NOT
""$vec1->Size()-1"" and
""$vec2->Size()-1"", as
they would be for any other method in this module, but that these
offsets may actually point to one position PAST THE END of the
corresponding bit vector.
This is necessary in order to make it possible to
APPEND a given stretch of bits to the target bit vector instead
of REPLACING something in it.
For reasons of symmetry and generality, the same applies to
the offset in the source bit vector, even though such an offset (one
position past the end of the bit vector) does not serve any practical
purpose there (but does not cause any harm either).
(Actually this saves you from the need of testing for this
special case, in certain circumstances.)
Note that whenever the term ""$off1
+ $len1"" exceeds the size
""$vec1->Size()"" of bit
vector "$vec1" (or if
""$off2 + $len2"" exceeds
""$vec2->Size()""), the
corresponding length ("$len1" or
"$len2", respectively) is
automatically reduced internally so that
""$off1 + $len1 <=
$vec1->Size()"" (and
""$off2 + $len2 <=
$vec2->Size()"") holds.
(Note that this does NOT alter the intended result,
even though this may seem counter-intuitive at first!)
This may even result in a length
("$len1" or
"$len2") of zero.
A length of zero for the interval in the SOURCE bit
vector (""$len1 == 0"")
means that the indicated stretch of bits in the target bit vector
(starting at position "$off2") is to
be replaced by NOTHING, i.e., is to be DELETED.
A length of zero for the interval in the TARGET bit
vector ("$len2 == 0") means that
NOTHING is replaced, and that the stretch of bits from the source
bit vector is simply INSERTED into the target bit vector at the
indicated position ("$off2").
If both length parameters are zero, nothing is done at
all.
Note that in contrast to any other method in this module
(especially
""Interval_Copy()"",
""Insert()"" and
""Delete()""), this method
IMPLICITLY and AUTOMATICALLY adapts the length of the
resulting bit vector as needed, as given by
$size = $vec2->Size(); # before
$size += $len1 - $len2; # after
(The only other method in this module that changes the size of
a bit vector is the method
""Resize()"".)
In other words, replacing a given interval of bits in the
target bit vector with a longer or shorter stretch of bits from the
source bit vector, or simply inserting
(""$len2 == 0"") a stretch
of bits into or deleting (""$len1 ==
0"") an interval of bits from the target bit vector
will automatically increase or decrease, respectively, the size of the
target bit vector accordingly.
For the sake of generality, this may even result in a bit
vector with a size of zero (containing no bits at all).
This is also the reason why bit vectors of length zero are
permitted in this module in the first place, starting with version
5.0.
Finally, note that "$vec1"
and "$vec2" may be identical, i.e.,
in-place processing is possible.
(If you think about that for a while or if you look at the
code, you will see that this is far from trivial!)
- "if ($vector->is_empty())"
Tests whether the given bit vector is empty, i.e., whether
ALL of its bits are cleared (in the "off" state).
In "big integer" arithmetic, this is equivalent to
testing whether the number stored in the bit vector is zero
("0").
Returns "true"
("1") if the bit vector is empty and
"false" ("0") otherwise.
Note that this method also returns "true"
("1") if the given bit vector has a
length of zero, i.e., if it contains no bits at all.
- "if ($vector->is_full())"
Tests whether the given bit vector is full, i.e., whether
ALL of its bits are set (in the "on" state).
In "big integer" arithmetic, this is equivalent to
testing whether the number stored in the bit vector is minus one
("-1").
Returns "true"
("1") if the bit vector is full and
"false" ("0") otherwise.
If the given bit vector has a length of zero (i.e., if it
contains no bits at all), this method returns "false"
("0").
- "if ($vec1->equal($vec2))"
Tests the two given bit vectors for equality.
Returns "true"
("1") if the two bit vectors are exact
copies of one another and "false"
("0") otherwise.
- "$cmp = $vec1->Lexicompare($vec2);"
Compares the two given bit vectors, which are regarded as
UNSIGNED numbers in binary representation.
The method returns
""-1"" if the first bit
vector is smaller than the second bit vector,
"0" if the two bit vectors are exact
copies of one another and "1" if the
first bit vector is greater than the second bit vector.
- "$cmp = $vec1->Compare($vec2);"
Compares the two given bit vectors, which are regarded as
SIGNED numbers in binary representation.
The method returns
""-1"" if the first bit
vector is smaller than the second bit vector,
"0" if the two bit vectors are exact
copies of one another and "1" if the
first bit vector is greater than the second bit vector.
- "$string = $vector->to_Hex();"
Returns a hexadecimal string representing the given bit
vector.
Note that this representation is quite compact, in that it
only needs at most twice the number of bytes needed to store the bit
vector itself, internally.
Note also that since a hexadecimal digit is always worth four
bits, the length of the resulting string is always a multiple of four
bits, regardless of the true length (in bits) of the given bit
vector.
Finally, note that the LEAST significant hexadecimal
digit is located at the RIGHT end of the resulting string, and
the MOST significant digit at the LEFT end.
- "$vector->from_Hex($string);"
Allows to read in the contents of a bit vector from a
hexadecimal string, such as returned by the method
""to_Hex()"" (see
above).
Remember that the least significant bits are always to the
right of a hexadecimal string, and the most significant bits to the
left. Therefore, the string is actually read in from right to left while
the bit vector is filled accordingly, 4 bits at a time, starting with
the least significant bits and going upward to the most significant
bits.
If the given string contains less hexadecimal digits than are
needed to completely fill the given bit vector, the remaining (most
significant) bits are all cleared.
This also means that, even if the given string does not
contain enough digits to completely fill the given bit vector, the
previous contents of the bit vector are erased completely.
If the given string is longer than it needs to fill the given
bit vector, the superfluous characters are simply ignored.
(In fact they are ignored completely - they are not even
checked for proper syntax. See also below for more about that.)
This behaviour is intentional so that you may read in the
string representing one bit vector into another bit vector of different
size, i.e., as much of it as will fit.
If during the process of reading the given string any
character is encountered which is not a hexadecimal digit, a fatal
syntax error ensues ("input string syntax error").
- "$string = $vector->to_Bin();"
Returns a binary string representing the given bit vector.
Example:
$vector = Bit::Vector->new(8);
$vector->Primes();
$string = $vector->to_Bin();
print "'$string'\n";
This prints:
'10101100'
(Bits #7, #5, #3 and #2 are set.)
Note that the LEAST significant bit is located at the
RIGHT end of the resulting string, and the MOST
significant bit at the LEFT end.
- "$vector->from_Bin($string);"
This method allows you to read in the contents of a bit vector
from a binary string, such as returned by the method
""to_Bin()"" (see
above).
Note that this method assumes that the LEAST
significant bit is located at the RIGHT end of the binary string,
and the MOST significant bit at the LEFT end. Therefore,
the string is actually read in from right to left while the bit vector
is filled accordingly, one bit at a time, starting with the least
significant bit and going upward to the most significant bit.
If the given string contains less binary digits
("0" and
"1") than are needed to completely
fill the given bit vector, the remaining (most significant) bits are all
cleared.
This also means that, even if the given string does not
contain enough digits to completely fill the given bit vector, the
previous contents of the bit vector are erased completely.
If the given string is longer than it needs to fill the given
bit vector, the superfluous characters are simply ignored.
(In fact they are ignored completely - they are not even
checked for proper syntax. See also below for more about that.)
This behaviour is intentional so that you may read in the
string representing one bit vector into another bit vector of different
size, i.e., as much of it as will fit.
If during the process of reading the given string any
character is encountered which is not either
"0" or
"1", a fatal syntax error ensues
("input string syntax error").
- "$string = $vector->to_Dec();"
This method returns a string representing the contents of the
given bit vector converted to decimal (base
10).
Note that this method assumes the given bit vector to be
SIGNED (and to contain a number in two's complement binary
representation).
Consequently, whenever the most significant bit of the given
bit vector is set, the number stored in it is regarded as being
NEGATIVE.
The resulting string can be fed into
""from_Dec()"" (see below)
in order to copy the contents of this bit vector to another one (or to
restore the contents of this one). This is not advisable, though, since
this would be very inefficient (there are much more efficient methods
for storing and copying bit vectors in this module).
Note that such conversion from binary to decimal is inherently
slow since the bit vector has to be repeatedly divided by
10 with remainder until the quotient becomes
0 (each remainder in turn represents a single
decimal digit of the resulting string).
This is also true for the implementation of this method in
this module, even though a considerable effort has been made to speed it
up: instead of repeatedly dividing by 10, the
bit vector is repeatedly divided by the largest power of
10 that will fit into a machine word. The
remainder is then repeatedly divided by 10 using
only machine word arithmetics, which is much faster than dividing the
whole bit vector ("divide and rule" principle).
According to my own measurements, this resulted in an 8-fold
speed increase over the straightforward approach.
Still, conversion to decimal should be used only where
absolutely necessary.
Keep the resulting string stored in some variable if you need
it again, instead of converting the bit vector all over again.
Beware that if you set the configuration for overloaded
operators to "output=decimal", this method will be called for
every bit vector enclosed in double quotes!
- "$vector->from_Dec($string);"
This method allows you to convert a given decimal number,
which may be positive or negative, into two's complement binary
representation, which is then stored in the given bit vector.
The decimal number should always be provided as a string, to
avoid possible truncation (due to the limited precision of integers in
Perl) or formatting (due to Perl's use of scientific notation for large
numbers), which would lead to errors.
If the binary representation of the given decimal number is
too big to fit into the given bit vector (if the given bit vector does
not contain enough bits to hold it), a fatal "numeric overflow
error" occurs.
If the input string contains other characters than decimal
digits ("0-9") and an optional leading
sign (""+"" or
""-""), a fatal "input
string syntax error" occurs.
Beware that large positive numbers which cause the most
significant bit to be set (e.g. "255" in a bit vector with 8
bits) will be printed as negative numbers when converted back to decimal
using the method "to_Dec()" (e.g. "-1", in
our example), because numbers with the most significant bit set are
considered to be negative in two's complement binary representation.
Note also that while it is possible to thusly enter negative
numbers as large positive numbers (e.g. "255" for
"-1" in a bit vector with 8 bits), the contrary isn't, i.e.,
you cannot enter "-255" for "+1", in our example. A
fatal "numeric overflow error" will occur if you try to do
so.
If possible program abortion is unwanted or intolerable, use
""eval"", like this:
eval { $vector->from_Dec("1152921504606846976"); };
if ($@)
{
# an error occurred
}
There are four possible error messages:
if ($@ =~ /item is not a string/)
if ($@ =~ /input string syntax error/)
if ($@ =~ /numeric overflow error/)
if ($@ =~ /unable to allocate memory/)
Note that the conversion from decimal to binary is costly in
terms of processing time, since a lot of multiplications have to be
carried out (in principle, each decimal digit must be multiplied with
the binary representation of the power of 10
corresponding to its position in the decimal number, i.e., 1, 10, 100,
1000, 10000 and so on).
This is not as time consuming as the opposite conversion, from
binary to decimal (where successive divisions have to be carried out,
which are even more expensive than multiplications), but still
noticeable.
Again (as in the case of
""to_Dec()""), the
implementation of this method in this module uses the principle of
"divide and rule" in order to speed up the conversion, i.e.,
as many decimal digits as possible are first accumulated (converted) in
a machine word and only then stored in the given bit vector.
Even so, use this method only where absolutely necessary if
speed is an important consideration in your application.
Beware that if you set the configuration for overloaded
operators to "input=decimal", this method will be called for
every scalar operand you use!
- "$string = $vector->to_Enum();"
Converts the given bit vector or set into an enumeration of
single indices and ranges of indices (".newsrc" style),
representing the bits that are set
("1") in the bit vector.
Example:
$vector = Bit::Vector->new(20);
$vector->Bit_On(2);
$vector->Bit_On(3);
$vector->Bit_On(11);
$vector->Interval_Fill(5,7);
$vector->Interval_Fill(13,19);
print "'", $vector->to_Enum(), "'\n";
which prints
'2,3,5-7,11,13-19'
If the given bit vector is empty, the resulting string will
also be empty.
Note, by the way, that the above example can also be written a
little handier, perhaps, as follows:
Bit::Vector->Configuration("out=enum");
$vector = Bit::Vector->new(20);
$vector->Index_List_Store(2,3,5,6,7,11,13,14,15,16,17,18,19);
print "'$vector'\n";
- "$vector->from_Enum($string);"
This method first empties the given bit vector and then tries
to set the bits and ranges of bits specified in the given string.
The string "$string" must
only contain unsigned integers or ranges of integers (two unsigned
integers separated by a dash "-"), separated by commas
(",").
All other characters are disallowed (including white space!)
and will lead to a fatal "input string syntax error".
In each range, the first integer (the lower limit of the
range) must always be less than or equal to the second integer (the
upper limit), or a fatal "minimum > maximum index" error
occurs.
All integers must lie in the permitted range for the given bit
vector, i.e., they must lie between
"0" and
""$vector->Size()-1"".
If this condition is not met, a fatal "index out of
range" error occurs.
If possible program abortion is unwanted or intolerable, use
""eval"", like this:
eval { $vector->from_Enum("2,3,5-7,11,13-19"); };
if ($@)
{
# an error occurred
}
There are four possible error messages:
if ($@ =~ /item is not a string/)
if ($@ =~ /input string syntax error/)
if ($@ =~ /index out of range/)
if ($@ =~ /minimum > maximum index/)
Note that the order of the indices and ranges is irrelevant,
i.e.,
eval { $vector->from_Enum("11,5-7,3,13-19,2"); };
results in the same vector as in the example above.
Ranges and indices may also overlap.
This is because each (single) index in the string is passed to
the method ""Bit_On()"",
internally, and each range to the method
""Interval_Fill()"".
This means that the resulting bit vector is just the union of
all the indices and ranges specified in the given string.
- "$vector->Bit_Off($index);"
Clears the bit with index
"$index" in the given vector.
- "$vector->Bit_On($index);"
Sets the bit with index
"$index" in the given vector.
- "$vector->bit_flip($index)"
Flips (i.e., complements) the bit with index
"$index" in the given vector.
Moreover, this method returns the NEW state of the bit
in question, i.e., it returns "0" if
the bit is cleared or "1" if the bit
is set (AFTER flipping it).
- "if ($vector->bit_test($index))"
"if
($vector->contains($index))"
Returns the current state of the bit with index
"$index" in the given vector, i.e.,
returns "0" if it is cleared (in the
"off" state) or "1" if it is
set (in the "on" state).
- "$vector->Bit_Copy($index,$bit);"
Sets the bit with index
"$index" in the given vector either to
"0" or
"1" depending on the boolean value
"$bit".
- "$vector->LSB($bit);"
Allows you to set the least significant bit in the given bit
vector to the value given by the boolean parameter
"$bit".
This is a (faster) shortcut for
""$vector->Bit_Copy(0,$bit);"".
- "$vector->MSB($bit);"
Allows you to set the most significant bit in the given bit
vector to the value given by the boolean parameter
"$bit".
This is a (faster) shortcut for
""$vector->Bit_Copy($vector->Size()-1,$bit);"".
- "$bit = $vector->lsb();"
Returns the least significant bit of the given bit vector.
This is a (faster) shortcut for
""$bit =
$vector->bit_test(0);"".
- "$bit = $vector->msb();"
Returns the most significant bit of the given bit vector.
This is a (faster) shortcut for
""$bit =
$vector->bit_test($vector->Size()-1);"".
- "$carry_out =
$vector->rotate_left();"
carry MSB vector: LSB
out:
+---+ +---+---+---+--- ---+---+---+---+
| | <---+--- | | | | ... | | | | <---+
+---+ | +---+---+---+--- ---+---+---+---+ |
| |
+------------------------------------------------+
The least significant bit (LSB) is the bit with index
"0", the most significant bit (MSB) is
the bit with index
""$vector->Size()-1"".
- "$carry_out =
$vector->rotate_right();"
MSB vector: LSB carry
out:
+---+---+---+--- ---+---+---+---+ +---+
+---> | | | | ... | | | | ---+---> | |
| +---+---+---+--- ---+---+---+---+ | +---+
| |
+------------------------------------------------+
The least significant bit (LSB) is the bit with index
"0", the most significant bit (MSB) is
the bit with index
""$vector->Size()-1"".
- "$carry_out =
$vector->shift_left($carry_in);"
carry MSB vector: LSB carry
out: in:
+---+ +---+---+---+--- ---+---+---+---+ +---+
| | <--- | | | | ... | | | | <--- | |
+---+ +---+---+---+--- ---+---+---+---+ +---+
The least significant bit (LSB) is the bit with index
"0", the most significant bit (MSB) is
the bit with index
""$vector->Size()-1"".
- "$carry_out =
$vector->shift_right($carry_in);"
carry MSB vector: LSB carry
in: out:
+---+ +---+---+---+--- ---+---+---+---+ +---+
| | ---> | | | | ... | | | | ---> | |
+---+ +---+---+---+--- ---+---+---+---+ +---+
The least significant bit (LSB) is the bit with index
"0", the most significant bit (MSB) is
the bit with index
""$vector->Size()-1"".
- "$vector->Move_Left($bits);"
Shifts the given bit vector left by
"$bits" bits, i.e., inserts
"$bits" new bits at the lower end
(least significant bit) of the bit vector, moving all other bits up by
"$bits" places, thereby losing the
"$bits" most significant bits.
The inserted new bits are all cleared (set to the
"off" state).
This method does nothing if
"$bits" is equal to zero.
Beware that the whole bit vector is cleared WITHOUT
WARNING if "$bits" is greater than
or equal to the size of the given bit vector!
In fact this method is equivalent to
for ( $i = 0; $i < $bits; $i++ ) { $vector->shift_left(0); }
except that it is much more efficient (for
"$bits" greater than or equal to the
number of bits in a machine word on your system) than this
straightforward approach.
- "$vector->Move_Right($bits);"
Shifts the given bit vector right by
"$bits" bits, i.e., deletes the
"$bits" least significant bits of the
bit vector, moving all other bits down by
"$bits" places, thereby creating
"$bits" new bits at the upper end
(most significant bit) of the bit vector.
These new bits are all cleared (set to the "off"
state).
This method does nothing if
"$bits" is equal to zero.
Beware that the whole bit vector is cleared WITHOUT
WARNING if "$bits" is greater than
or equal to the size of the given bit vector!
In fact this method is equivalent to
for ( $i = 0; $i < $bits; $i++ ) { $vector->shift_right(0); }
except that it is much more efficient (for
"$bits" greater than or equal to the
number of bits in a machine word on your system) than this
straightforward approach.
- "$vector->Insert($offset,$bits);"
This method inserts "$bits"
fresh new bits at position "$offset"
in the given bit vector.
The "$bits" most significant
bits are lost, and all bits starting with bit number
"$offset" up to and including bit
number
""$vector->Size()-$bits-1""
are moved up by "$bits" places.
The now vacant "$bits" bits
starting at bit number "$offset" (up
to and including bit number
""$offset+$bits-1"") are
then set to zero (cleared).
Note that this method does NOT increase the size of the
given bit vector, i.e., the bit vector is NOT extended at its
upper end to "rescue" the
"$bits" uppermost (most significant)
bits - instead, these bits are lost forever.
If you don't want this to happen, you have to increase the
size of the given bit vector EXPLICITLY and BEFORE you
perform the "Insert" operation, with a statement such as the
following:
$vector->Resize($vector->Size() + $bits);
Or use the method
""Interval_Substitute()""
instead of ""Insert()"",
which performs automatic growing and shrinking of its target bit
vector.
Note also that "$offset"
must lie in the permitted range between
"0" and
""$vector->Size()-1"", or
a fatal "offset out of range" error will occur.
If the term ""$offset +
$bits"" exceeds
""$vector->Size()-1"",
all the bits starting with bit number
"$offset" up to bit number
""$vector->Size()-1"" are
simply cleared.
- "$vector->Delete($offset,$bits);"
This method deletes, i.e., removes the bits starting at
position "$offset" up to and including
bit number
""$offset+$bits-1"" from the
given bit vector.
The remaining uppermost bits (starting at position
""$offset+$bits"" up to and
including bit number
""$vector->Size()-1"")
are moved down by "$bits" places.
The now vacant uppermost (most significant)
"$bits" bits are then set to zero
(cleared).
Note that this method does NOT decrease the size of the
given bit vector, i.e., the bit vector is NOT clipped at its
upper end to "get rid of" the vacant
"$bits" uppermost bits.
If you don't want this, i.e., if you want the bit vector to
shrink accordingly, you have to do so EXPLICITLY and AFTER
the "Delete" operation, with a couple of statements such as
these:
$size = $vector->Size();
if ($bits > $size) { $bits = $size; }
$vector->Resize($size - $bits);
Or use the method
""Interval_Substitute()""
instead of ""Delete()"",
which performs automatic growing and shrinking of its target bit
vector.
Note also that "$offset"
must lie in the permitted range between
"0" and
""$vector->Size()-1"", or
a fatal "offset out of range" error will occur.
If the term ""$offset +
$bits"" exceeds
""$vector->Size()-1"",
all the bits starting with bit number
"$offset" up to bit number
""$vector->Size()-1"" are
simply cleared.
- "$carry = $vector->increment();"
This method increments the given bit vector.
Note that this method regards bit vectors as being unsigned,
i.e., the largest possible positive number is directly followed by the
smallest possible (or greatest possible, speaking in absolute terms)
negative number:
before: 2 ^ (b-1) - 1 (= "0111...1111")
after: 2 ^ (b-1) (= "1000...0000")
where ""b"" is the
number of bits of the given bit vector.
The method returns "false"
("0") in all cases except when a carry
over occurs (in which case it returns "true", i.e.,
"1"), which happens when the number
"1111...1111" is incremented, which gives
"0000...0000" plus a carry over to the next higher (binary)
digit.
This can be used for the terminating condition of a
"while" loop, for instance, in order to cycle through all
possible values the bit vector can assume.
- "$carry = $vector->decrement();"
This method decrements the given bit vector.
Note that this method regards bit vectors as being unsigned,
i.e., the smallest possible (or greatest possible, speaking in absolute
terms) negative number is directly followed by the largest possible
positive number:
before: 2 ^ (b-1) (= "1000...0000")
after: 2 ^ (b-1) - 1 (= "0111...1111")
where ""b"" is the
number of bits of the given bit vector.
The method returns "false"
("0") in all cases except when a carry
over occurs (in which case it returns "true", i.e.,
"1"), which happens when the number
"0000...0000" is decremented, which gives
"1111...1111" minus a carry over to the next higher (binary)
digit.
This can be used for the terminating condition of a
"while" loop, for instance, in order to cycle through all
possible values the bit vector can assume.
- "$overflow = $vec2->inc($vec1);"
This method copies the contents of bit vector
"$vec1" to bit vector
"$vec2" and increments the copy (not
the original).
If by incrementing the number its sign becomes invalid, the
return value ("overflow" flag) will be true
("1"), or false
("0") if not. (See the description of
the method "add()" below for a more in-depth
explanation of what "overflow" means).
Note that in-place operation is also possible, i.e.,
"$vec1" and
"$vec2" may be identical.
- "$overflow = $vec2->dec($vec1);"
This method copies the contents of bit vector
"$vec1" to bit vector
"$vec2" and decrements the copy (not
the original).
If by decrementing the number its sign becomes invalid, the
return value ("overflow" flag) will be true
("1"), or false
("0") if not. (See the description of
the method "subtract()" below for a more in-depth
explanation of what "overflow" means).
Note that in-place operation is also possible, i.e.,
"$vec1" and
"$vec2" may be identical.
- "$carry =
$vec3->add($vec1,$vec2,$carry);"
"($carry,$overflow) =
$vec3->add($vec1,$vec2,$carry);"
This method adds the two numbers contained in bit vector
"$vec1" and
"$vec2" with carry
"$carry" and stores the result in bit
vector "$vec3".
I.e.,
$vec3 = $vec1 +
$vec2 + $carry
Note that the "$carry"
parameter is a boolean value, i.e., only its least significant bit is
taken into account. (Think of it as though
""$carry &= 1;"" was
always executed internally.)
In scalar context, the method returns a boolean value which
indicates if a carry over (to the next higher bit position) has occured.
In list context, the method returns the carry and the overflow flag (in
this order).
The overflow flag is true
("1") if the sign (i.e., the most
significant bit) of the result is wrong. This can happen when adding two
very large positive numbers or when adding two (by their absolute value)
very large negative numbers. See also further below.
The carry in- and output is needed mainly for cascading, i.e.,
to add numbers that are fragmented into several pieces.
Example:
# initialize
for ( $i = 0; $i < $n; $i++ )
{
$a[$i] = Bit::Vector->new($bits);
$b[$i] = Bit::Vector->new($bits);
$c[$i] = Bit::Vector->new($bits);
}
# fill @a and @b
# $a[ 0 ] is low order part,
# $a[$n-1] is high order part,
# and same for @b
# add
$carry = 0;
for ( $i = 0; $i < $n; $i++ )
{
$carry = $c[$i]->add($a[$i],$b[$i],$carry);
}
Note that it makes no difference to this method whether the
numbers in "$vec1" and
"$vec2" are unsigned or signed (i.e.,
in two's complement binary representation).
Note however that the return value (carry flag) is not
meaningful when the numbers are SIGNED.
Moreover, when the numbers are signed, a special type of error
can occur which is commonly called an "overflow error".
An overflow error occurs when the sign of the result (its most
significant bit) is flipped (i.e., falsified) by a carry over from the
next-lower bit position ("MSB-1").
In fact matters are a bit more complicated than that: the
overflow flag is set to "true" whenever there is a carry over
from bit position MSB-1 to the most significant bit (MSB) but no carry
over from the MSB to the output carry flag, or vice-versa, i.e., when
there is no carry over from bit position MSB-1 to the most significant
bit (MSB) but a carry over to the output carry flag.
Thus the overflow flag is the result of an exclusive-or
operation between incoming and outgoing carry over at the most
significant bit position.
- "$carry =
$vec3->subtract($vec1,$vec2,$carry);"
"($carry,$overflow) =
$vec3->subtract($vec1,$vec2,$carry);"
This method subtracts the two numbers contained in bit vector
"$vec1" and
"$vec2" with carry
"$carry" and stores the result in bit
vector "$vec3".
I.e.,
$vec3 = $vec1 -
$vec2 - $carry
Note that the "$carry"
parameter is a boolean value, i.e., only its least significant bit is
taken into account. (Think of it as though
""$carry &= 1;"" was
always executed internally.)
In scalar context, the method returns a boolean value which
indicates if a carry over (to the next higher bit position) has occured.
In list context, the method returns the carry and the overflow flag (in
this order).
The overflow flag is true
("1") if the sign (i.e., the most
significant bit) of the result is wrong. This can happen when
subtracting a very large negative number from a very large positive
number or vice-versa. See also further below.
The carry in- and output is needed mainly for cascading, i.e.,
to subtract numbers that are fragmented into several pieces.
Example:
# initialize
for ( $i = 0; $i < $n; $i++ )
{
$a[$i] = Bit::Vector->new($bits);
$b[$i] = Bit::Vector->new($bits);
$c[$i] = Bit::Vector->new($bits);
}
# fill @a and @b
# $a[ 0 ] is low order part,
# $a[$n-1] is high order part,
# and same for @b
# subtract
$carry = 0;
for ( $i = 0; $i < $n; $i++ )
{
$carry = $c[$i]->subtract($a[$i],$b[$i],$carry);
}
Note that it makes no difference to this method whether the
numbers in "$vec1" and
"$vec2" are unsigned or signed (i.e.,
in two's complement binary representation).
Note however that the return value (carry flag) is not
meaningful when the numbers are SIGNED.
Moreover, when the numbers are signed, a special type of error
can occur which is commonly called an "overflow error".
An overflow error occurs when the sign of the result (its most
significant bit) is flipped (i.e., falsified) by a carry over from the
next-lower bit position ("MSB-1").
In fact matters are a bit more complicated than that: the
overflow flag is set to "true" whenever there is a carry over
from bit position MSB-1 to the most significant bit (MSB) but no carry
over from the MSB to the output carry flag, or vice-versa, i.e., when
there is no carry over from bit position MSB-1 to the most significant
bit (MSB) but a carry over to the output carry flag.
Thus the overflow flag is the result of an exclusive-or
operation between incoming and outgoing carry over at the most
significant bit position.
- "$vec2->Neg($vec1);"
"$vec2->Negate($vec1);"
This method calculates the two's complement of the number in
bit vector "$vec1" and stores the
result in bit vector "$vec2".
Calculating the two's complement of a given number in binary
representation consists of inverting all bits and incrementing the
result by one.
This is the same as changing the sign of the given number from
""+"" to
""-"" or vice-versa. In
other words, applying this method twice on a given number yields the
original number again.
Note that in-place processing is also possible, i.e.,
"$vec1" and
"$vec2" may be identical.
Most importantly, beware that this method produces a
counter-intuitive result if the number contained in bit vector
"$vec1" is "2 ^
(n-1)" (i.e., "1000...0000"), where
""n"" is the number of bits
the given bit vector contains: The negated value of this number is the
number itself!
- "$vec2->Abs($vec1);"
"$vec2->Absolute($vec1);"
Depending on the sign (i.e., the most significant bit) of the
number in bit vector "$vec1", the
contents of bit vector "$vec1" are
copied to bit vector "$vec2" either
with the method ""Copy()""
(if the number in bit vector "$vec1"
is positive), or with
""Negate()"" (if the number
in bit vector "$vec1" is
negative).
In other words, this method calculates the absolute value of
the number in bit vector "$vec1" and
stores the result in bit vector
"$vec2".
Note that in-place processing is also possible, i.e.,
"$vec1" and
"$vec2" may be identical.
Most importantly, beware that this method produces a
counter-intuitive result if the number contained in bit vector
"$vec1" is "2 ^
(n-1)" (i.e., "1000...0000"), where
""n"" is the number of bits
the given bit vector contains: The absolute value of this number is the
number itself, even though this number is still negative by definition
(the most significant bit is still set)!
- "$sign = $vector->Sign();"
This method returns "0" if
all bits in the given bit vector are cleared, i.e., if the given bit
vector contains the number "0", or if
the given bit vector has a length of zero (contains no bits at all).
If not all bits are cleared, this method returns
""-1"" if the most
significant bit is set (i.e., if the bit vector contains a negative
number), or "1" otherwise (i.e., if
the bit vector contains a positive number).
- "$vec3->Multiply($vec1,$vec2);"
This method multiplies the two numbers contained in bit vector
"$vec1" and
"$vec2" and stores the result in bit
vector "$vec3".
Note that this method regards its arguments as
SIGNED.
If you want to make sure that a large number can never be
treated as being negative by mistake, make your bit vectors at least one
bit longer than the largest number you wish to represent, right from the
start, or proceed as follows:
$msb1 = $vec1->msb();
$msb2 = $vec2->msb();
$vec1->Resize($vec1->Size()+1);
$vec2->Resize($vec2->Size()+1);
$vec3->Resize($vec3->Size()+1);
$vec1->MSB($msb1);
$vec2->MSB($msb2);
$vec3->Multiply($vec1,$vec2);
Note also that all three bit vector arguments must in
principle obey the rule of matching sizes, but that the bit vector
"$vec3" may be larger than the two
factors "$vec1" and
"$vec2".
In fact multiplying two binary numbers with
""n"" bits may yield a
result which is at most
""2n"" bits long.
Therefore, it is usually a good idea to let bit vector
"$vec3" have twice the size of bit
vector "$vec1" and
"$vec2", unless you are absolutely
sure that the result will fit into a bit vector of the same size as the
two factors.
If you are wrong, a fatal "numeric overflow error"
will occur.
Finally, note that in-place processing is possible, i.e.,
"$vec3" may be identical with
"$vec1" or
"$vec2", or both.
- "$quot->Divide($vec1,$vec2,$rest);"
This method divides the two numbers contained in bit vector
"$vec1" and
"$vec2" and stores the quotient in bit
vector "$quot" and the remainder in
bit vector "$rest".
I.e.,
$quot = $vec1 /
$vec2; # div
$rest = $vec1 %
$vec2; # mod
Therefore, "$quot" and
"$rest" must be two DISTINCT
bit vectors, or a fatal "result vector(s) must be distinct"
error will occur.
Note also that a fatal "division by zero error" will
occur if "$vec2" is equal to zero.
Note further that this method regards its arguments as
SIGNED.
If you want to make sure that a large number can never be
treated as being negative by mistake, make your bit vectors at least one
bit longer than the largest number you wish to represent, right from the
start, or proceed as follows:
$msb1 = $vec1->msb();
$msb2 = $vec2->msb();
$vec1->Resize($vec1->Size()+1);
$vec2->Resize($vec2->Size()+1);
$quot->Resize($quot->Size()+1);
$rest->Resize($rest->Size()+1);
$vec1->MSB($msb1);
$vec2->MSB($msb2);
$quot->Divide($vec1,$vec2,$rest);
Finally, note that in-place processing is possible, i.e.,
"$quot" may be identical with
"$vec1" or
"$vec2" or both, and
"$rest" may also be identical with
"$vec1" or
"$vec2" or both, as long as
"$quot" and
"$rest" are distinct. (!)
- "$vecgcd->GCD($veca,$vecb);"
This method calculates the "Greatest Common Divisor"
of the two numbers contained in bit vector
"$veca" and
"$vecb" and stores the result in bit
vector "$vecgcd".
The method uses Euklid's algorithm internally:
int GCD(int a, int b)
{
int t;
while (b != 0)
{
t = a % b; /* = remainder of (a div b) */
a = b;
b = t;
}
return(a);
}
Note that "GCD(z,0) == GCD(0,z) ==
z".
- "$vecgcd->GCD($vecx,$vecy,$veca,$vecb);"
This variant of the "GCD" method calculates the
"Greatest Common Divisor" of the two numbers contained in bit
vector "$veca" and
"$vecb" and stores the result in bit
vector "$vecgcd".
Moreover, it determines the two factors which are necessary in
order to represent the greatest common divisor as a linear combination
of its two arguments, i.e., the two factors
"x" and
"y" so that
"GCD(a,b) == x * a + y * b", and
stores them in bit vector "$vecx" and
"$vecy", respectively.
For example:
a = 2322
b = 654
GCD( 2322, 654 ) == 6
x = 20
y = -71
20 * 2322 - 71 * 654 == 6
Please see http://www.cut-the-knot.org/blue/extension.shtml
for an explanation of how this extension of Euklid's algorithm
works.
- "$vec3->Power($vec1,$vec2);"
This method calculates the exponentiation of base
"$vec1" elevated to the
"$vec2" power, i.e.,
""$vec1 ** $vec2"", and
stores the result in bit vector
"$vec3".
The method uses an efficient divide-and-conquer algorithm:
Suppose the exponent is (decimal) 13, for example. The binary
representation of this exponent is "1101".
This means we want to calculate
$vec1 * $vec1 * $vec1 * $vec1 * $vec1 * $vec1 * $vec1 * $vec1 *
$vec1 * $vec1 * $vec1 * $vec1 *
$vec1
That is, "$vec1" multiplied
with itself 13 times. The grouping into lines above is no coincidence.
The first line comprises 8 factors, the second contains 4, and the last
line just one. This just happens to be the binary representation of 13.
";-)"
We then calculate a series of squares (of squares of
squares...) of the base, i.e.,
$power[0] = $vec1;
$power[1] = $vec1 * $vec1;
$power[2] = $power[1] * $power[1];
$power[3] = $power[2] * $power[2];
etc.
To calculate the power of our example, we simply initialize
our result with 1 and consecutively multiply it with the items of the
series of powers we just calculated, if the corresponding bit of the
binary representation of the exponent is set:
$result = 1;
$result *= $power[0] if ($vec2 & 1);
$result *= $power[1] if ($vec2 & 2);
$result *= $power[2] if ($vec2 & 4);
$result *= $power[3] if ($vec2 & 8);
etc.
The bit vector "$vec3" must
be of the same size as the base
"$vec1" or greater.
"$vec3" and
"$vec1" may be the same vector (i.e.,
in-place calculation as in ""$vec1 **=
$vec2;"" is possible), but
"$vec3" and
"$vec2" must be distinct. Finally, the
exponent "$vec2" must be positive. A
fatal error occurs if any of these conditions is not met.
- "$vector->Block_Store($buffer);"
This method allows you to load the contents of a given bit
vector in one go.
This is useful when you store the contents of a bit vector in
a file, for instance (using method
""Block_Read()""), and when
you want to restore the previously saved bit vector.
For this, "$buffer"
MUST be a string (NO automatic conversion from numeric to
string is provided here as would normally in Perl!) containing the bit
vector in "low order byte first" order.
If the given string is shorter than what is needed to
completely fill the given bit vector, the remaining (most significant)
bytes of the bit vector are filled with zeros, i.e., the previous
contents of the bit vector are always erased completely.
If the given string is longer than what is needed to
completely fill the given bit vector, the superfluous bytes are simply
ignored.
See "sysread" in perlfunc for how to read in the
contents of "$buffer" from a file
prior to passing it to this method.
- "$buffer = $vector->Block_Read();"
This method allows you to export the contents of a given bit
vector in one block.
This is useful when you want to save the contents of a bit
vector for later, for instance in a file.
The advantage of this method is that it allows you to do so in
the compactest possible format, in binary.
The method returns a Perl string which contains an exact copy
of the contents of the given bit vector in "low order byte
first" order.
See "syswrite" in perlfunc for how to write the data
from this string to a file.
- "$size = $vector->Word_Size();"
Each bit vector is internally organized as an array of machine
words.
The methods whose names begin with "Word_" allow you
to access this internal array of machine words.
Note that because the size of a machine word may vary from
system to system, these methods are inherently
MACHINE-DEPENDENT!
Therefore, DO NOT USE these methods unless you are
absolutely certain that portability of your code is not an issue!
You have been warned!
To be machine-independent, use the methods whose names begin
with ""Chunk_"" instead,
with chunk sizes no greater than 32 bits.
The method
""Word_Size()"" returns the
number of machine words that the internal array of words of the given
bit vector contains.
This is similar in function to the term
""scalar(@array)"" for a
Perl array.
- "$vector->Word_Store($offset,$word);"
This method allows you to store a given value
"$word" at a given position
"$offset" in the internal array of
words of the given bit vector.
Note that "$offset" must lie
in the permitted range between "0" and
""$vector->Word_Size()-1"",
or a fatal "offset out of range" error will occur.
This method is similar in function to the expression
""$array[$offset] = $word;""
for a Perl array.
- "$word =
$vector->Word_Read($offset);"
This method allows you to access the value of a given machine
word at position "$offset" in the
internal array of words of the given bit vector.
Note that "$offset" must lie
in the permitted range between "0" and
""$vector->Word_Size()-1"",
or a fatal "offset out of range" error will occur.
This method is similar in function to the expression
""$word = $array[$offset];""
for a Perl array.
- "$vector->Word_List_Store(@words);"
This method allows you to store a list of values
"@words" in the internal array of
machine words of the given bit vector.
Thereby the LEFTMOST value in the list
("$words[0]") is stored in the
LEAST significant word of the internal array of words (the one
with offset "0"), the next value from
the list ("$words[1]") is stored in
the word with offset "1", and so on,
as intuitively expected.
If the list "@words"
contains fewer elements than the internal array of words of the given
bit vector contains machine words, the remaining (most significant)
words are filled with zeros.
If the list "@words"
contains more elements than the internal array of words of the given bit
vector contains machine words, the superfluous values are simply
ignored.
This method is comparable in function to the expression
""@array = @words;"" for a
Perl array.
- "@words = $vector->Word_List_Read();"
This method allows you to retrieve the internal array of
machine words of the given bit vector all at once.
Thereby the LEFTMOST value in the returned list
("$words[0]") is the LEAST
significant word from the given bit vector, and the RIGHTMOST
value in the returned list
("$words[$#words]") is the MOST
significant word of the given bit vector.
This method is similar in function to the expression
""@words = @array;"" for a
Perl array.
- "$vector->Word_Insert($offset,$count);"
This method inserts "$count"
empty new machine words at position
"$offset" in the internal array of
words of the given bit vector.
The "$count" most
significant words are lost, and all words starting with word number
"$offset" up to and including word
number
""$vector->Word_Size()-$count-1""
are moved up by "$count" places.
The now vacant "$count"
words starting at word number
"$offset" (up to and including word
number ""$offset+$count-1"")
are then set to zero (cleared).
Note that this method does NOT increase the size of the
given bit vector, i.e., the bit vector is NOT extended at its
upper end to "rescue" the
"$count" uppermost (most significant)
words - instead, these words are lost forever.
If you don't want this to happen, you have to increase the
size of the given bit vector EXPLICITLY and BEFORE you
perform the "Insert" operation, with a statement such as the
following:
$vector->Resize($vector->Size() + $count * Bit::Vector->Word_Bits());
Note also that "$offset"
must lie in the permitted range between
"0" and
""$vector->Word_Size()-1"",
or a fatal "offset out of range" error will occur.
If the term ""$offset +
$count"" exceeds
""$vector->Word_Size()-1"",
all the words starting with word number
"$offset" up to word number
""$vector->Word_Size()-1""
are simply cleared.
- "$vector->Word_Delete($offset,$count);"
This method deletes, i.e., removes the words starting at
position "$offset" up to and including
word number
""$offset+$count-1"" from
the internal array of machine words of the given bit vector.
The remaining uppermost words (starting at position
""$offset+$count"" up to and
including word number
""$vector->Word_Size()-1"")
are moved down by "$count" places.
The now vacant uppermost (most significant)
"$count" words are then set to zero
(cleared).
Note that this method does NOT decrease the size of the
given bit vector, i.e., the bit vector is NOT clipped at its
upper end to "get rid of" the vacant
"$count" uppermost words.
If you don't want this, i.e., if you want the bit vector to
shrink accordingly, you have to do so EXPLICITLY and AFTER
the "Delete" operation, with a couple of statements such as
these:
$bits = $vector->Size();
$count *= Bit::Vector->Word_Bits();
if ($count > $bits) { $count = $bits; }
$vector->Resize($bits - $count);
Note also that "$offset"
must lie in the permitted range between
"0" and
""$vector->Word_Size()-1"",
or a fatal "offset out of range" error will occur.
If the term ""$offset +
$count"" exceeds
""$vector->Word_Size()-1"",
all the words starting with word number
"$offset" up to word number
""$vector->Word_Size()-1""
are simply cleared.
- "$vector->Chunk_Store($chunksize,$offset,$chunk);"
This method allows you to set more than one bit at a time with
different values.
You can access chunks (i.e., ranges of contiguous bits)
between one and at most
""Bit::Vector->Long_Bits()""
bits wide.
In order to be portable, though, you should never use chunk
sizes larger than 32 bits.
If the given "$chunksize"
does not lie between "1" and
""Bit::Vector->Long_Bits()"",
a fatal "chunk size out of range" error will occur.
The method copies the
"$chunksize" least significant bits
from the value "$chunk" to the given
bit vector, starting at bit position
"$offset" and proceeding upwards until
bit number
""$offset+$chunksize-1"".
(I.e., bit number "0" of
"$chunk" becomes bit number
"$offset" in the given bit vector, and
bit number ""$chunksize-1""
becomes bit number
""$offset+$chunksize-1"".)
If the term
""$offset+$chunksize-1""
exceeds
""$vector->Size()-1"",
the corresponding superfluous (most significant) bits from
"$chunk" are simply ignored.
Note that "$offset" itself
must lie in the permitted range between
"0" and
""$vector->Size()-1"", or
a fatal "offset out of range" error will occur.
This method (as well as the other
""Chunk_"" methods) is
useful, for example, when you are reading in data in chunks of, say, 8
bits, which you need to access later, say, using 16 bits at a time (like
audio CD wave files, for instance).
- "$chunk =
$vector->Chunk_Read($chunksize,$offset);"
This method allows you to read the values of more than one bit
at a time.
You can read chunks (i.e., ranges of contiguous bits) between
one and at most
""Bit::Vector->Long_Bits()""
bits wide.
In order to be portable, though, you should never use chunk
sizes larger than 32 bits.
If the given "$chunksize"
does not lie between "1" and
""Bit::Vector->Long_Bits()"",
a fatal "chunk size out of range" error will occur.
The method returns the
"$chunksize" bits from the given bit
vector starting at bit position
"$offset" and proceeding upwards until
bit number
""$offset+$chunksize-1"".
(I.e., bit number "$offset"
of the given bit vector becomes bit number
"0" of the returned value, and bit
number
""$offset+$chunksize-1""
becomes bit number
""$chunksize-1"".)
If the term
""$offset+$chunksize-1""
exceeds
""$vector->Size()-1"",
the non-existent bits are simply not returned.
Note that "$offset" itself
must lie in the permitted range between
"0" and
""$vector->Size()-1"", or
a fatal "offset out of range" error will occur.
- "$vector->Chunk_List_Store($chunksize,@chunks);"
This method allows you to fill the given bit vector with a
list of data packets ("chunks") of any size
("$chunksize") you like (within
certain limits).
In fact the given
"$chunksize" must lie in the range
between "1" and
""Bit::Vector->Long_Bits()"",
or a fatal "chunk size out of range" error will occur.
In order to be portable, though, you should never use chunk
sizes larger than 32 bits.
The given bit vector is thereby filled in ascending order: The
first chunk from the list (i.e.,
"$chunks[0]") fills the
"$chunksize" least significant bits,
the next chunk from the list
("$chunks[1]") fills the bits number
"$chunksize" to number
""2*$chunksize-1"", the
third chunk ("$chunks[2]") fills the
bits number
""2*$chunksize"", to number
""3*$chunksize-1"", and so
on.
If there a less chunks in the list than are needed to fill the
entire bit vector, the remaining (most significant) bits are cleared,
i.e., the previous contents of the given bit vector are always erased
completely.
If there are more chunks in the list than are needed to fill
the entire bit vector, and/or if a chunk extends beyond
""$vector->Size()-1""
(which happens whenever
""$vector->Size()"" is
not a multiple of "$chunksize"), the
superfluous chunks and/or bits are simply ignored.
The method is useful, for example (and among many other
applications), for the conversion of packet sizes in a data stream.
This method can also be used to store an octal string in a
given bit vector:
$vector->Chunk_List_Store(3, split(//, reverse $string));
Note however that unlike the conversion methods
""from_Hex()"",
""from_Bin()"",
""from_Dec()"" and
""from_Enum()"", this
statement does not include any syntax checking, i.e., it may fail
silently, without warning.
To perform syntax checking, add the following statements:
if ($string =~ /^[0-7]+$/)
{
# okay, go ahead with conversion as shown above
}
else
{
# error, string contains other than octal characters
}
Another application is to store a repetitive pattern in a
given bit vector:
$pattern = 0xDEADBEEF;
$length = 32; # = length of $pattern in bits
$size = $vector->Size();
$factor = int($size / $length);
if ($size % $length) { $factor++; }
$vector->Chunk_List_Store($length, ($pattern) x $factor);
- "@chunks =
$vector->Chunk_List_Read($chunksize);"
This method allows you to access the contents of the given bit
vector in form of a list of data packets ("chunks") of a size
("$chunksize") of your choosing
(within certain limits).
In fact the given
"$chunksize" must lie in the range
between "1" and
""Bit::Vector->Long_Bits()"",
or a fatal "chunk size out of range" error will occur.
In order to be portable, though, you should never use chunk
sizes larger than 32 bits.
The given bit vector is thereby read in ascending order: The
"$chunksize" least significant bits
(bits number "0" to
""$chunksize-1"") become the
first chunk in the returned list (i.e.,
"$chunks[0]"). The bits number
"$chunksize" to
""2*$chunksize-1"" become
the next chunk in the list
("$chunks[1]"), and so on.
If
""$vector->Size()"" is
not a multiple of "$chunksize", the
last chunk in the list will contain fewer bits than
"$chunksize".
BEWARE that for large bit vectors and/or small values
of "$chunksize", the number of
returned list elements can be extremely large! BE CAREFUL!
You could blow up your application with lack of memory (each
list element is a full-grown Perl scalar, internally, with an associated
memory overhead for its administration!) or at least cause a noticeable,
more or less long-lasting "freeze" of your application!
Possible applications:
The method is especially useful in the conversion of packet
sizes in a data stream.
This method can also be used to convert a given bit vector to
a string of octal numbers:
$string = reverse join('', $vector->Chunk_List_Read(3));
- "$vector->Index_List_Remove(@indices);"
This method allows you to specify a list of indices of bits
which should be turned off in the given bit vector.
In fact this method is a shortcut for
foreach $index (@indices)
{
$vector->Bit_Off($index);
}
In contrast to all other import methods in this module, this
method does NOT clear the given bit vector before processing its
list of arguments.
Instead, this method allows you to accumulate the results of
various consecutive calls.
(The same holds for the method
""Index_List_Store()"". As a
consequence, you can "wipe out" what you did using the method
""Index_List_Remove()"" by
passing the identical argument list to the method
""Index_List_Store()"".)
- "$vector->Index_List_Store(@indices);"
This method allows you to specify a list of indices of bits
which should be turned on in the given bit vector.
In fact this method is a shortcut for
foreach $index (@indices)
{
$vector->Bit_On($index);
}
In contrast to all other import methods in this module, this
method does NOT clear the given bit vector before processing its
list of arguments.
Instead, this method allows you to accumulate the results of
various consecutive calls.
(The same holds for the method
""Index_List_Remove()"". As
a consequence, you can "wipe out" what you did using the
method
""Index_List_Store()"" by
passing the identical argument list to the method
""Index_List_Remove()"".)
- "@indices =
$vector->Index_List_Read();"
This method returns a list of Perl scalars.
The list contains one scalar for each set bit in the given bit
vector.
BEWARE that for large bit vectors, this can result in a
literally overwhelming number of list elements! BE CAREFUL! You
could run out of memory or slow down your application considerably!
Each scalar contains the number of the index corresponding to
the bit in question.
These indices are always returned in ascending order.
If the given bit vector is empty (contains only cleared bits)
or if it has a length of zero (if it contains no bits at all), the
method returns an empty list.
This method can be useful, for instance, to obtain a list of
prime numbers:
$limit = 1000; # or whatever
$vector = Bit::Vector->new($limit+1);
$vector->Primes();
@primes = $vector->Index_List_Read();
- "$vec3->Or($vec1,$vec2);"
"$set3->Union($set1,$set2);"
This method calculates the union of
"$set1" and
"$set2" and stores the result in
"$set3".
This is usually written as ""$set3
= $set1 u $set2"" in set theory (where "u" is
the "cup" operator).
(On systems where the "cup" character is unavailable
this operator is often denoted by a plus sign "+".)
In-place calculation is also possible, i.e.,
"$set3" may be identical with
"$set1" or
"$set2" or both.
- "$vec3->And($vec1,$vec2);"
"$set3->Intersection($set1,$set2);"
This method calculates the intersection of
"$set1" and
"$set2" and stores the result in
"$set3".
This is usually written as ""$set3
= $set1 n $set2"" in set theory (where "n" is
the "cap" operator).
(On systems where the "cap" character is unavailable
this operator is often denoted by an asterisk "*".)
In-place calculation is also possible, i.e.,
"$set3" may be identical with
"$set1" or
"$set2" or both.
- "$vec3->AndNot($vec1,$vec2);"
"$set3->Difference($set1,$set2);"
This method calculates the difference of
"$set1" less
"$set2" and stores the result in
"$set3".
This is usually written as ""$set3
= $set1 \ $set2"" in set theory (where "\" is
the "less" operator).
In-place calculation is also possible, i.e.,
"$set3" may be identical with
"$set1" or
"$set2" or both.
- "$vec3->Xor($vec1,$vec2);"
"$set3->ExclusiveOr($set1,$set2);"
This method calculates the symmetric difference of
"$set1" and
"$set2" and stores the result in
"$set3".
This can be written as ""$set3 =
($set1 u $set2) \ ($set1 n $set2)"" in set theory (the
union of the two sets less their intersection).
When sets are implemented as bit vectors then the above
formula is equivalent to the exclusive-or between corresponding bits of
the two bit vectors (hence the name of this method).
Note that this method is also much more efficient than
evaluating the above formula explicitly since it uses a built-in machine
language instruction internally.
In-place calculation is also possible, i.e.,
"$set3" may be identical with
"$set1" or
"$set2" or both.
- "$vec2->Not($vec1);"
"$set2->Complement($set1);"
This method calculates the complement of
"$set1" and stores the result in
"$set2".
In "big integer" arithmetic, this is equivalent to
calculating the one's complement of the number stored in the bit vector
"$set1" in binary representation.
In-place calculation is also possible, i.e.,
"$set2" may be identical with
"$set1".
- "if ($set1->subset($set2))"
Returns "true"
("1") if
"$set1" is a subset of
"$set2" (i.e., completely contained in
"$set2") and "false"
("0") otherwise.
This means that any bit which is set
("1") in
"$set1" must also be set in
"$set2", but
"$set2" may contain set bits which are
not set in "$set1", in order for the
condition of subset relationship to be true between these two sets.
Note that by definition, if two sets are identical, they are
also subsets (and also supersets) of each other.
- "$norm = $set->Norm();"
Returns the norm (number of bits which are set) of the given
vector.
This is equivalent to the number of elements contained in the
given set.
Uses a byte lookup table for calculating the number of set
bits per byte, and thus needs a time for evaluation (and a number of
loops) linearly proportional to the length of the given bit vector (in
bytes).
This should be the fastest algorithm on average.
- "$norm = $set->Norm2();"
Returns the norm (number of bits which are set) of the given
vector.
This is equivalent to the number of elements contained in the
given set.
This does the same as the method
""Norm()"" above, only with
a different algorithm:
This method counts the number of set and cleared bits at the
same time and will stop when either of them has been exhausted, thus
needing at most half as many loops per machine word as the total number
of bits in a machine word - in fact it will need a number of loops equal
to the minimum of the number of set bits and the number of cleared
bits.
This might be a faster algorithm than of the method
""Norm()"" above on some
systems, depending on the system's architecture and the compiler and
optimisation used, for bit vectors with sparse set bits and for bit
vectors with sparse cleared bits (i.e., predominantly set bits).
- "$norm = $set->Norm3();"
Returns the norm (number of bits which are set) of the given
vector.
This is equivalent to the number of elements contained in the
given set.
This does the same as the two methods
""Norm()"" and
""Norm2()"" above, however
with a different algorithm.
In fact this is the implementation of the method
""Norm()"" used in previous
versions of this module.
The method needs a number of loops per machine word equal to
the number of set bits in that machine word.
Only for bit vectors with sparse set bits will this method be
fast; it will depend on a system's architecture and compiler whether the
method will be faster than any of the two methods above in such
cases.
On average however, this is probably the slowest method of the
three.
- "$min = $set->Min();"
Returns the minimum of the given set, i.e., the minimum of all
indices of all set bits in the given bit vector
"$set".
If the set is empty (no set bits), plus infinity (represented
by the constant "MAX_LONG" on your system) is returned.
(This constant is usually
2 ^ (n-1) - 1, where
""n"" is the number of bits
of an unsigned long on your machine.)
- "$max = $set->Max();"
Returns the maximum of the given set, i.e., the maximum of all
indices of all set bits in the given bit vector
"$set".
If the set is empty (no set bits), minus infinity (represented
by the constant "MIN_LONG" on your system) is returned.
(This constant is usually
-(2 ^ (n-1) - 1) or
-(2 ^ (n-1)), where
""n"" is the number of bits
of an unsigned long on your machine.)
- "$m3->Multiplication($r3,$c3,$m1,$r1,$c1,$m2,$r2,$c2);"
This method multiplies two boolean matrices (stored as bit
vectors) "$m1" and
"$m2" and stores the result in matrix
"$m3".
The method uses the binary "xor" operation
(""^"") as the boolean
addition operator
(""+"").
An exception is raised if the product of the number of rows
and columns of any of the three matrices differs from the actual size of
their underlying bit vector.
An exception is also raised if the numbers of rows and columns
of the three matrices do not harmonize in the required manner:
rows3 == rows1
cols3 == cols2
cols1 == rows2
This method is used by the module
"Math::MatrixBool".
See Math::MatrixBool(3) for details.
- "$m3->Product($r3,$c3,$m1,$r1,$c1,$m2,$r2,$c2);"
This method multiplies two boolean matrices (stored as bit
vectors) "$m1" and
"$m2" and stores the result in matrix
"$m3".
This special method uses the binary "or" operation
(""|"") as the boolean
addition operator
(""+"").
An exception is raised if the product of the number of rows
and columns of any of the three matrices differs from the actual size of
their underlying bit vector.
An exception is also raised if the numbers of rows and columns
of the three matrices do not harmonize in the required manner:
rows3 == rows1
cols3 == cols2
cols1 == rows2
This method is used by the module
"Math::MatrixBool".
See Math::MatrixBool(3) for details.
- "$matrix->Closure($rows,$cols);"
This method calculates the reflexive transitive closure of the
given boolean matrix (stored as a bit vector) using Kleene's
algoritm.
(See Math::Kleene(3) for a brief introduction into the
theory behind Kleene's algorithm.)
The reflexive transitive closure answers the question whether
a path exists between any two vertices of a graph whose edges are given
as a matrix:
If a (directed) edge exists going from vertex "i" to
vertex "j", then the element in the matrix with coordinates
(i,j) is set to "1" (otherwise it
remains set to "0").
If the edges are undirected, the resulting matrix is
symmetric, i.e., elements (i,j) and (j,i) always contain the same
value.
The matrix representing the edges of the graph only answers
the question whether an EDGE exists between any two vertices of
the graph or not, whereas the reflexive transitive closure answers the
question whether a PATH (a series of adjacent edges) exists
between any two vertices of the graph!
Note that the contents of the given matrix are modified by
this method, so make a copy of the initial matrix in time if you are
going to need it again later.
An exception is raised if the given matrix is not quadratic,
i.e., if the number of rows and columns of the given matrix is not
identical.
An exception is also raised if the product of the number of
rows and columns of the given matrix differs from the actual size of its
underlying bit vector.
This method is used by the module
"Math::MatrixBool".
See Math::MatrixBool(3) for details.
- "$matrix2->Transpose($rows2,$cols2,$matrix1,$rows1,$cols1);"
This method calculates the transpose of a boolean matrix
"$matrix1" (stored as a bit vector)
and stores the result in matrix
"$matrix2".
The transpose of a boolean matrix, representing the edges of a
graph, can be used for finding the strongly connected components of that
graph.
An exception is raised if the product of the number of rows
and columns of any of the two matrices differs from the actual size of
its underlying bit vector.
An exception is also raised if the following conditions are
not met:
rows2 == cols1
cols2 == rows1
Note that in-place processing
("$matrix1" and
"$matrix2" are identical) is only
possible if the matrix is quadratic. Otherwise, a fatal "matrix is
not quadratic" error will occur.
This method is used by the module
"Math::MatrixBool".
See Math::MatrixBool(3) for details.