NAME
Bit::Vector - efficient base class implementing bit vectors
This module implements bit vectors of arbitrary size and provides efficient methods for handling them.
This goes far beyond the built-in capabilities of Perl for handling bit vectors (compare with the method list below).
Moreover, the C core of this module can be used "stand-alone" in other C applications; Perl is not necessarily required.
The module is intended to serve as a base class for other applications or application classes, such as implementing sets or performing big integer arithmetic.
All methods are implemented in C internally for maximum performance.
The module also provides overloaded arithmetic and relational operators for maximum ease of use (Perl only).
(Note that there is (of course) a little speed penalty to pay for overloaded operators. If speed is crucial, use the methods of this module directly instead of their corresponding overloaded operators!)
SYNOPSIS
CLASS METHODS (implemented in C)
Version
$version = Bit::Vector->Version();
Word_Bits
$bits = Bit::Vector->Word_Bits(); # bits in a machine word
Long_Bits
$bits = Bit::Vector->Long_Bits(); # bits in an unsigned long
new
$vector = Bit::Vector->new($bits); # bit vector constructor
Concat_List
$vector = Bit::Vector->Concat_List(@vectors);OBJECT METHODS (implemented in C)
new
$vec2 = $vec1->new($bits); # alternative call of constructor
Shadow
$vec2 = $vec1->Shadow(); # new vector, same size but empty
Clone
$vec2 = $vec1->Clone(); # new vector, exact duplicate
Concat
$vector = $vec1->Concat($vec2);
Concat_List
$vector = $vec1->Concat_List($vec2,$vec3,...);
Size
$bits = $vector->Size();
Resize
$vector->Resize($bits);
$vector->Resize($vector->Size()+5);
$vector->Resize($vector->Size()-5);
Copy
$vec2->Copy($vec1);
Empty
$vector->Empty();
Fill
$vector->Fill();
Flip
$vector->Flip();
Primes
$vector->Primes(); # Sieve of Erathostenes
Reverse
$vec2->Reverse($vec1);
Interval_Empty
$vector->Interval_Empty($min,$max);
Interval_Fill
$vector->Interval_Fill($min,$max);
Interval_Flip
$vector->Interval_Flip($min,$max);
Interval_Reverse
$vector->Interval_Reverse($min,$max);
Interval_Scan_inc
if (($min,$max) = $vector->Interval_Scan_inc($start))
Interval_Scan_dec
if (($min,$max) = $vector->Interval_Scan_dec($start))
Interval_Copy
$vec2->Interval_Copy($vec1,$offset2,$offset1,$length);
Interval_Substitute
$vec2->Interval_Substitute($vec1,$off2,$len2,$off1,$len1);
is_empty
if ($vector->is_empty())
is_full
if ($vector->is_full())
equal
if ($vec1->equal($vec2))
Lexicompare (unsigned)
if ($vec1->Lexicompare($vec2) == 0)
if ($vec1->Lexicompare($vec2) != 0)
if ($vec1->Lexicompare($vec2) < 0)
if ($vec1->Lexicompare($vec2) <= 0)
if ($vec1->Lexicompare($vec2) > 0)
if ($vec1->Lexicompare($vec2) >= 0)
Compare (signed)
if ($vec1->Compare($vec2) == 0)
if ($vec1->Compare($vec2) != 0)
if ($vec1->Compare($vec2) < 0)
if ($vec1->Compare($vec2) <= 0)
if ($vec1->Compare($vec2) > 0)
if ($vec1->Compare($vec2) >= 0)
to_Hex
$string = $vector->to_Hex();
from_hex
$ok = $vector->from_hex($string);
to_Bin
$string = $vector->to_Bin();
from_bin
$ok = $vector->from_bin($string);
to_Dec
$string = $vector->to_Dec();
from_dec
$ok = $vector->from_dec($string);
to_Enum
$string = $vector->to_Enum(); # e.g. "2,3,5-7,11,13-19"
from_enum
$ok = $vector->from_enum($string);
Bit_Off
$vector->Bit_Off($index);
Bit_On
$vector->Bit_On($index);
bit_flip
$bit = $vector->bit_flip($index);
bit_test, contains
$bit = $vector->bit_test($index);
$bit = $vector->contains($index);
if ($vector->bit_test($index))
if ($vector->contains($index))
Bit_Copy
$vector->Bit_Copy($index,$bit);
lsb (least significant bit)
$bit = $vector->lsb();
msb (most significant bit)
$bit = $vector->msb();
rotate_left
$carry = $vector->rotate_left();
rotate_right
$carry = $vector->rotate_right();
shift_left
$carry = $vector->shift_left($carry);
shift_right
$carry = $vector->shift_right($carry);
Move_Left
$vector->Move_Left($bits); # shift left "$bits" positions
Move_Right
$vector->Move_Right($bits); # shift right "$bits" positions
Insert
$vector->Insert($offset,$bits);
Delete
$vector->Delete($offset,$bits);
increment
$carry = $vector->increment();
decrement
$carry = $vector->decrement();
add
$carry = $vec3->add($vec1,$vec2,$carry);
subtract
$carry = $vec3->subtract($vec1,$vec2,$carry);
Negate
$vec2->Negate($vec1);
Absolute
$vec2->Absolute($vec1);
Sign
if ($vector->Sign() == 0)
if ($vector->Sign() != 0)
if ($vector->Sign() < 0)
if ($vector->Sign() <= 0)
if ($vector->Sign() > 0)
if ($vector->Sign() >= 0)
Multiply
$vec3->Multiply($vec1,$vec2);
Divide
$quot->Divide($vec1,$vec2,$rest);
GCD (Greatest Common Divisor)
$vec3->GCD($vec1,$vec2);
Block_Store
$vector->Block_Store($buffer);
Block_Read
$buffer = $vector->Block_Read();
Word_Size
$size = $vector->Word_Size(); # number of words in "$vector"
Word_Store
$vector->Word_Store($offset,$word);
Word_Read
$word = $vector->Word_Read($offset);
Word_List_Store
$vector->Word_List_Store(@words);
Word_List_Read
@words = $vector->Word_List_Read();
Word_Insert
$vector->Word_Insert($offset,$count);
Word_Delete
$vector->Word_Delete($offset,$count);
Chunk_Store
$vector->Chunk_Store($chunksize,$offset,$chunk);
Chunk_Read
$chunk = $vector->Chunk_Read($chunksize,$offset);
Chunk_List_Store
$vector->Chunk_List_Store($chunksize,@chunks);
Chunk_List_Read
@chunks = $vector->Chunk_List_Read($chunksize);
Index_List_Remove
$vector->Index_List_Remove(@indices);
Index_List_Store
$vector->Index_List_Store(@indices);
Index_List_Read
@indices = $vector->Index_List_Read();
Union
$set3->Union($set1,$set2);
Intersection
$set3->Intersection($set1,$set2);
Difference
$set3->Difference($set1,$set2);
ExclusiveOr
$set3->ExclusiveOr($set1,$set2);
Complement
$set2->Complement($set1);
subset
if ($set1->subset($set2)) # true if $set1 is subset of $set2
Norm
$norm = $set->Norm();
Min
$min = $set->Min();
Max
$max = $set->Max();
Multiplication
$matrix3->Multiplication($rows3,$cols3,
$matrix1,$rows1,$cols1,
$matrix2,$rows2,$cols2);
Closure
$matrix->Closure($rows,$cols);
Transpose
$matrix2->Transpose($rows2,$cols2,$matrix1,$rows1,$cols1);CLASS METHODS (implemented in Perl)
Configuration
$config = Bit::Vector->Configuration();
Bit::Vector->Configuration($config);
$oldconfig = Bit::Vector->Configuration($newconfig);OVERLOADED OPERATORS (implemented in Perl)
String Conversion
$string = "$vector"; # depending on configuration
print "\$vector = '$vector'\n";
Emptyness
if ($vector) # if not empty (non-zero)
if (! $vector) # if empty (zero)
unless ($vector) # if empty (zero)
Complement (one's complement)
$vector2 = ~$vector1;
$vector = ~$vector;
Negation (two's complement)
$vector2 = -$vector1;
$vector = -$vector;
Norm
$norm = abs($vector); # depending on configuration
Absolute
$vector2 = abs($vector1); # depending on configuration
Concatenation
$vector3 = $vector1 . $vector2;
$vector1 .= $vector2;
$vector1 = $vector2 . $vector1;
$vector2 = $vector1 . $scalar; # depending on configuration
$vector2 = $scalar . $vector1;
$vector .= $scalar;
Duplication
$vector2 = $vector1 x $factor;
$vector x= $factor;
Shift Left
$vector2 = $vector1 << $bits;
$vector <<= $bits;
Shift Right
$vector2 = $vector1 >> $bits;
$vector >>= $bits;
Union
$vector3 = $vector1 | $vector2;
$vector1 |= $vector2;
$vector2 = $vector1 | $scalar;
$vector |= $scalar;
$vector3 = $vector1 + $vector2; # depending on configuration
$vector1 += $vector2;
$vector2 = $vector1 + $scalar;
$vector += $scalar;
Intersection
$vector3 = $vector1 & $vector2;
$vector1 &= $vector2;
$vector2 = $vector1 & $scalar;
$vector &= $scalar;
$vector3 = $vector1 * $vector2; # depending on configuration
$vector1 *= $vector2;
$vector2 = $vector1 * $scalar;
$vector *= $scalar;
ExclusiveOr
$vector3 = $vector1 ^ $vector2;
$vector1 ^= $vector2;
$vector2 = $vector1 ^ $scalar;
$vector ^= $scalar;
Set Difference
$vector3 = $vector1 - $vector2; # depending on configuration
$vector1 -= $vector2;
$vector1 = $vector2 - $vector1;
$vector2 = $vector1 - $scalar;
$vector2 = $scalar - $vector1;
$vector -= $scalar;
Addition
$vector3 = $vector1 + $vector2; # depending on configuration
$vector1 += $vector2;
$vector2 = $vector1 + $scalar;
$vector += $scalar;
Subtraction
$vector3 = $vector1 - $vector2; # depending on configuration
$vector1 -= $vector2;
$vector1 = $vector2 - $vector1;
$vector2 = $vector1 - $scalar;
$vector2 = $scalar - $vector1;
$vector -= $scalar;
Multiplication
$vector3 = $vector1 * $vector2; # depending on configuration
$vector1 *= $vector2;
$vector2 = $vector1 * $scalar;
$vector *= $scalar;
Division
$vector3 = $vector1 / $vector2;
$vector1 /= $vector2;
$vector1 = $vector2 / $vector1;
$vector2 = $vector1 / $scalar;
$vector2 = $scalar / $vector1;
$vector /= $scalar;
Modulo
$vector3 = $vector1 % $vector2;
$vector1 %= $vector2;
$vector1 = $vector2 % $vector1;
$vector2 = $vector1 % $scalar;
$vector2 = $scalar % $vector1;
$vector %= $scalar;
Increment
++$vector;
$vector++;
Decrement
--$vector;
$vector--;
Lexical Comparison (unsigned)
$cmp = $vector1 cmp $vector2;
if ($vector1 lt $vector2)
if ($vector1 le $vector2)
if ($vector1 gt $vector2)
if ($vector1 ge $vector2)
$cmp = $vector cmp $scalar;
if ($vector lt $scalar)
if ($vector le $scalar)
if ($vector gt $scalar)
if ($vector ge $scalar)
Comparison (signed)
$cmp = $vector1 <=> $vector2;
if ($vector1 < $vector2) # depending on configuration
if ($vector1 <= $vector2)
if ($vector1 > $vector2)
if ($vector1 >= $vector2)
$cmp = $vector <=> $scalar;
if ($vector < $scalar) # depending on configuration
if ($vector <= $scalar)
if ($vector > $scalar)
if ($vector >= $scalar)
Equality
if ($vector1 eq $vector2)
if ($vector1 ne $vector2)
if ($vector eq $scalar)
if ($vector ne $scalar)
if ($vector1 == $vector2)
if ($vector1 != $vector2)
if ($vector == $scalar)
if ($vector != $scalar)
Subset Relationship
if ($vector1 <= $vector2) # depending on configuration
True Subset Relationship
if ($vector1 < $vector2) # depending on configuration
Superset Relationship
if ($vector1 >= $vector2) # depending on configuration
True Superset Relationship
if ($vector1 > $vector2) # depending on configurationIMPORTANT NOTES
Method naming conventions
Method names completely in lower case indicate a boolean return value.
(Except for the bit vector constructor method "
new()", of course.)Boolean values
Boolean values in this module are always a numeric zero ("0") for "false" and a numeric one ("1") for "true".
Negative numbers
All numeric input parameters passed to any of the methods of this module or (in general, but see below) to overloaded operators are regarded as being UNSIGNED.
This affects overloaded operators only where numeric factors (as with "
<<", ">>" and "x") are concerned or when the configuration (see also the section "Overloaded operators configuration" immediately below) states that numeric input (which comes in place of one of the two bit vector object operands the overloaded operator expects) is to be regarded as bit indices (which is the default, however).As a consequence, whenever you pass a negative number as an argument to some method of this module (or an overloaded operator - under the conditions explained above), it will be treated as a (usually very large) positive number due to its internal two's complement binary representation, usually resulting in an "index out of range" error message and program abortion.
Note that this does not apply to "big integer" decimal numbers, which are (usually) passed as strings, and which may of course be negative (see also the section "Big integers" a little further below).
Overloaded operators configuration
Note that the behaviour of certain overloaded operators can be changed in various ways by means of the "
Configuration()" method (for more details, see the description of this method further below).For instance, scalars (i.e., numbers and strings) provided as operands to overloaded operators are automatically converted to bit vectors, internally.
These scalars are thereby automatically assumed to be indices or to be in hexadecimal, binary, decimal or enumeration format, depending on the configuration.
Similarly, when converting bit vectors to strings using double quotes (""), the output format will also depend on the previously chosen configuration.
Finally, some overloaded operators may have different semantics depending on the proper configuration; for instance, the operator "+" can be the "union" operator from set theory or the arithmetic "add" operator.
In all cases (input, output and operator semantics), the defaults have been chosen in such a way so that the behaviour of the module is backward compatible with previous versions.
"Big integers"
As long as "big integers" (for "big integer" arithmetic) are small enough so that Perl doesn't need scientific notation (exponents) to be able to represent them internally, you can provide these "big integer" constants to the overloaded operators of this module (or to the method "
from_dec()") in numeric form (i.e., either as a numeric constant or expression or as a Perl variable containing a numeric value).Note that you will get an error message (resulting in program abortion) if your "big integer" numbers exceed that limit.
Because this limit is machine-dependent and not obvious to find out, it is strongly recommended that you enclose ALL your "big integer" constants in your programs in (double or single) quotes.
Examples:
$vector /= 10; # ok because number is small $vector /= -10; # ok for same reason $vector /= "10"; # always correct $vector += "1152921504606846976"; # quotes probably required hereAll examples assume
Bit::Vector->Configuration("input=decimal");having been set beforehand.
Note also that this module does not support scientific notation (exponents) for "big integer" decimal numbers because you can always make the bit vector large enough for the whole number to fit without loss of precision (as it would occur if scientific notation were used).
Finally, note that the only characters allowed in "big integer" constant strings are the digits
0..9and an optional leading sign ("+" or "-").All other characters produce a syntax error.
Valid operands for overloaded operators
All overloaded operators expect at least one bit vector operand, in order for the operator to "know" that not the usual operation is to be carried out, but rather the overloaded variant.
This is especially true for all unary operators:
"$vector" if ($vector) if (!$vector) ~$vector -$vector abs($vector) $vector++ ++$vector $vector-- --$vectorFor obvious reasons the left operand (the "lvalue") of all assignment operators is also required to be a bit vector:
.= x= <<= >>= |= &= ^= += -= *= /= %=In the case of three special operators, namely "
<<", ">>" and "x", as well as their related assignment variants, "<<=", ">>=" and "x=", the left operand is ALWAYS a bit vector and the right operand is ALWAYS a number (which is the factor indicating how many times the operator is to be applied).In all truly binary operators, i.e.,
. | & ^ + - * / % <=> cmp == eq != ne < lt <= le > gt >= geone of either operands may be replaced by a Perl scalar, i.e., a number or a string, either as a Perl constant, a Perl expression or a Perl variable yielding a number or a string.
The same applies to the right side operand (the "rvalue") of the remaining assignment operators, i.e.,
.= |= &= ^= += -= *= /= %=Note that this Perl scalar should be of the correct type, i.e., numeric or string, for the chosen configuration, because otherwise a warning message will occur if your program runs under the "
-w" switch of Perl.The acceptable scalar types for each possible configuration are the following:
input = bit indices (default) : numeric input = hexadecimal : string input = binary : string input = decimal : string (in general) input = decimal : numeric (if small enough) input = enumeration : stringNOTE ALSO THAT THESE SCALAR OPERANDS ARE CONVERTED TO BIT VECTORS OF THE SAME SIZE AS THE BIT VECTOR WHICH IS THE OTHER OPERAND.
The only exception from this rule are hexadecimal and binary strings in connection with the concatenation operator ("
."); these strings are converted to bit vectors of a size matching the length of the input string, i.e., four times the length for hexadecimal strings (because each hexadecimal digit is worth 4 bits) and once the length for binary strings.If a decimal number ("big integer") is too large to be stored in a bit vector of the given size, a "numeric overflow error" occurs.
If a bit index is out of range for the given bit vector, an "index out of range" error occurs.
If a scalar operand cannot be converted successfully (caused by invalid syntax, for instance), a fatal "scalar operand conversion error" is issued.
If the two operands of the operator "
<<", ">>" or "x" are reversed, a fatal "reversed operands error" occurs.If an operand is neither a bit vector nor a scalar, then a fatal "illegal operand type error" occurs.
Bit order
Note that bit vectors are stored least order bit and least order word first internally.
I.e., bit #0 of any given bit vector corresponds to bit #0 of word #0 in the array of machine words representing the bit vector.
(Where word #0 comes first in memory, i.e., it is stored at the least memory address in the allocated block of memory holding the given bit vector.)
Note however that machine words can be stored least order byte first or last, depending on your system's implementation.
When you are exporting or importing a whole bit vector at once using the methods "
Block_Read()" and "Block_Store()" (the only time in this module where this could make any difference), however, a conversion to and from "least order byte first" order is automatically supplied.In other words, what "
Block_Read()" provides and what "Block_Store()" expects is always in "least order byte first" order, regardless of the order in which words are stored internally on your machine.This is to make sure that what you export on one machine using "
Block_Read()" can always be read in correctly with "Block_Store()" on a different machine.Note further that whenever bit vectors are converted to and from (binary or hexadecimal) strings, the rightmost bit is always the least significant one, and the leftmost bit is always the most significant bit.
This is because in our western culture, numbers are always represented in this way (least significant to most significant digits go from right to left).
Of course this requires an internal reversion of order, which the corresponding conversion methods perform automatically (without any additional overhead).
"Word" related methods
Note that all methods whose names begin with "
Word_" are MACHINE-DEPENDENT!They depend on the size (number of bits) of an "unsigned int" (C type) on your machine.
Therefore, you should only use these methods if you are ABSOLUTELY CERTAIN that portability of your code is not an issue!
Note that you can use arbitrarily large chunks (i.e., fragments of bit vectors) of up to 32 bits IN A PORTABLE WAY using the methods whose names begin with "
Chunk_".Chunk sizes
Note that legal chunk sizes for all methods whose names begin with "
Chunk_" range from "1" to "Bit::Vector->Long_Bits();" bits ("0" is NOT allowed!).In order to make your programs portable, however, you shouldn't use chunk sizes larger than 32 bits, since this is the minimum size of an "unsigned long" (C type) on all systems, as prescribed by ANSI C.
Matching sizes
For all methods involving several bit vectors at the same time, except for the methods "
Concat()" and "Concat_List()", all bit vector arguments must have identical sizes (number of bits), or a fatal "size mismatch" error will occur.Index ranges
All indices for any given bits must lie between "
0" and "$vector->Size()-1", or a fatal "index out of range" error will occur.
DESCRIPTION
CLASS METHODS (implemented in C)
$version = Bit::Vector->Version();Returns the current version number of this module.
$bits = Bit::Vector->Word_Bits();Returns the number of bits of an "unsigned int" (C type) on your machine.
(An "unsigned int" is also called a "machine word", hence the name of this method.)
$bits = Bit::Vector->Long_Bits();Returns the number of bits of an "unsigned long" (C type) on your machine.
$vector = Bit::Vector->new($bits);This is the bit vector constructor method.
Call this method to create a new bit vector containing "
$bits" bits (with indices ranging from "0" to "$bits-1").Note that - in contrast to previous versions - bit vectors of length zero (i.e., with
$bits = 0) are permitted now.The method returns a reference to the newly created bit vector.
A new bit vector is always initialized so that all bits are cleared (turned off).
An exception will be raised if the method is unable to allocate the necessary memory.
Note 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, the bit vector constructor method will obediently attempt to create a bit vector of that size, probably resulting in an exception, as explained above.
$vector = Bit::Vector->Concat_List(@vectors);This method creates a new vector containing all bit vectors from the argument list in concatenated form.
The argument list may contain any number of arguments (including zero); the only condition is that all arguments must be bit vectors.
There is no condition concerning the length (in number of bits) of these arguments.
The vectors from the argument list are not changed in any way.
If the argument list is empty or if all arguments have length zero, the resulting bit vector will also have length zero.
Note that the rightmost bit vector from the argument list will become the least significant part of the resulting bit vector, and the leftmost bit vector from the argument list will become the most significant part of the resulting bit vector.
OBJECT METHODS (implemented in C)
$vec2 = $vec1->new();$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);$vector = $vec1->Concat_List($vec2,$vec3,...);$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.
$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);$vec2->Interval_Substitute($vec1,$off2,$len2,$off1,$len1);if ($vector->is_empty())Tests wether the given bit vector is empty, i.e., wether ALL of its bits are cleared (in the "off" state).
In "big integer arithmetic", this is equivalent to testing wether the number stored in the bit vector is zero ("0").
Returns "true" ("1") if the bit vector is empty and "false" ("0") otherwise.
if ($vector->is_full())Tests wether the given bit vector is full, i.e., wether ALL of its bits are set (in the "on" state).
In "big integer arithmetic", this is equivalent to testing wether 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 ($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 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.
Moreover, in order to simplify the conversion, the unused bits in the bit vector (if any) are also converted, which may produce some extra (but innocuous) leading hexadecimal zeros.
$ok = $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, an error ensues.
In such a case the bit vector is filled up with zeros starting at the point of the error (i.e., all remaining uppermost bits) and the method returns "false" ("0").
If all goes well the method returns "true" ("1").
$string = $vector->to_Bin();$ok = $vector->from_bin($string);$string = $vector->to_Dec();This method returns a string representing the contents of the given bit vector converted to decimal (base
10).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
10with remainder until the quotient becomes0(each remainder in turn represents a single decimal digit of the resulting string).This is also true for this method, even though considerable effort has been put into its implementation in order to speed it up: instead of repeatedly dividing by
10, the bit vector is repeatedly divided by the largest power of10that will fit into a machine word. The remainder is then repeatedly divided by10using 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.
$ok = $vector->from_dec($string);$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, 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";$ok = $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).
In each range, the first integer must always be less than or equal to the second one.
All integers must lie in the permitted range for the given bit vector, i.e., they must lie between "
0" and "$vector->Size()-1".The method returns "false" ("0") if any of the above conditions is violated, or "true" ("1") if no error occurred.
Example:
$ok = $vector->from_enum("2,3,5-7,11,13-19");Note that the order of the indices and ranges is irrelevant, i.e.,
$ok = $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))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".$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);$vector->Delete($offset,$bits);$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.
$carry = $vec3->add($vec1,$vec2,$carry);$carry = $vec3->subtract($vec1,$vec2,$carry);$vec2->Negate($vec1);$vec2->Absolute($vec1);$sign = $vector->Sign();$vec3->Multiply($vec1,$vec2);$quot->Divide($vec1,$vec2,$rest);$vec3->GCD($vec1,$vec2);$vector->Block_Store($buffer);$buffer = $vector->Block_Read();$size = $vector->Word_Size();$vector->Word_Store($offset,$word);$word = $vector->Word_Read($offset);$vector->Word_List_Store(@words);@words = $vector->Word_List_Read();$vector->Word_Insert($offset,$count);$vector->Word_Delete($offset,$count);$vector->Chunk_Store($chunksize,$offset,$chunk);$chunk = $vector->Chunk_Read($chunksize,$offset);$vector->Chunk_List_Store($chunksize,@chunks);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 }@chunks = $vector->Chunk_List_Read($chunksize);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);$vector->Index_List_Store(@indices);@indices = $vector->Index_List_Read();$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.$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.$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.$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.$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.
$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".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 == rows2This 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 wether 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 wether an EDGE exists between any two vertices of the graph or not, whereas the reflexive transitive closure answers the question wether 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 == rows1Note 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.
CLASS METHODS (implemented in Perl)
$config = Bit::Vector->Configuration();Bit::Vector->Configuration($config);$oldconfig = Bit::Vector->Configuration($newconfig);This method serves to alter the semantics (i.e., behaviour) of certain overloaded operators (which are all implemented in Perl, by the way).
It does not have any effect whatsoever on anything else. In particular, it does not affect the methods implemented in C.
The method accepts an (optional) string as input in which certain keywords are expected, which influence some or almost all of the overloaded operators in several possible ways.
The method always returns a string (which you do not need to take care of, i.e., to store, in case you aren't interested in keeping it) which is a complete representation of the current configuration (i.e., BEFORE any modifications are applied) and which can be fed back to this method later in order to restore the previous configuration.
There are three aspects of the way certain overloaded operators behave which can be controlled with this method:
+ the way scalar operands (replacing one of the two bit vector object operands) are automatically converted internally into a bit vector object of their own, + the operation certain overloaded operators perform, i.e., an operation with sets or an arithmetic operation, + the format to which bit vectors are converted automatically when they are enclosed in double quotes.The input string may contain any number of assignments, each of which controls one of these three aspects.
Each assignment has the form "
<which>=<value>"."
<which>" and "<value>" thereby consist of letters ([a-zA-Z]) and white space.Multiple assignments have to be separated by one or more comma (","), semi-colon (";"), colon (":"), vertical bar ("|"), slash ("/"), newline ("\n"), ampersand ("&"), plus ("+") or dash ("-").
Empty lines or statements (only white space) are allowed but will be ignored.
"
<which>" has to contain one or more keywords from one of three groups, each group representing one of the three aspects that the "Configuration()" method controls:+ "^scalar", "^input", "^in$" + "^operator", "^semantic", "^ops$" + "^string", "^output", "^out$"The character "^" thereby denotes the beginning of a word, and "$" denotes the end. Case is ignored (!).
Using these keywords, you can build any phrase you like to select one of the three aspects (see also examples given below).
The only condition is that no other keyword from any of the other two groups may match - otherwise a syntax error will occur (i.e., ambiguities are forbidden). A syntax error also occurs if none of the keywords matches.
This same principle applies to "
<value>":Depending on which aspect you specified for "
<which>", there are different groups of keywords that determine the value the selected aspect will be set to:+ "<which>" = "^scalar", "^input", "^in$": "<value>" = * "^bit$", "^index", "^indice" * "^hex" * "^bin" * "^dec" * "^enum" + "<which>" = "^operator", "^semantic", "^ops$": "<value>" = * "^set$" * "^arithmetic" + "<which>" = "^string", "^output", "^out$": "<value>" = * "^hex" * "^bin" * "^dec" * "^enum"Examples:
"Any scalar input I provide should be considered to be = a bit index" "I want to have operator semantics suitable for = arithmetics" "Any bit vector in double quotes is to be output as = an enumeration"
Scalar input:
In the case of scalar input, "^bit$", "^index", or "^indice" all cause scalar input to be considered to represent a bit index, i.e., "$vector ^= 5;" will flip bit #5 in the given bit vector (this is essentially the same as "$vector->bit_flip(5);").
Note that "bit indices" is the default setting for "scalar input".
The keyword "^hex" will cause scalar input to be considered as being in hexadecimal, i.e., "$vector ^= 5;" will flip bit #0 and bit #2 (because hexadecimal "5" is binary "0101").
(Note though that hexadecimal input should always be enclosed in quotes, otherwise it will be interpreted as a decimal number by Perl! The example relies on the fact that hexadecimal 0-9 and decimal 0-9 are the same.)
The keyword "^bin" will cause scalar input to be considered as being in binary format. All characters except "0" and "1" are forbidden in this case (i.e., produce a syntax error).
"$vector ^= '0101';", for instance, will flip bit #0 and bit #2.
The keyword "^dec" causes scalar input to be considered as integers in decimal format, i.e., "$vector ^= 5;" will flip bit #0 and bit #2 (because decimal "5" is binary "0101").
(Note though that all decimal input should be enclosed in quotes, because for large numbers, Perl will use scientific notation internally for representing them, which produces a syntax error because scientific notation is neither supported by this module nor needed.)
Finally, the keyword "^enum" causes scalar input to be considered as being a list ("enumeration") of indices and ranges of (contiguous) indices, i.e., "$vector |= '2,3,5,7-13,17-23';" will cause bits #2, #3, #5, #7 through #13 and #17 through #23 to be set.
Operator semantics:
Several overloaded operators can have two distinct functions depending on this setting.
The affected operators are: "+", "-", "*", "<", "<=", ">" and ">=".
With the default setting, "set operations", these operators perform:
+ set union ( set1 u set2 )
- set difference ( set1 \ set2 )
* set intersection ( set1 n set2 )
< true subset relationship ( set1 < set2 )
<= subset relationship ( set1 <= set2 )
> true superset relationship ( set1 > set2 )
>= superset relationship ( set1 >= set2 )With the alternative setting, "arithmetic operations", these operators perform:
+ addition ( num1 + num2 )
- subtraction ( num1 - num2 )
* multiplication ( num1 * num2 )
< "less than" comparison ( num1 < num2 )
<= "less than or equal" comparison ( num1 <= num2 )
> "greater than" comparison ( num1 > num2 )
>= "greater than or equal" comparison ( num1 >= num2 )Note that these latter comparison operators ("<", "<=", ">" and ">=") regard their operands as being SIGNED.
To perform comparisons with UNSIGNED operands, use the operators "lt", "le", "gt" and "ge" instead (in contrast to the operators above, these operators are NOT affected by the "operator semantics" setting).
String output:
There are four methods which convert the contents of a given bit vector into a string: "to_Hex()", "to_Bin()", "to_Dec()" and "to_Enum()" (not counting "Block_Read()", since this method does not return a human-readable string).
(For conversion to octal, see the description of the method "Chunk_List_Read()".)
Therefore, there are four possible formats into which a bit vector can be converted when it is enclosed in double quotes, for example:
print "\$vector = '$vector'\n";
$string = "$vector";Hence you can set "string output" to four different values: To "hex" for hexadecimal format (which is the default), to "bin" for binary format, to "dec" for conversion to decimal numbers and to "enum" for conversion to enumerations (".newsrc" style sets).
BEWARE that the conversion to decimal numbers is inherently slow; it can easily take up several seconds for a single large bit vector!
Therefore you should store the decimal strings returned to you rather than converting a given bit vector again.
Examples:
The default setting as returned by the method "Configuration()" is:
Scalar Input = Bit Index
Operator Semantics = Set Operators
String Output = HexadecimalPerforming a statement such as:
Bit::Vector->Configuration("in=bin,ops=arithmetic,out=bin");
print Bit::Vector->Configuration(), "\n";yields the following output:
Scalar Input = Binary
Operator Semantics = Arithmetic Operators
String Output = BinaryNote that you can always feed this output back into the "Configuration()" method to restore that setting later.
This also means that you can enter the same given setting with almost any degree of verbosity you like (as long as the required keywords appear and no ambiguities arise).
Note further that any aspect you do not specify is not changed, i.e., the statement
Bit::Vector->Configuration("operators = arithmetic");leaves all other aspects unchanged.
OVERLOADED OPERATORS (implemented in Perl)
(under construction)
SEE ALSO
Set::IntegerFast(3), Set::IntegerRange(3), Math::MatrixBool(3), Math::MatrixReal(3), DFA::Kleene(3), Math::Kleene(3), Graph::Kruskal(3).
perl(1), perlsub(1), perlmod(1), perlref(1), perlobj(1), perlbot(1), perltoot(1), perlxs(1), perlxstut(1), perlguts(1), overload(3).
VERSION
This man page documents "Bit::Vector" version 5.0.
AUTHOR
Steffen Beyer <sb@sdm.de>.
COPYRIGHT
Copyright (c) 1995, 1996, 1997, 1998 by Steffen Beyer. All rights reserved.
LICENSE
This package is "Non-Profit-Ware" ("NP-ware").
You may use, copy, modify and redistribute it under the terms of the "Non-Profit License" (NPL).
Please refer to the file "LICENSE" in this module's distribution for details!
2 POD Errors
The following errors were encountered while parsing the POD:
- Around line 3028:
You forgot a '=back' before '=head2'
- Around line 3163:
=back without =over