1Vector(3) User Contributed Perl Documentation Vector(3)
2
6 Bit::Vector - Efficient bit vector, set of integers and "big int" math
7 library
8
10 OVERLOADED OPERATORS
11 See Bit::Vector::Overload(3).
13 MORE STRING IMPORT/EXPORT
15 See Bit::Vector::String(3).
17 CLASS METHODS
19 Version
21 $version = Bit::Vector->Version();
22 Word_Bits
24 $bits = Bit::Vector->Word_Bits(); # bits in a machine word
25 Long_Bits
27 $bits = Bit::Vector->Long_Bits(); # bits in an unsigned long
28 new
30 $vector = Bit::Vector->new($bits); # bit vector constructor
31 @veclist = Bit::Vector->new($bits,$count);
33 new_Hex
35 $vector = Bit::Vector->new_Hex($bits,$string);
36 new_Bin
38 $vector = Bit::Vector->new_Bin($bits,$string);
39 new_Dec
41 $vector = Bit::Vector->new_Dec($bits,$string);
42 new_Enum
44 $vector = Bit::Vector->new_Enum($bits,$string);
45 Concat_List
47 $vector = Bit::Vector->Concat_List(@vectors);
48 OBJECT METHODS
50 new
52 $vec2 = $vec1->new($bits); # alternative call of constructor
53 @veclist = $vec->new($bits,$count);
55 Shadow
57 $vec2 = $vec1->Shadow(); # new vector, same size but empty
58 Clone
60 $vec2 = $vec1->Clone(); # new vector, exact duplicate
61 Concat
63 $vector = $vec1->Concat($vec2);
64 Concat_List
66 $vector = $vec1->Concat_List($vec2,$vec3,...);
67 Size
69 $bits = $vector->Size();
70 Resize
72 $vector->Resize($bits);
73 $vector->Resize($vector->Size()+5);
74 $vector->Resize($vector->Size()-5);
75 Copy
77 $vec2->Copy($vec1);
78 Empty
80 $vector->Empty();
81 Fill
83 $vector->Fill();
84 Flip
86 $vector->Flip();
87 Primes
89 $vector->Primes(); # Sieve of Erathostenes
90 Reverse
92 $vec2->Reverse($vec1);
93 Interval_Empty
95 $vector->Interval_Empty($min,$max);
96 Interval_Fill
98 $vector->Interval_Fill($min,$max);
99 Interval_Flip
101 $vector->Interval_Flip($min,$max);
102 Interval_Reverse
104 $vector->Interval_Reverse($min,$max);
105 Interval_Scan_inc
107 if (($min,$max) = $vector->Interval_Scan_inc($start))
108 Interval_Scan_dec
110 if (($min,$max) = $vector->Interval_Scan_dec($start))
111 Interval_Copy
113 $vec2->Interval_Copy($vec1,$offset2,$offset1,$length);
114 Interval_Substitute
116 $vec2->Interval_Substitute($vec1,$off2,$len2,$off1,$len1);
117 is_empty
119 if ($vector->is_empty())
120 is_full
122 if ($vector->is_full())
123 equal
125 if ($vec1->equal($vec2))
126 Lexicompare (unsigned)
128 if ($vec1->Lexicompare($vec2) == 0)
129 if ($vec1->Lexicompare($vec2) != 0)
130 if ($vec1->Lexicompare($vec2) < 0)
131 if ($vec1->Lexicompare($vec2) <= 0)
132 if ($vec1->Lexicompare($vec2) > 0)
133 if ($vec1->Lexicompare($vec2) >= 0)
134 Compare (signed)
136 if ($vec1->Compare($vec2) == 0)
137 if ($vec1->Compare($vec2) != 0)
138 if ($vec1->Compare($vec2) < 0)
139 if ($vec1->Compare($vec2) <= 0)
140 if ($vec1->Compare($vec2) > 0)
141 if ($vec1->Compare($vec2) >= 0)
142 to_Hex
144 $string = $vector->to_Hex();
145 from_Hex
147 $vector->from_Hex($string);
148 to_Bin
150 $string = $vector->to_Bin();
151 from_Bin
153 $vector->from_Bin($string);
154 to_Dec
156 $string = $vector->to_Dec();
157 from_Dec
159 $vector->from_Dec($string);
160 to_Enum
162 $string = $vector->to_Enum(); # e.g. "2,3,5-7,11,13-19"
163 from_Enum
165 $vector->from_Enum($string);
166 Bit_Off
168 $vector->Bit_Off($index);
169 Bit_On
171 $vector->Bit_On($index);
172 bit_flip
174 $bit = $vector->bit_flip($index);
175 bit_test
177 contains
178 $bit = $vector->bit_test($index);
179 $bit = $vector->contains($index);
180 if ($vector->bit_test($index))
181 if ($vector->contains($index))
182 Bit_Copy
184 $vector->Bit_Copy($index,$bit);
185 LSB (least significant bit)
187 $vector->LSB($bit);
188 MSB (most significant bit)
190 $vector->MSB($bit);
191 lsb (least significant bit)
193 $bit = $vector->lsb();
194 msb (most significant bit)
196 $bit = $vector->msb();
197 rotate_left
199 $carry = $vector->rotate_left();
200 rotate_right
202 $carry = $vector->rotate_right();
203 shift_left
205 $carry = $vector->shift_left($carry);
206 shift_right
208 $carry = $vector->shift_right($carry);
209 Move_Left
211 $vector->Move_Left($bits); # shift left "$bits" positions
212 Move_Right
214 $vector->Move_Right($bits); # shift right "$bits" positions
215 Insert
217 $vector->Insert($offset,$bits);
218 Delete
220 $vector->Delete($offset,$bits);
221 increment
223 $carry = $vector->increment();
224 decrement
226 $carry = $vector->decrement();
227 inc
229 $overflow = $vec2->inc($vec1);
230 dec
232 $overflow = $vec2->dec($vec1);
233 add
235 $carry = $vec3->add($vec1,$vec2,$carry);
236 ($carry,$overflow) = $vec3->add($vec1,$vec2,$carry);
237 subtract
239 $carry = $vec3->subtract($vec1,$vec2,$carry);
240 ($carry,$overflow) = $vec3->subtract($vec1,$vec2,$carry);
241 Neg
243 Negate
244 $vec2->Neg($vec1);
245 $vec2->Negate($vec1);
246 Abs
248 Absolute
249 $vec2->Abs($vec1);
250 $vec2->Absolute($vec1);
251 Sign
253 if ($vector->Sign() == 0)
254 if ($vector->Sign() != 0)
255 if ($vector->Sign() < 0)
256 if ($vector->Sign() <= 0)
257 if ($vector->Sign() > 0)
258 if ($vector->Sign() >= 0)
259 Multiply
261 $vec3->Multiply($vec1,$vec2);
262 Divide
264 $quot->Divide($vec1,$vec2,$rest);
265 GCD (Greatest Common Divisor)
267 $vecgcd->GCD($veca,$vecb);
268 $vecgcd->GCD($vecx,$vecy,$veca,$vecb);
269 Power
271 $vec3->Power($vec1,$vec2);
272 Block_Store
274 $vector->Block_Store($buffer);
275 Block_Read
277 $buffer = $vector->Block_Read();
278 Word_Size
280 $size = $vector->Word_Size(); # number of words in "$vector"
281 Word_Store
283 $vector->Word_Store($offset,$word);
284 Word_Read
286 $word = $vector->Word_Read($offset);
287 Word_List_Store
289 $vector->Word_List_Store(@words);
290 Word_List_Read
292 @words = $vector->Word_List_Read();
293 Word_Insert
295 $vector->Word_Insert($offset,$count);
296 Word_Delete
298 $vector->Word_Delete($offset,$count);
299 Chunk_Store
301 $vector->Chunk_Store($chunksize,$offset,$chunk);
302 Chunk_Read
304 $chunk = $vector->Chunk_Read($chunksize,$offset);
305 Chunk_List_Store
307 $vector->Chunk_List_Store($chunksize,@chunks);
308 Chunk_List_Read
310 @chunks = $vector->Chunk_List_Read($chunksize);
311 Index_List_Remove
313 $vector->Index_List_Remove(@indices);
314 Index_List_Store
316 $vector->Index_List_Store(@indices);
317 Index_List_Read
319 @indices = $vector->Index_List_Read();
320 Or
322 Union
323 $vec3->Or($vec1,$vec2);
324 $set3->Union($set1,$set2);
325 And
327 Intersection
328 $vec3->And($vec1,$vec2);
329 $set3->Intersection($set1,$set2);
330 AndNot
332 Difference
333 $vec3->AndNot($vec1,$vec2);
334 $set3->Difference($set1,$set2);
335 Xor
337 ExclusiveOr
338 $vec3->Xor($vec1,$vec2);
339 $set3->ExclusiveOr($set1,$set2);
340 Not
342 Complement
343 $vec2->Not($vec1);
344 $set2->Complement($set1);
345 subset
347 if ($set1->subset($set2)) # true if $set1 is subset of $set2
348 Norm
350 $norm = $set->Norm();
351 $norm = $set->Norm2();
352 $norm = $set->Norm3();
353 Min
355 $min = $set->Min();
356 Max
358 $max = $set->Max();
359 Multiplication
361 $matrix3->Multiplication($rows3,$cols3,
362 $matrix1,$rows1,$cols1,
363 $matrix2,$rows2,$cols2);
364 Product
366 $matrix3->Product($rows3,$cols3,
367 $matrix1,$rows1,$cols1,
368 $matrix2,$rows2,$cols2);
369 Closure
371 $matrix->Closure($rows,$cols);
372 Transpose
374 $matrix2->Transpose($rows2,$cols2,$matrix1,$rows1,$cols1);
375
377 · Method naming conventions
378 Method names completely in lower case indicate a boolean return
380 value.
381 (Except for the bit vector constructor method ""new()"", of course.)
383 · Boolean values
385 Boolean values in this module are always a numeric zero ("0") for
387 "false" and a numeric one ("1") for "true".
388 · Negative numbers
390 All numeric input parameters passed to any of the methods in this
392 module are regarded as being UNSIGNED (as opposed to the contents of
393 the bit vectors themselves, which are usually considered to be
394 SIGNED).
395 As a consequence, whenever you pass a negative number as an argument
397 to some method of this module, it will be treated as a (usually very
398 large) positive number due to its internal two's complement binary
399 representation, usually resulting in an "index out of range" error
400 message and program abortion.
401 · Bit order
403 Note that bit vectors are stored least order bit and least order word
405 first internally.
406 I.e., bit #0 of any given bit vector corresponds to bit #0 of word #0
408 in the array of machine words representing the bit vector.
409 (Where word #0 comes first in memory, i.e., it is stored at the least
411 memory address in the allocated block of memory holding the given bit
412 vector.)
413 Note however that machine words can be stored least order byte first
415 or last, depending on your system's implementation.
416 When you are exporting or importing a whole bit vector at once using
418 the methods ""Block_Read()"" and ""Block_Store()"" (the only time in
419 this module where this could make any difference), however, a conver‐
420 sion to and from "least order byte first" order is automatically sup‐
421 plied.
422 In other words, what ""Block_Read()"" provides and what
424 ""Block_Store()"" expects is always in "least order byte first"
425 order, regardless of the order in which words are stored internally
426 on your machine.
427 This is to make sure that what you export on one machine using
429 ""Block_Read()"" can always be read in correctly with
430 ""Block_Store()"" on a different machine.
431 Note further that whenever bit vectors are converted to and from
433 (binary or hexadecimal) strings, the RIGHTMOST bit is always the
434 LEAST SIGNIFICANT one, and the LEFTMOST bit is always the MOST SIG‐
435 NIFICANT bit.
436 This is because in our western culture, numbers are always repre‐
438 sented in this way (least significant to most significant digits go
439 from right to left).
440 Of course this requires an internal reversion of order, which the
442 corresponding conversion methods perform automatically (without any
443 additional overhead, it's just a matter of starting the internal loop
444 at the bottom or the top end).
445 · "Word" related methods
447 Note that all methods whose names begin with ""Word_"" are MACHINE-
449 DEPENDENT!
450 They depend on the size (number of bits) of an "unsigned int" (C
452 type) on your machine.
453 Therefore, you should only use these methods if you are ABSOLUTELY
455 CERTAIN that portability of your code is not an issue!
456 Note that you can use arbitrarily large chunks (i.e., fragments of
458 bit vectors) of up to 32 bits IN A PORTABLE WAY using the methods
459 whose names begin with ""Chunk_"".
460 · Chunk sizes
462 Note that legal chunk sizes for all methods whose names begin with
464 ""Chunk_"" range from "1" to ""Bit::Vector->Long_Bits();"" bits ("0"
465 is NOT allowed!).
466 In order to make your programs portable, however, you shouldn't use
468 chunk sizes larger than 32 bits, since this is the minimum size of an
469 "unsigned long" (C type) on all systems, as prescribed by ANSI C.
470 · Matching sizes
472 In general, for methods involving several bit vectors at the same
474 time, all bit vector arguments must have identical sizes (number of
475 bits), or a fatal "size mismatch" error will occur.
476 Exceptions from this rule are the methods ""Concat()"", ""Con‐
478 cat_List()"", ""Copy()"", ""Interval_Copy()"" and ""Interval_Substi‐
479 tute()"", where no conditions at all are imposed on the size of their
480 bit vector arguments.
481 In method ""Multiply()"", all three bit vector arguments must in
483 principle obey the rule of matching sizes, but the bit vector in
484 which the result of the multiplication is to be stored may be larger
485 than the two bit vector arguments containing the factors for the mul‐
486 tiplication.
487 In method ""Power()"", the bit vector for the result must be the same
489 size or greater than the base of the exponentiation term. The expo‐
490 nent can be any size.
491 · Index ranges
493 All indices for any given bits must lie between "0" and ""$vec‐
495 tor->Size()-1"", or a fatal "index out of range" error will occur.
496
498 OVERLOADED OPERATORS
499 See Bit::Vector::Overload(3).
501 MORE STRING IMPORT/EXPORT
503 See Bit::Vector::String(3).
505 CLASS METHODS
507 · "$version = Bit::Vector->Version();"
509 Returns the current version number of this module.
511 · "$bits = Bit::Vector->Word_Bits();"
513 Returns the number of bits of an "unsigned int" (C type) on your
515 machine.
516 (An "unsigned int" is also called a "machine word", hence the name of
518 this method.)
519 · "$bits = Bit::Vector->Long_Bits();"
521 Returns the number of bits of an "unsigned long" (C type) on your
523 machine.
524 · "$vector = Bit::Vector->new($bits);"
526 This is the bit vector constructor method.
528 Call this method to create a new bit vector containing "$bits" bits
530 (with indices ranging from "0" to ""$bits-1"").
531 Note that - in contrast to previous versions - bit vectors of length
533 zero (i.e., with "$bits = 0") are permitted now.
534 The method returns a reference to the newly created bit vector.
536 A new bit vector is always initialized so that all bits are cleared
538 (turned off).
539 An exception will be raised if the method is unable to allocate the
541 necessary memory.
542 Note that if you specify a negative number for "$bits" it will be
544 interpreted as a large positive number due to its internal two's com‐
545 plement binary representation.
546 In such a case, the bit vector constructor method will obediently
548 attempt to create a bit vector of that size, probably resulting in an
549 exception, as explained above.
550 · "@veclist = Bit::Vector->new($bits,$count);"
552 You can also create more than one bit vector at a time if you specify
554 the optional second parameter "$count".
555 The method returns a list of "$count" bit vectors which all have the
557 same number of bits "$bits" (and which are all initialized, i.e., all
558 bits are cleared).
559 If "$count" is zero, an empty list is returned.
561 If "$bits" is zero, a list of null-sized bit vectors is returned.
563 Note again that if you specify a negative number for "$count" it will
565 be interpreted as a large positive number due to its internal two's
566 complement binary representation.
567 In such a case, the bit vector constructor method will obediently
569 attempt to create that many bit vectors, probably resulting in an
570 exception ("out of memory").
571 · "$vector = Bit::Vector->new_Hex($bits,$string);"
573 This method is an alternative constructor which allows you to create
575 a new bit vector object (with "$bits" bits) and to initialize it all
576 in one go.
577 The method internally first calls the bit vector constructor method
579 ""new()"" and then passes the given string to the method
580 ""from_Hex()"".
581 However, this method is more efficient than performing these two
583 steps separately: First because in this method, the memory area occu‐
584 pied by the new bit vector is not initialized to zeros (which is
585 pointless in this case), and second because it saves you from the
586 associated overhead of one additional method invocation.
587 An exception will be raised if the necessary memory cannot be allo‐
589 cated (see the description of the method ""new()"" immediately above
590 for possible causes) or if the given string cannot be converted suc‐
591 cessfully (see the description of the method ""from_Hex()"" further
592 below for details).
593 In the latter case, the memory occupied by the new bit vector is
595 released first (i.e., "free"d) before the exception is actually
596 raised.
597 · "$vector = Bit::Vector->new_Bin($bits,$string);"
599 This method is an alternative constructor which allows you to create
601 a new bit vector object (with "$bits" bits) and to initialize it all
602 in one go.
603 The method internally first calls the bit vector constructor method
605 ""new()"" and then passes the given string to the method
606 ""from_Bin()"".
607 However, this method is more efficient than performing these two
609 steps separately: First because in this method, the memory area occu‐
610 pied by the new bit vector is not initialized to zeros (which is
611 pointless in this case), and second because it saves you from the
612 associated overhead of one additional method invocation.
613 An exception will be raised if the necessary memory cannot be allo‐
615 cated (see the description of the method ""new()"" above for possible
616 causes) or if the given string cannot be converted successfully (see
617 the description of the method ""from_Bin()"" further below for
618 details).
619 In the latter case, the memory occupied by the new bit vector is
621 released first (i.e., "free"d) before the exception is actually
622 raised.
623 · "$vector = Bit::Vector->new_Dec($bits,$string);"
625 This method is an alternative constructor which allows you to create
627 a new bit vector object (with "$bits" bits) and to initialize it all
628 in one go.
629 The method internally first calls the bit vector constructor method
631 ""new()"" and then passes the given string to the method
632 ""from_Dec()"".
633 However, this method is more efficient than performing these two
635 steps separately: First because in this method, ""new()"" does not
636 initialize the memory area occupied by the new bit vector with zeros
637 (which is pointless in this case, because ""from_Dec()"" will do it
638 anyway), and second because it saves you from the associated overhead
639 of one additional method invocation.
640 An exception will be raised if the necessary memory cannot be allo‐
642 cated (see the description of the method ""new()"" above for possible
643 causes) or if the given string cannot be converted successfully (see
644 the description of the method ""from_Dec()"" further below for
645 details).
646 In the latter case, the memory occupied by the new bit vector is
648 released first (i.e., "free"d) before the exception is actually
649 raised.
650 · "$vector = Bit::Vector->new_Enum($bits,$string);"
652 This method is an alternative constructor which allows you to create
654 a new bit vector object (with "$bits" bits) and to initialize it all
655 in one go.
656 The method internally first calls the bit vector constructor method
658 ""new()"" and then passes the given string to the method
659 ""from_Enum()"".
660 However, this method is more efficient than performing these two
662 steps separately: First because in this method, ""new()"" does not
663 initialize the memory area occupied by the new bit vector with zeros
664 (which is pointless in this case, because ""from_Enum()"" will do it
665 anyway), and second because it saves you from the associated overhead
666 of one additional method invocation.
667 An exception will be raised if the necessary memory cannot be allo‐
669 cated (see the description of the method ""new()"" above for possible
670 causes) or if the given string cannot be converted successfully (see
671 the description of the method ""from_Enum()"" further below for
672 details).
673 In the latter case, the memory occupied by the new bit vector is
675 released first (i.e., "free"d) before the exception is actually
676 raised.
677 · "$vector = Bit::Vector->Concat_List(@vectors);"
679 This method creates a new vector containing all bit vectors from the
681 argument list in concatenated form.
682 The argument list may contain any number of arguments (including
684 zero); the only condition is that all arguments must be bit vectors.
685 There is no condition concerning the length (in number of bits) of
687 these arguments.
688 The vectors from the argument list are not changed in any way.
690 If the argument list is empty or if all arguments have length zero,
692 the resulting bit vector will also have length zero.
693 Note that the RIGHTMOST bit vector from the argument list will become
695 the LEAST significant part of the resulting bit vector, and the LEFT‐
696 MOST bit vector from the argument list will become the MOST signifi‐
697 cant part of the resulting bit vector.
698 OBJECT METHODS
700 · "$vec2 = $vec1->new($bits);"
702 "@veclist = $vec->new($bits);"
704 This is an alternative way of calling the bit vector constructor
706 method.
707 Vector "$vec1" (or "$vec") is not affected by this, it just serves as
709 an anchor for the method invocation mechanism.
710 In fact ALL class methods in this module can be called this way, even
712 though this is probably considered to be "politically incorrect" by
713 OO ("object-orientation") aficionados. ;-)
714 So even if you are too lazy to type ""Bit::Vector->"" instead of
716 ""$vec1->"" (and even though laziness is - allegedly - a programmer's
717 virtue ":-)"), maybe it is better not to use this feature if you
718 don't want to get booed at. ;-)
719 · "$vec2 = $vec1->Shadow();"
721 Creates a NEW bit vector "$vec2" of the SAME SIZE as "$vec1" but
723 which is EMPTY.
724 Just like a shadow that has the same shape as the object it origi‐
726 nates from, but is flat and has no volume, i.e., contains nothing.
727 · "$vec2 = $vec1->Clone();"
729 Creates a NEW bit vector "$vec2" of the SAME SIZE as "$vec1" which is
731 an EXACT COPY of "$vec1".
732 · "$vector = $vec1->Concat($vec2);"
734 This method returns a new bit vector object which is the result of
736 the concatenation of the contents of "$vec1" and "$vec2".
737 Note that the contents of "$vec1" become the MOST significant part of
739 the resulting bit vector, and "$vec2" the LEAST significant part.
740 If both bit vector arguments have length zero, the resulting bit vec‐
742 tor will also have length zero.
743 · "$vector = $vec1->Concat_List($vec2,$vec3,...);"
745 This is an alternative way of calling this (class) method as an
747 object method.
748 The method returns a new bit vector object which is the result of the
750 concatenation of the contents of "$vec1 . $vec2 . $vec3 . ..."
751 See the section "class methods" above for a detailed description of
753 this method.
754 Note that the argument list may be empty and that all arguments must
756 be bit vectors if it isn't.
757 · "$bits = $vector->Size();"
759 Returns the size (number of bits) the given vector was created with
761 (or ""Resize()""d to).
762 · "$vector->Resize($bits);"
764 Changes the size of the given vector to the specified number of bits.
766 This method allows you to change the size of an existing bit vector,
768 preserving as many bits from the old vector as will fit into the new
769 one (i.e., all bits with indices smaller than the minimum of the
770 sizes of both vectors, old and new).
771 If the number of machine words needed to store the new vector is
773 smaller than or equal to the number of words needed to store the old
774 vector, the memory allocated for the old vector is reused for the new
775 one, and only the relevant book-keeping information is adjusted
776 accordingly.
777 This means that even if the number of bits increases, new memory is
779 not necessarily being allocated (i.e., if the old and the new number
780 of bits fit into the same number of machine words).
781 If the number of machine words needed to store the new vector is
783 greater than the number of words needed to store the old vector, new
784 memory is allocated for the new vector, the old vector is copied to
785 the new one, the remaining bits in the new vector are cleared (turned
786 off) and the old vector is deleted, i.e., the memory that was allo‐
787 cated for it is released.
788 (An exception will be raised if the method is unable to allocate the
790 necessary memory for the new vector.)
791 As a consequence, if you decrease the size of a given vector so that
793 it will use fewer machine words, and increase it again later so that
794 it will use more words than immediately before but still less than
795 the original vector, new memory will be allocated anyway because the
796 information about the size of the original vector is lost whenever
797 you resize it.
798 Note also that if you specify a negative number for "$bits" it will
800 be interpreted as a large positive number due to its internal two's
801 complement binary representation.
802 In such a case, "Resize()" will obediently attempt to create a bit
804 vector of that size, probably resulting in an exception, as explained
805 above.
806 Finally, note that - in contrast to previous versions - resizing a
808 bit vector to a size of zero bits (length zero) is now permitted.
809 · "$vec2->Copy($vec1);"
811 Copies the contents of bit vector "$vec1" to bit vector "$vec2".
813 The previous contents of bit vector "$vec2" get overwritten, i.e.,
815 are lost.
816 Both vectors must exist beforehand, i.e., this method does not CREATE
818 any new bit vector object.
819 The two vectors may be of any size.
821 If the source bit vector is larger than the target, this method will
823 copy as much of the least significant bits of the source vector as
824 will fit into the target vector, thereby discarding any extraneous
825 most significant bits.
826 BEWARE that this causes a brutal cutoff in the middle of your data,
828 and it will also leave you with an almost unpredictable sign if sub‐
829 sequently the number in the target vector is going to be interpreted
830 as a number! (You have been warned!)
831 If the target bit vector is larger than the source, this method fills
833 up the remaining most significant bits in the target bit vector with
834 either 0's or 1's, depending on the sign (= the most significant bit)
835 of the source bit vector. This is also known as "sign extension".
836 This makes it possible to copy numbers from a smaller bit vector into
838 a larger one while preserving the number's absolute value as well as
839 its sign (due to the two's complement binary representation of num‐
840 bers).
841 · "$vector->Empty();"
843 Clears all bits in the given vector.
845 · "$vector->Fill();"
847 Sets all bits in the given vector.
849 · "$vector->Flip();"
851 Flips (i.e., complements) all bits in the given vector.
853 · "$vector->Primes();"
855 Clears the given bit vector and sets all bits whose indices are prime
857 numbers.
858 This method uses the algorithm known as the "Sieve of Erathostenes"
860 internally.
861 · "$vec2->Reverse($vec1);"
863 This method copies the given vector "$vec1" to the vector "$vec2",
865 thereby reversing the order of all bits.
866 I.e., the least significant bit of "$vec1" becomes the most signifi‐
868 cant bit of "$vec2", whereas the most significant bit of "$vec1"
869 becomes the least significant bit of "$vec2", and so forth for all
870 bits in between.
871 Note that in-place processing is also possible, i.e., "$vec1" and
873 "$vec2" may be identical.
874 (Internally, this is the same as "$vec1->Inter‐
876 val_Reverse(0,$vec1->Size()-1);".)
877 · "$vector->Interval_Empty($min,$max);"
879 Clears all bits in the interval "[$min..$max]" (including both lim‐
881 its) in the given vector.
882 "$min" and "$max" may have the same value; this is the same as clear‐
884 ing a single bit with ""Bit_Off()"" (but less efficient).
885 Note that "$vector->Interval_Empty(0,$vector->Size()-1);" is the same
887 as "$vector->Empty();" (but less efficient).
888 · "$vector->Interval_Fill($min,$max);"
890 Sets all bits in the interval "[$min..$max]" (including both limits)
892 in the given vector.
893 "$min" and "$max" may have the same value; this is the same as set‐
895 ting a single bit with ""Bit_On()"" (but less efficient).
896 Note that "$vector->Interval_Fill(0,$vector->Size()-1);" is the same
898 as "$vector->Fill();" (but less efficient).
899 · "$vector->Interval_Flip($min,$max);"
901 Flips (i.e., complements) all bits in the interval "[$min..$max]"
903 (including both limits) in the given vector.
904 "$min" and "$max" may have the same value; this is the same as flip‐
906 ping a single bit with ""bit_flip()"" (but less efficient).
907 Note that "$vector->Interval_Flip(0,$vector->Size()-1);" is the same
909 as "$vector->Flip();" and "$vector->Complement($vector);" (but less
910 efficient).
911 · "$vector->Interval_Reverse($min,$max);"
913 Reverses the order of all bits in the interval "[$min..$max]"
915 (including both limits) in the given vector.
916 I.e., bits "$min" and "$max" swap places, and so forth for all bits
918 in between.
919 "$min" and "$max" may have the same value; this has no effect whatso‐
921 ever, though.
922 · "if (($min,$max) = $vector->Interval_Scan_inc($start))"
924 Returns the minimum and maximum indices of the next contiguous block
926 of set bits (i.e., bits in the "on" state).
927 The search starts at index "$start" (i.e., "$min" >= "$start") and
929 proceeds upwards (i.e., "$max" >= "$min"), thus repeatedly increments
930 the search pointer "$start" (internally).
931 Note though that the contents of the variable (or scalar literal
933 value) "$start" is NOT altered. I.e., you have to set it to the
934 desired value yourself prior to each call to ""Interval_Scan_inc()""
935 (see also the example given below).
936 Actually, the bit vector is not searched bit by bit, but one machine
938 word at a time, in order to speed up execution (which means that this
939 method is quite efficient).
940 An empty list is returned if no such block can be found.
942 Note that a single set bit (surrounded by cleared bits) is a valid
944 block by this definition. In that case the return values for "$min"
945 and "$max" are the same.
946 Typical use:
948 $start = 0;
950 while (($start < $vector->Size()) &&
951 (($min,$max) = $vector->Interval_Scan_inc($start)))
952 {
953 $start = $max + 2;
954 # do something with $min and $max
956 }
957 · "if (($min,$max) = $vector->Interval_Scan_dec($start))"
959 Returns the minimum and maximum indices of the next contiguous block
961 of set bits (i.e., bits in the "on" state).
962 The search starts at index "$start" (i.e., "$max" <= "$start") and
964 proceeds downwards (i.e., "$min" <= "$max"), thus repeatedly decre‐
965 ments the search pointer "$start" (internally).
966 Note though that the contents of the variable (or scalar literal
968 value) "$start" is NOT altered. I.e., you have to set it to the
969 desired value yourself prior to each call to ""Interval_Scan_dec()""
970 (see also the example given below).
971 Actually, the bit vector is not searched bit by bit, but one machine
973 word at a time, in order to speed up execution (which means that this
974 method is quite efficient).
975 An empty list is returned if no such block can be found.
977 Note that a single set bit (surrounded by cleared bits) is a valid
979 block by this definition. In that case the return values for "$min"
980 and "$max" are the same.
981 Typical use:
983 $start = $vector->Size() - 1;
985 while (($start >= 0) &&
986 (($min,$max) = $vector->Interval_Scan_dec($start)))
987 {
988 $start = $min - 2;
989 # do something with $min and $max
991 }
992 · "$vec2->Interval_Copy($vec1,$offset2,$offset1,$length);"
994 This method allows you to copy a stretch of contiguous bits (starting
996 at any position "$offset1" you choose, with a length of "$length"
997 bits) from a given "source" bit vector "$vec1" to another position
998 "$offset2" in a "target" bit vector "$vec2".
999 Note that the two bit vectors "$vec1" and "$vec2" do NOT need to have
1001 the same (matching) size!
1002 Consequently, any of the two terms ""$offset1 + $length"" and ""$off‐
1004 set2 + $length"" (or both) may exceed the actual length of its corre‐
1005 sponding bit vector (""$vec1->Size()"" and ""$vec2->Size()"", respec‐
1006 tively).
1007 In such a case, the "$length" parameter is automatically reduced
1009 internally so that both terms above are bounded by the number of bits
1010 of their corresponding bit vector.
1011 This may even result in a length of zero, in which case nothing is
1013 copied at all.
1014 (Of course the value of the "$length" parameter, supplied by you in
1016 the initial method call, may also be zero right from the start!)
1017 Note also that "$offset1" and "$offset2" must lie within the range
1019 "0" and, respectively, ""$vec1->Size()-1"" or ""$vec2->Size()-1"", or
1020 a fatal "offset out of range" error will occur.
1021 Note further that "$vec1" and "$vec2" may be identical, i.e., you may
1023 copy a stretch of contiguous bits from one part of a given bit vector
1024 to another part.
1025 The source and the target interval may even overlap, in which case
1027 the copying is automatically performed in ascending or descending
1028 order (depending on the direction of the copy - downwards or upwards
1029 in the bit vector, respectively) to handle this situation correctly,
1030 i.e., so that no bits are being overwritten before they have been
1031 copied themselves.
1032 · "$vec2->Interval_Substitute($vec1,$off2,$len2,$off1,$len1);"
1034 This method is (roughly) the same for bit vectors (i.e., arrays of
1036 booleans) as what the "splice" function in Perl is for lists (i.e.,
1037 arrays of scalars).
1038 (See "splice" in perlfunc for more details about this function.)
1040 The method allows you to substitute a stretch of contiguous bits
1042 (defined by a position (offset) "$off1" and a length of "$len1" bits)
1043 from a given "source" bit vector "$vec1" for a different stretch of
1044 contiguous bits (defined by a position (offset) "$off2" and a length
1045 of "$len2" bits) in another, "target" bit vector "$vec2".
1046 Note that the two bit vectors "$vec1" and "$vec2" do NOT need to have
1048 the same (matching) size!
1049 Note further that "$off1" and "$off2" must lie within the range "0"
1051 and, respectively, ""$vec1->Size()"" or ""$vec2->Size()"", or a fatal
1052 "offset out of range" error will occur.
1053 Alert readers will have noticed that these upper limits are NOT
1055 ""$vec1->Size()-1"" and ""$vec2->Size()-1"", as they would be for any
1056 other method in this module, but that these offsets may actually
1057 point to one position PAST THE END of the corresponding bit vector.
1058 This is necessary in order to make it possible to APPEND a given
1060 stretch of bits to the target bit vector instead of REPLACING some‐
1061 thing in it.
1062 For reasons of symmetry and generality, the same applies to the off‐
1064 set in the source bit vector, even though such an offset (one posi‐
1065 tion past the end of the bit vector) does not serve any practical
1066 purpose there (but does not cause any harm either).
1067 (Actually this saves you from the need of testing for this special
1069 case, in certain circumstances.)
1070 Note that whenever the term ""$off1 + $len1"" exceeds the size
1072 ""$vec1->Size()"" of bit vector "$vec1" (or if ""$off2 + $len2""
1073 exceeds ""$vec2->Size()""), the corresponding length ("$len1" or
1074 "$len2", respectively) is automatically reduced internally so that
1075 ""$off1 + $len1 <= $vec1->Size()"" (and ""$off2 + $len2 <=
1076 $vec2->Size()"") holds.
1077 (Note that this does NOT alter the intended result, even though this
1079 may seem counter-intuitive at first!)
1080 This may even result in a length ("$len1" or "$len2") of zero.
1082 A length of zero for the interval in the SOURCE bit vector (""$len1
1084 == 0"") means that the indicated stretch of bits in the target bit
1085 vector (starting at position "$off2") is to be replaced by NOTHING,
1086 i.e., is to be DELETED.
1087 A length of zero for the interval in the TARGET bit vector ("$len2 ==
1089 0") means that NOTHING is replaced, and that the stretch of bits from
1090 the source bit vector is simply INSERTED into the target bit vector
1091 at the indicated position ("$off2").
1092 If both length parameters are zero, nothing is done at all.
1094 Note that in contrast to any other method in this module (especially
1096 ""Interval_Copy()"", ""Insert()"" and ""Delete()""), this method
1097 IMPLICITLY and AUTOMATICALLY adapts the length of the resulting bit
1098 vector as needed, as given by
1099 $size = $vec2->Size(); # before
1101 $size += $len1 - $len2; # after
1102 (The only other method in this module that changes the size of a bit
1104 vector is the method ""Resize()"".)
1105 In other words, replacing a given interval of bits in the target bit
1107 vector with a longer or shorter stretch of bits from the source bit
1108 vector, or simply inserting (""$len2 == 0"") a stretch of bits into
1109 or deleting (""$len1 == 0"") an interval of bits from the target bit
1110 vector will automatically increase or decrease, respectively, the
1111 size of the target bit vector accordingly.
1112 For the sake of generality, this may even result in a bit vector with
1114 a size of zero (containing no bits at all).
1115 This is also the reason why bit vectors of length zero are permitted
1117 in this module in the first place, starting with version 5.0.
1118 Finally, note that "$vec1" and "$vec2" may be identical, i.e., in-
1120 place processing is possible.
1121 (If you think about that for a while or if you look at the code, you
1123 will see that this is far from trivial!)
1124 · "if ($vector->is_empty())"
1126 Tests whether the given bit vector is empty, i.e., whether ALL of its
1128 bits are cleared (in the "off" state).
1129 In "big integer" arithmetic, this is equivalent to testing whether
1131 the number stored in the bit vector is zero ("0").
1132 Returns "true" ("1") if the bit vector is empty and "false" ("0")
1134 otherwise.
1135 Note that this method also returns "true" ("1") if the given bit vec‐
1137 tor has a length of zero, i.e., if it contains no bits at all.
1138 · "if ($vector->is_full())"
1140 Tests whether the given bit vector is full, i.e., whether ALL of its
1142 bits are set (in the "on" state).
1143 In "big integer" arithmetic, this is equivalent to testing whether
1145 the number stored in the bit vector is minus one ("-1").
1146 Returns "true" ("1") if the bit vector is full and "false" ("0") oth‐
1148 erwise.
1149 If the given bit vector has a length of zero (i.e., if it contains no
1151 bits at all), this method returns "false" ("0").
1152 · "if ($vec1->equal($vec2))"
1154 Tests the two given bit vectors for equality.
1156 Returns "true" ("1") if the two bit vectors are exact copies of one
1158 another and "false" ("0") otherwise.
1159 · "$cmp = $vec1->Lexicompare($vec2);"
1161 Compares the two given bit vectors, which are regarded as UNSIGNED
1163 numbers in binary representation.
1164 The method returns ""-1"" if the first bit vector is smaller than the
1166 second bit vector, "0" if the two bit vectors are exact copies of one
1167 another and "1" if the first bit vector is greater than the second
1168 bit vector.
1169 · "$cmp = $vec1->Compare($vec2);"
1171 Compares the two given bit vectors, which are regarded as SIGNED num‐
1173 bers in binary representation.
1174 The method returns ""-1"" if the first bit vector is smaller than the
1176 second bit vector, "0" if the two bit vectors are exact copies of one
1177 another and "1" if the first bit vector is greater than the second
1178 bit vector.
1179 · "$string = $vector->to_Hex();"
1181 Returns a hexadecimal string representing the given bit vector.
1183 Note that this representation is quite compact, in that it only needs
1185 at most twice the number of bytes needed to store the bit vector
1186 itself, internally.
1187 Note also that since a hexadecimal digit is always worth four bits,
1189 the length of the resulting string is always a multiple of four bits,
1190 regardless of the true length (in bits) of the given bit vector.
1191 Finally, note that the LEAST significant hexadecimal digit is located
1193 at the RIGHT end of the resulting string, and the MOST significant
1194 digit at the LEFT end.
1195 · "$vector->from_Hex($string);"
1197 Allows to read in the contents of a bit vector from a hexadecimal
1199 string, such as returned by the method ""to_Hex()"" (see above).
1200 Remember that the least significant bits are always to the right of a
1202 hexadecimal string, and the most significant bits to the left. There‐
1203 fore, the string is actually read in from right to left while the bit
1204 vector is filled accordingly, 4 bits at a time, starting with the
1205 least significant bits and going upward to the most significant bits.
1206 If the given string contains less hexadecimal digits than are needed
1208 to completely fill the given bit vector, the remaining (most signifi‐
1209 cant) bits are all cleared.
1210 This also means that, even if the given string does not contain
1212 enough digits to completely fill the given bit vector, the previous
1213 contents of the bit vector are erased completely.
1214 If the given string is longer than it needs to fill the given bit
1216 vector, the superfluous characters are simply ignored.
1217 (In fact they are ignored completely - they are not even checked for
1219 proper syntax. See also below for more about that.)
1220 This behaviour is intentional so that you may read in the string rep‐
1222 resenting one bit vector into another bit vector of different size,
1223 i.e., as much of it as will fit.
1224 If during the process of reading the given string any character is
1226 encountered which is not a hexadecimal digit, a fatal syntax error
1227 ensues ("input string syntax error").
1228 · "$string = $vector->to_Bin();"
1230 Returns a binary string representing the given bit vector.
1232 Example:
1234 $vector = Bit::Vector->new(8);
1236 $vector->Primes();
1237 $string = $vector->to_Bin();
1238 print "'$string'\n";
1239 This prints:
1241 '10101100'
1243 (Bits #7, #5, #3 and #2 are set.)
1245 Note that the LEAST significant bit is located at the RIGHT end of
1247 the resulting string, and the MOST significant bit at the LEFT end.
1248 · "$vector->from_Bin($string);"
1250 This method allows you to read in the contents of a bit vector from a
1252 binary string, such as returned by the method ""to_Bin()"" (see
1253 above).
1254 Note that this method assumes that the LEAST significant bit is
1256 located at the RIGHT end of the binary string, and the MOST signifi‐
1257 cant bit at the LEFT end. Therefore, the string is actually read in
1258 from right to left while the bit vector is filled accordingly, one
1259 bit at a time, starting with the least significant bit and going
1260 upward to the most significant bit.
1261 If the given string contains less binary digits ("0" and "1") than
1263 are needed to completely fill the given bit vector, the remaining
1264 (most significant) bits are all cleared.
1265 This also means that, even if the given string does not contain
1267 enough digits to completely fill the given bit vector, the previous
1268 contents of the bit vector are erased completely.
1269 If the given string is longer than it needs to fill the given bit
1271 vector, the superfluous characters are simply ignored.
1272 (In fact they are ignored completely - they are not even checked for
1274 proper syntax. See also below for more about that.)
1275 This behaviour is intentional so that you may read in the string rep‐
1277 resenting one bit vector into another bit vector of different size,
1278 i.e., as much of it as will fit.
1279 If during the process of reading the given string any character is
1281 encountered which is not either "0" or "1", a fatal syntax error
1282 ensues ("input string syntax error").
1283 · "$string = $vector->to_Dec();"
1285 This method returns a string representing the contents of the given
1287 bit vector converted to decimal (base 10).
1288 Note that this method assumes the given bit vector to be SIGNED (and
1290 to contain a number in two's complement binary representation).
1291 Consequently, whenever the most significant bit of the given bit vec‐
1293 tor is set, the number stored in it is regarded as being NEGATIVE.
1294 The resulting string can be fed into ""from_Dec()"" (see below) in
1296 order to copy the contents of this bit vector to another one (or to
1297 restore the contents of this one). This is not advisable, though,
1298 since this would be very inefficient (there are much more efficient
1299 methods for storing and copying bit vectors in this module).
1300 Note that such conversion from binary to decimal is inherently slow
1302 since the bit vector has to be repeatedly divided by 10 with remain‐
1303 der until the quotient becomes 0 (each remainder in turn represents a
1304 single decimal digit of the resulting string).
1305 This is also true for the implementation of this method in this mod‐
1307 ule, even though a considerable effort has been made to speed it up:
1308 instead of repeatedly dividing by 10, the bit vector is repeatedly
1309 divided by the largest power of 10 that will fit into a machine word.
1310 The remainder is then repeatedly divided by 10 using only machine
1311 word arithmetics, which is much faster than dividing the whole bit
1312 vector ("divide and rule" principle).
1313 According to my own measurements, this resulted in an 8-fold speed
1315 increase over the straightforward approach.
1316 Still, conversion to decimal should be used only where absolutely
1318 necessary.
1319 Keep the resulting string stored in some variable if you need it
1321 again, instead of converting the bit vector all over again.
1322 Beware that if you set the configuration for overloaded operators to
1324 "output=decimal", this method will be called for every bit vector
1325 enclosed in double quotes!
1326 · "$vector->from_Dec($string);"
1328 This method allows you to convert a given decimal number, which may
1330 be positive or negative, into two's complement binary representation,
1331 which is then stored in the given bit vector.
1332 The decimal number should always be provided as a string, to avoid
1334 possible truncation (due to the limited precision of integers in
1335 Perl) or formatting (due to Perl's use of scientific notation for
1336 large numbers), which would lead to errors.
1337 If the binary representation of the given decimal number is too big
1339 to fit into the given bit vector (if the given bit vector does not
1340 contain enough bits to hold it), a fatal "numeric overflow error"
1341 occurs.
1342 If the input string contains other characters than decimal digits
1344 ("0-9") and an optional leading sign (""+"" or ""-""), a fatal "input
1345 string syntax error" occurs.
1346 Beware that large positive numbers which cause the most significant
1348 bit to be set (e.g. "255" in a bit vector with 8 bits) will be
1349 printed as negative numbers when converted back to decimal using the
1350 method "to_Dec()" (e.g. "-1", in our example), because numbers with
1351 the most significant bit set are considered to be negative in two's
1352 complement binary representation.
1353 Note also that while it is possible to thusly enter negative numbers
1355 as large positive numbers (e.g. "255" for "-1" in a bit vector with 8
1356 bits), the contrary isn't, i.e., you cannot enter "-255" for "+1", in
1357 our example. A fatal "numeric overflow error" will occur if you try
1358 to do so.
1359 If possible program abortion is unwanted or intolerable, use
1361 ""eval"", like this:
1362 eval { $vector->from_Dec("1152921504606846976"); };
1364 if ($@)
1365 {
1366 # an error occurred
1367 }
1368 There are four possible error messages:
1370 if ($@ =~ /item is not a string/)
1372 if ($@ =~ /input string syntax error/)
1374 if ($@ =~ /numeric overflow error/)
1376 if ($@ =~ /unable to allocate memory/)
1378 Note that the conversion from decimal to binary is costly in terms of
1380 processing time, since a lot of multiplications have to be carried
1381 out (in principle, each decimal digit must be multiplied with the
1382 binary representation of the power of 10 corresponding to its posi‐
1383 tion in the decimal number, i.e., 1, 10, 100, 1000, 10000 and so on).
1384 This is not as time consuming as the opposite conversion, from binary
1386 to decimal (where successive divisions have to be carried out, which
1387 are even more expensive than multiplications), but still noticeable.
1388 Again (as in the case of ""to_Dec()""), the implementation of this
1390 method in this module uses the principle of "divide and rule" in
1391 order to speed up the conversion, i.e., as many decimal digits as
1392 possible are first accumulated (converted) in a machine word and only
1393 then stored in the given bit vector.
1394 Even so, use this method only where absolutely necessary if speed is
1396 an important consideration in your application.
1397 Beware that if you set the configuration for overloaded operators to
1399 "input=decimal", this method will be called for every scalar operand
1400 you use!
1401 · "$string = $vector->to_Enum();"
1403 Converts the given bit vector or set into an enumeration of single
1405 indices and ranges of indices (".newsrc" style), representing the
1406 bits that are set ("1") in the bit vector.
1407 Example:
1409 $vector = Bit::Vector->new(20);
1411 $vector->Bit_On(2);
1412 $vector->Bit_On(3);
1413 $vector->Bit_On(11);
1414 $vector->Interval_Fill(5,7);
1415 $vector->Interval_Fill(13,19);
1416 print "'", $vector->to_Enum(), "'\n";
1417 which prints
1419 '2,3,5-7,11,13-19'
1421 If the given bit vector is empty, the resulting string will also be
1423 empty.
1424 Note, by the way, that the above example can also be written a little
1426 handier, perhaps, as follows:
1427 Bit::Vector->Configuration("out=enum");
1429 $vector = Bit::Vector->new(20);
1430 $vector->Index_List_Store(2,3,5,6,7,11,13,14,15,16,17,18,19);
1431 print "'$vector'\n";
1432 · "$vector->from_Enum($string);"
1434 This method first empties the given bit vector and then tries to set
1436 the bits and ranges of bits specified in the given string.
1437 The string "$string" must only contain unsigned integers or ranges of
1439 integers (two unsigned integers separated by a dash "-"), separated
1440 by commas (",").
1441 All other characters are disallowed (including white space!) and
1443 will lead to a fatal "input string syntax error".
1444 In each range, the first integer (the lower limit of the range) must
1446 always be less than or equal to the second integer (the upper limit),
1447 or a fatal "minimum > maximum index" error occurs.
1448 All integers must lie in the permitted range for the given bit vec‐
1450 tor, i.e., they must lie between "0" and ""$vector->Size()-1"".
1451 If this condition is not met, a fatal "index out of range" error
1453 occurs.
1454 If possible program abortion is unwanted or intolerable, use
1456 ""eval"", like this:
1457 eval { $vector->from_Enum("2,3,5-7,11,13-19"); };
1459 if ($@)
1460 {
1461 # an error occurred
1462 }
1463 There are four possible error messages:
1465 if ($@ =~ /item is not a string/)
1467 if ($@ =~ /input string syntax error/)
1469 if ($@ =~ /index out of range/)
1471 if ($@ =~ /minimum > maximum index/)
1473 Note that the order of the indices and ranges is irrelevant, i.e.,
1475 eval { $vector->from_Enum("11,5-7,3,13-19,2"); };
1477 results in the same vector as in the example above.
1479 Ranges and indices may also overlap.
1481 This is because each (single) index in the string is passed to the
1483 method ""Bit_On()"", internally, and each range to the method
1484 ""Interval_Fill()"".
1485 This means that the resulting bit vector is just the union of all the
1487 indices and ranges specified in the given string.
1488 · "$vector->Bit_Off($index);"
1490 Clears the bit with index "$index" in the given vector.
1492 · "$vector->Bit_On($index);"
1494 Sets the bit with index "$index" in the given vector.
1496 · "$vector->bit_flip($index)"
1498 Flips (i.e., complements) the bit with index "$index" in the given
1500 vector.
1501 Moreover, this method returns the NEW state of the bit in question,
1503 i.e., it returns "0" if the bit is cleared or "1" if the bit is set
1504 (AFTER flipping it).
1505 · "if ($vector->bit_test($index))"
1507 "if ($vector->contains($index))"
1509 Returns the current state of the bit with index "$index" in the given
1511 vector, i.e., returns "0" if it is cleared (in the "off" state) or
1512 "1" if it is set (in the "on" state).
1513 · "$vector->Bit_Copy($index,$bit);"
1515 Sets the bit with index "$index" in the given vector either to "0" or
1517 "1" depending on the boolean value "$bit".
1518 · "$vector->LSB($bit);"
1520 Allows you to set the least significant bit in the given bit vector
1522 to the value given by the boolean parameter "$bit".
1523 This is a (faster) shortcut for ""$vector->Bit_Copy(0,$bit);"".
1525 · "$vector->MSB($bit);"
1527 Allows you to set the most significant bit in the given bit vector to
1529 the value given by the boolean parameter "$bit".
1530 This is a (faster) shortcut for ""$vector->Bit_Copy($vec‐
1532 tor->Size()-1,$bit);"".
1533 · "$bit = $vector->lsb();"
1535 Returns the least significant bit of the given bit vector.
1537 This is a (faster) shortcut for ""$bit = $vector->bit_test(0);"".
1539 · "$bit = $vector->msb();"
1541 Returns the most significant bit of the given bit vector.
1543 This is a (faster) shortcut for ""$bit = $vector->bit_test($vec‐
1545 tor->Size()-1);"".
1546 · "$carry_out = $vector->rotate_left();"
1548 carry MSB vector: LSB
1550 out:
1551 +---+ +---+---+---+--- ---+---+---+---+
1552 ⎪ ⎪ <---+--- ⎪ ⎪ ⎪ ⎪ ... ⎪ ⎪ ⎪ ⎪ <---+
1553 +---+ ⎪ +---+---+---+--- ---+---+---+---+ ⎪
1554 ⎪ ⎪
1555 +------------------------------------------------+
1556 The least significant bit (LSB) is the bit with index "0", the most
1558 significant bit (MSB) is the bit with index ""$vector->Size()-1"".
1559 · "$carry_out = $vector->rotate_right();"
1561 MSB vector: LSB carry
1563 out:
1564 +---+---+---+--- ---+---+---+---+ +---+
1565 +---> ⎪ ⎪ ⎪ ⎪ ... ⎪ ⎪ ⎪ ⎪ ---+---> ⎪ ⎪
1566 ⎪ +---+---+---+--- ---+---+---+---+ ⎪ +---+
1567 ⎪ ⎪
1568 +------------------------------------------------+
1569 The least significant bit (LSB) is the bit with index "0", the most
1571 significant bit (MSB) is the bit with index ""$vector->Size()-1"".
1572 · "$carry_out = $vector->shift_left($carry_in);"
1574 carry MSB vector: LSB carry
1576 out: in:
1577 +---+ +---+---+---+--- ---+---+---+---+ +---+
1578 ⎪ ⎪ <--- ⎪ ⎪ ⎪ ⎪ ... ⎪ ⎪ ⎪ ⎪ <--- ⎪ ⎪
1579 +---+ +---+---+---+--- ---+---+---+---+ +---+
1580 The least significant bit (LSB) is the bit with index "0", the most
1582 significant bit (MSB) is the bit with index ""$vector->Size()-1"".
1583 · "$carry_out = $vector->shift_right($carry_in);"
1585 carry MSB vector: LSB carry
1587 in: out:
1588 +---+ +---+---+---+--- ---+---+---+---+ +---+
1589 ⎪ ⎪ ---> ⎪ ⎪ ⎪ ⎪ ... ⎪ ⎪ ⎪ ⎪ ---> ⎪ ⎪
1590 +---+ +---+---+---+--- ---+---+---+---+ +---+
1591 The least significant bit (LSB) is the bit with index "0", the most
1593 significant bit (MSB) is the bit with index ""$vector->Size()-1"".
1594 · "$vector->Move_Left($bits);"
1596 Shifts the given bit vector left by "$bits" bits, i.e., inserts
1598 "$bits" new bits at the lower end (least significant bit) of the bit
1599 vector, moving all other bits up by "$bits" places, thereby losing
1600 the "$bits" most significant bits.
1601 The inserted new bits are all cleared (set to the "off" state).
1603 This method does nothing if "$bits" is equal to zero.
1605 Beware that the whole bit vector is cleared WITHOUT WARNING if
1607 "$bits" is greater than or equal to the size of the given bit vector!
1608 In fact this method is equivalent to
1610 for ( $i = 0; $i < $bits; $i++ ) { $vector->shift_left(0); }
1612 except that it is much more efficient (for "$bits" greater than or
1614 equal to the number of bits in a machine word on your system) than
1615 this straightforward approach.
1616 · "$vector->Move_Right($bits);"
1618 Shifts the given bit vector right by "$bits" bits, i.e., deletes the
1620 "$bits" least significant bits of the bit vector, moving all other
1621 bits down by "$bits" places, thereby creating "$bits" new bits at the
1622 upper end (most significant bit) of the bit vector.
1623 These new bits are all cleared (set to the "off" state).
1625 This method does nothing if "$bits" is equal to zero.
1627 Beware that the whole bit vector is cleared WITHOUT WARNING if
1629 "$bits" is greater than or equal to the size of the given bit vector!
1630 In fact this method is equivalent to
1632 for ( $i = 0; $i < $bits; $i++ ) { $vector->shift_right(0); }
1634 except that it is much more efficient (for "$bits" greater than or
1636 equal to the number of bits in a machine word on your system) than
1637 this straightforward approach.
1638 · "$vector->Insert($offset,$bits);"
1640 This method inserts "$bits" fresh new bits at position "$offset" in
1642 the given bit vector.
1643 The "$bits" most significant bits are lost, and all bits starting
1645 with bit number "$offset" up to and including bit number ""$vec‐
1646 tor->Size()-$bits-1"" are moved up by "$bits" places.
1647 The now vacant "$bits" bits starting at bit number "$offset" (up to
1649 and including bit number ""$offset+$bits-1"") are then set to zero
1650 (cleared).
1651 Note that this method does NOT increase the size of the given bit
1653 vector, i.e., the bit vector is NOT extended at its upper end to
1654 "rescue" the "$bits" uppermost (most significant) bits - instead,
1655 these bits are lost forever.
1656 If you don't want this to happen, you have to increase the size of
1658 the given bit vector EXPLICITLY and BEFORE you perform the "Insert"
1659 operation, with a statement such as the following:
1660 $vector->Resize($vector->Size() + $bits);
1662 Or use the method ""Interval_Substitute()"" instead of ""Insert()"",
1664 which performs automatic growing and shrinking of its target bit vec‐
1665 tor.
1666 Note also that "$offset" must lie in the permitted range between "0"
1668 and ""$vector->Size()-1"", or a fatal "offset out of range" error
1669 will occur.
1670 If the term ""$offset + $bits"" exceeds ""$vector->Size()-1"", all
1672 the bits starting with bit number "$offset" up to bit number ""$vec‐
1673 tor->Size()-1"" are simply cleared.
1674 · "$vector->Delete($offset,$bits);"
1676 This method deletes, i.e., removes the bits starting at position
1678 "$offset" up to and including bit number ""$offset+$bits-1"" from the
1679 given bit vector.
1680 The remaining uppermost bits (starting at position ""$offset+$bits""
1682 up to and including bit number ""$vector->Size()-1"") are moved down
1683 by "$bits" places.
1684 The now vacant uppermost (most significant) "$bits" bits are then set
1686 to zero (cleared).
1687 Note that this method does NOT decrease the size of the given bit
1689 vector, i.e., the bit vector is NOT clipped at its upper end to "get
1690 rid of" the vacant "$bits" uppermost bits.
1691 If you don't want this, i.e., if you want the bit vector to shrink
1693 accordingly, you have to do so EXPLICITLY and AFTER the "Delete"
1694 operation, with a couple of statements such as these:
1695 $size = $vector->Size();
1697 if ($bits > $size) { $bits = $size; }
1698 $vector->Resize($size - $bits);
1699 Or use the method ""Interval_Substitute()"" instead of ""Delete()"",
1701 which performs automatic growing and shrinking of its target bit vec‐
1702 tor.
1703 Note also that "$offset" must lie in the permitted range between "0"
1705 and ""$vector->Size()-1"", or a fatal "offset out of range" error
1706 will occur.
1707 If the term ""$offset + $bits"" exceeds ""$vector->Size()-1"", all
1709 the bits starting with bit number "$offset" up to bit number ""$vec‐
1710 tor->Size()-1"" are simply cleared.
1711 · "$carry = $vector->increment();"
1713 This method increments the given bit vector.
1715 Note that this method regards bit vectors as being unsigned, i.e.,
1717 the largest possible positive number is directly followed by the
1718 smallest possible (or greatest possible, speaking in absolute terms)
1719 negative number:
1720 before: 2 ^ (b-1) - 1 (= "0111...1111")
1722 after: 2 ^ (b-1) (= "1000...0000")
1723 where ""b"" is the number of bits of the given bit vector.
1725 The method returns "false" ("0") in all cases except when a carry
1727 over occurs (in which case it returns "true", i.e., "1"), which hap‐
1728 pens when the number "1111...1111" is incremented, which gives
1729 "0000...0000" plus a carry over to the next higher (binary) digit.
1730 This can be used for the terminating condition of a "while" loop, for
1732 instance, in order to cycle through all possible values the bit vec‐
1733 tor can assume.
1734 · "$carry = $vector->decrement();"
1736 This method decrements the given bit vector.
1738 Note that this method regards bit vectors as being unsigned, i.e.,
1740 the smallest possible (or greatest possible, speaking in absolute
1741 terms) negative number is directly followed by the largest possible
1742 positive number:
1743 before: 2 ^ (b-1) (= "1000...0000")
1745 after: 2 ^ (b-1) - 1 (= "0111...1111")
1746 where ""b"" is the number of bits of the given bit vector.
1748 The method returns "false" ("0") in all cases except when a carry
1750 over occurs (in which case it returns "true", i.e., "1"), which hap‐
1751 pens when the number "0000...0000" is decremented, which gives
1752 "1111...1111" minus a carry over to the next higher (binary) digit.
1753 This can be used for the terminating condition of a "while" loop, for
1755 instance, in order to cycle through all possible values the bit vec‐
1756 tor can assume.
1757 · "$overflow = $vec2->inc($vec1);"
1759 This method copies the contents of bit vector "$vec1" to bit vector
1761 "$vec2" and increments the copy (not the original).
1762 If by incrementing the number its sign becomes invalid, the return
1764 value ("overflow" flag) will be true ("1"), or false ("0") if not.
1765 (See the description of the method "add()" below for a more in-depth
1766 explanation of what "overflow" means).
1767 Note that in-place operation is also possible, i.e., "$vec1" and
1769 "$vec2" may be identical.
1770 · "$overflow = $vec2->dec($vec1);"
1772 This method copies the contents of bit vector "$vec1" to bit vector
1774 "$vec2" and decrements the copy (not the original).
1775 If by decrementing the number its sign becomes invalid, the return
1777 value ("overflow" flag) will be true ("1"), or false ("0") if not.
1778 (See the description of the method "subtract()" below for a more in-
1779 depth explanation of what "overflow" means).
1780 Note that in-place operation is also possible, i.e., "$vec1" and
1782 "$vec2" may be identical.
1783 · "$carry = $vec3->add($vec1,$vec2,$carry);"
1785 "($carry,$overflow) = $vec3->add($vec1,$vec2,$carry);"
1787 This method adds the two numbers contained in bit vector "$vec1" and
1789 "$vec2" with carry "$carry" and stores the result in bit vector
1790 "$vec3".
1791 I.e.,
1793 $vec3 = $vec1 + $vec2 + $carry
1794 Note that the "$carry" parameter is a boolean value, i.e., only its
1796 least significant bit is taken into account. (Think of it as though
1797 ""$carry &= 1;"" was always executed internally.)
1798 In scalar context, the method returns a boolean value which indicates
1800 if a carry over (to the next higher bit position) has occured. In
1801 list context, the method returns the carry and the overflow flag (in
1802 this order).
1803 The overflow flag is true ("1") if the sign (i.e., the most signifi‐
1805 cant bit) of the result is wrong. This can happen when adding two
1806 very large positive numbers or when adding two (by their absolute
1807 value) very large negative numbers. See also further below.
1808 The carry in- and output is needed mainly for cascading, i.e., to add
1810 numbers that are fragmented into several pieces.
1811 Example:
1813 # initialize
1815 for ( $i = 0; $i < $n; $i++ )
1817 {
1818 $a[$i] = Bit::Vector->new($bits);
1819 $b[$i] = Bit::Vector->new($bits);
1820 $c[$i] = Bit::Vector->new($bits);
1821 }
1822 # fill @a and @b
1824 # $a[ 0 ] is low order part,
1826 # $a[$n-1] is high order part,
1827 # and same for @b
1828 # add
1830 $carry = 0;
1832 for ( $i = 0; $i < $n; $i++ )
1833 {
1834 $carry = $c[$i]->add($a[$i],$b[$i],$carry);
1835 }
1836 Note that it makes no difference to this method whether the numbers
1838 in "$vec1" and "$vec2" are unsigned or signed (i.e., in two's comple‐
1839 ment binary representation).
1840 Note however that the return value (carry flag) is not meaningful
1842 when the numbers are SIGNED.
1843 Moreover, when the numbers are signed, a special type of error can
1845 occur which is commonly called an "overflow error".
1846 An overflow error occurs when the sign of the result (its most sig‐
1848 nificant bit) is flipped (i.e., falsified) by a carry over from the
1849 next-lower bit position ("MSB-1").
1850 In fact matters are a bit more complicated than that: the overflow
1852 flag is set to "true" whenever there is a carry over from bit posi‐
1853 tion MSB-1 to the most significant bit (MSB) but no carry over from
1854 the MSB to the output carry flag, or vice-versa, i.e., when there is
1855 no carry over from bit position MSB-1 to the most significant bit
1856 (MSB) but a carry over to the output carry flag.
1857 Thus the overflow flag is the result of an exclusive-or operation
1859 between incoming and outgoing carry over at the most significant bit
1860 position.
1861 · "$carry = $vec3->subtract($vec1,$vec2,$carry);"
1863 "($carry,$overflow) = $vec3->subtract($vec1,$vec2,$carry);"
1865 This method subtracts the two numbers contained in bit vector "$vec1"
1867 and "$vec2" with carry "$carry" and stores the result in bit vector
1868 "$vec3".
1869 I.e.,
1871 $vec3 = $vec1 - $vec2 - $carry
1872 Note that the "$carry" parameter is a boolean value, i.e., only its
1874 least significant bit is taken into account. (Think of it as though
1875 ""$carry &= 1;"" was always executed internally.)
1876 In scalar context, the method returns a boolean value which indicates
1878 if a carry over (to the next higher bit position) has occured. In
1879 list context, the method returns the carry and the overflow flag (in
1880 this order).
1881 The overflow flag is true ("1") if the sign (i.e., the most signifi‐
1883 cant bit) of the result is wrong. This can happen when subtracting a
1884 very large negative number from a very large positive number or
1885 vice-versa. See also further below.
1886 The carry in- and output is needed mainly for cascading, i.e., to
1888 subtract numbers that are fragmented into several pieces.
1889 Example:
1891 # initialize
1893 for ( $i = 0; $i < $n; $i++ )
1895 {
1896 $a[$i] = Bit::Vector->new($bits);
1897 $b[$i] = Bit::Vector->new($bits);
1898 $c[$i] = Bit::Vector->new($bits);
1899 }
1900 # fill @a and @b
1902 # $a[ 0 ] is low order part,
1904 # $a[$n-1] is high order part,
1905 # and same for @b
1906 # subtract
1908 $carry = 0;
1910 for ( $i = 0; $i < $n; $i++ )
1911 {
1912 $carry = $c[$i]->subtract($a[$i],$b[$i],$carry);
1913 }
1914 Note that it makes no difference to this method whether the numbers
1916 in "$vec1" and "$vec2" are unsigned or signed (i.e., in two's comple‐
1917 ment binary representation).
1918 Note however that the return value (carry flag) is not meaningful
1920 when the numbers are SIGNED.
1921 Moreover, when the numbers are signed, a special type of error can
1923 occur which is commonly called an "overflow error".
1924 An overflow error occurs when the sign of the result (its most sig‐
1926 nificant bit) is flipped (i.e., falsified) by a carry over from the
1927 next-lower bit position ("MSB-1").
1928 In fact matters are a bit more complicated than that: the overflow
1930 flag is set to "true" whenever there is a carry over from bit posi‐
1931 tion MSB-1 to the most significant bit (MSB) but no carry over from
1932 the MSB to the output carry flag, or vice-versa, i.e., when there is
1933 no carry over from bit position MSB-1 to the most significant bit
1934 (MSB) but a carry over to the output carry flag.
1935 Thus the overflow flag is the result of an exclusive-or operation
1937 between incoming and outgoing carry over at the most significant bit
1938 position.
1939 · "$vec2->Neg($vec1);"
1941 "$vec2->Negate($vec1);"
1943 This method calculates the two's complement of the number in bit vec‐
1945 tor "$vec1" and stores the result in bit vector "$vec2".
1946 Calculating the two's complement of a given number in binary repre‐
1948 sentation consists of inverting all bits and incrementing the result
1949 by one.
1950 This is the same as changing the sign of the given number from ""+""
1952 to ""-"" or vice-versa. In other words, applying this method twice on
1953 a given number yields the original number again.
1954 Note that in-place processing is also possible, i.e., "$vec1" and
1956 "$vec2" may be identical.
1957 Most importantly, beware that this method produces a counter-intu‐
1959 itive result if the number contained in bit vector "$vec1" is "2 ^
1960 (n-1)" (i.e., "1000...0000"), where ""n"" is the number of bits the
1961 given bit vector contains: The negated value of this number is the
1962 number itself!
1963 · "$vec2->Abs($vec1);"
1965 "$vec2->Absolute($vec1);"
1967 Depending on the sign (i.e., the most significant bit) of the number
1969 in bit vector "$vec1", the contents of bit vector "$vec1" are copied
1970 to bit vector "$vec2" either with the method ""Copy()"" (if the num‐
1971 ber in bit vector "$vec1" is positive), or with ""Negate()"" (if the
1972 number in bit vector "$vec1" is negative).
1973 In other words, this method calculates the absolute value of the num‐
1975 ber in bit vector "$vec1" and stores the result in bit vector
1976 "$vec2".
1977 Note that in-place processing is also possible, i.e., "$vec1" and
1979 "$vec2" may be identical.
1980 Most importantly, beware that this method produces a counter-intu‐
1982 itive result if the number contained in bit vector "$vec1" is "2 ^
1983 (n-1)" (i.e., "1000...0000"), where ""n"" is the number of bits the
1984 given bit vector contains: The absolute value of this number is the
1985 number itself, even though this number is still negative by defini‐
1986 tion (the most significant bit is still set)!
1987 · "$sign = $vector->Sign();"
1989 This method returns "0" if all bits in the given bit vector are
1991 cleared, i.e., if the given bit vector contains the number "0", or if
1992 the given bit vector has a length of zero (contains no bits at all).
1993 If not all bits are cleared, this method returns ""-1"" if the most
1995 significant bit is set (i.e., if the bit vector contains a negative
1996 number), or "1" otherwise (i.e., if the bit vector contains a posi‐
1997 tive number).
1998 · "$vec3->Multiply($vec1,$vec2);"
2000 This method multiplies the two numbers contained in bit vector
2002 "$vec1" and "$vec2" and stores the result in bit vector "$vec3".
2003 Note that this method regards its arguments as SIGNED.
2005 If you want to make sure that a large number can never be treated as
2007 being negative by mistake, make your bit vectors at least one bit
2008 longer than the largest number you wish to represent, right from the
2009 start, or proceed as follows:
2010 $msb1 = $vec1->msb();
2012 $msb2 = $vec2->msb();
2013 $vec1->Resize($vec1->Size()+1);
2014 $vec2->Resize($vec2->Size()+1);
2015 $vec3->Resize($vec3->Size()+1);
2016 $vec1->MSB($msb1);
2017 $vec2->MSB($msb2);
2018 $vec3->Multiply($vec1,$vec2);
2019 Note also that all three bit vector arguments must in principle obey
2021 the rule of matching sizes, but that the bit vector "$vec3" may be
2022 larger than the two factors "$vec1" and "$vec2".
2023 In fact multiplying two binary numbers with ""n"" bits may yield a
2025 result which is at most ""2n"" bits long.
2026 Therefore, it is usually a good idea to let bit vector "$vec3" have
2028 twice the size of bit vector "$vec1" and "$vec2", unless you are
2029 absolutely sure that the result will fit into a bit vector of the
2030 same size as the two factors.
2031 If you are wrong, a fatal "numeric overflow error" will occur.
2033 Finally, note that in-place processing is possible, i.e., "$vec3" may
2035 be identical with "$vec1" or "$vec2", or both.
2036 · "$quot->Divide($vec1,$vec2,$rest);"
2038 This method divides the two numbers contained in bit vector "$vec1"
2040 and "$vec2" and stores the quotient in bit vector "$quot" and the
2041 remainder in bit vector "$rest".
2042 I.e.,
2044 $quot = $vec1 / $vec2; # div
2045 $rest = $vec1 % $vec2; # mod
2046 Therefore, "$quot" and "$rest" must be two DISTINCT bit vectors, or a
2048 fatal "result vector(s) must be distinct" error will occur.
2049 Note also that a fatal "division by zero error" will occur if "$vec2"
2051 is equal to zero.
2052 Note further that this method regards its arguments as SIGNED.
2054 If you want to make sure that a large number can never be treated as
2056 being negative by mistake, make your bit vectors at least one bit
2057 longer than the largest number you wish to represent, right from the
2058 start, or proceed as follows:
2059 $msb1 = $vec1->msb();
2061 $msb2 = $vec2->msb();
2062 $vec1->Resize($vec1->Size()+1);
2063 $vec2->Resize($vec2->Size()+1);
2064 $quot->Resize($quot->Size()+1);
2065 $rest->Resize($rest->Size()+1);
2066 $vec1->MSB($msb1);
2067 $vec2->MSB($msb2);
2068 $quot->Divide($vec1,$vec2,$rest);
2069 Finally, note that in-place processing is possible, i.e., "$quot" may
2071 be identical with "$vec1" or "$vec2" or both, and "$rest" may also be
2072 identical with "$vec1" or "$vec2" or both, as long as "$quot" and
2073 "$rest" are distinct. (!)
2074 · "$vecgcd->GCD($veca,$vecb);"
2076 This method calculates the "Greatest Common Divisor" of the two num‐
2078 bers contained in bit vector "$veca" and "$vecb" and stores the
2079 result in bit vector "$vecgcd".
2080 The method uses Euklid's algorithm internally:
2082 int GCD(int a, int b)
2084 {
2085 int t;
2086 while (b != 0)
2088 {
2089 t = a % b; /* = remainder of (a div b) */
2090 a = b;
2091 b = t;
2092 }
2093 return(a);
2094 }
2095 Note that "GCD(z,0) == GCD(0,z) == z".
2097 · "$vecgcd->GCD($vecx,$vecy,$veca,$vecb);"
2099 This variant of the "GCD" method calculates the "Greatest Common
2101 Divisor" of the two numbers contained in bit vector "$veca" and
2102 "$vecb" and stores the result in bit vector "$vecgcd".
2103 Moreover, it determines the two factors which are necessary in order
2105 to represent the greatest common divisor as a linear combination of
2106 its two arguments, i.e., the two factors "x" and "y" so that
2107 "GCD(a,b) == x * a + y * b", and stores them in bit vector "$vecx"
2108 and "$vecy", respectively.
2109 For example:
2111 a = 2322
2113 b = 654
2114 GCD( 2322, 654 ) == 6
2116 x = 20
2118 y = -71
2119 20 * 2322 - 71 * 654 == 6
2121 Please see http://www.cut-the-knot.org/blue/extension.shtml for an
2123 explanation of how this extension of Euklid's algorithm works.
2124 · "$vec3->Power($vec1,$vec2);"
2126 This method calculates the exponentiation of base "$vec1" elevated to
2128 the "$vec2" power, i.e., ""$vec1 ** $vec2"", and stores the result in
2129 bit vector "$vec3".
2130 The method uses an efficient divide-and-conquer algorithm:
2132 Suppose the exponent is (decimal) 13, for example. The binary repre‐
2134 sentation of this exponent is "1101".
2135 This means we want to calculate
2137 $vec1 * $vec1 * $vec1 * $vec1 * $vec1 * $vec1 * $vec1 * $vec1 *
2139 $vec1 * $vec1 * $vec1 * $vec1 *
2140 $vec1
2141 That is, "$vec1" multiplied with itself 13 times. The grouping into
2143 lines above is no coincidence. The first line comprises 8 factors,
2144 the second contains 4, and the last line just one. This just happens
2145 to be the binary representation of 13. ";-)"
2146 We then calculate a series of squares (of squares of squares...) of
2148 the base, i.e.,
2149 $power[0] = $vec1;
2151 $power[1] = $vec1 * $vec1;
2152 $power[2] = $power[1] * $power[1];
2153 $power[3] = $power[2] * $power[2];
2154 etc.
2155 To calculate the power of our example, we simply initialize our
2157 result with 1 and consecutively multiply it with the items of the
2158 series of powers we just calculated, if the corresponding bit of the
2159 binary representation of the exponent is set:
2160 $result = 1;
2162 $result *= $power[0] if ($vec2 & 1);
2163 $result *= $power[1] if ($vec2 & 2);
2164 $result *= $power[2] if ($vec2 & 4);
2165 $result *= $power[3] if ($vec2 & 8);
2166 etc.
2167 The bit vector "$vec3" must be of the same size as the base "$vec1"
2169 or greater. "$vec3" and "$vec1" may be the same vector (i.e., in-
2170 place calculation as in ""$vec1 **= $vec2;"" is possible), but
2171 "$vec3" and "$vec2" must be distinct. Finally, the exponent "$vec2"
2172 must be positive. A fatal error occurs if any of these conditions is
2173 not met.
2174 · "$vector->Block_Store($buffer);"
2176 This method allows you to load the contents of a given bit vector in
2178 one go.
2179 This is useful when you store the contents of a bit vector in a file,
2181 for instance (using method ""Block_Read()""), and when you want to
2182 restore the previously saved bit vector.
2183 For this, "$buffer" MUST be a string (NO automatic conversion from
2185 numeric to string is provided here as would normally in Perl!) con‐
2186 taining the bit vector in "low order byte first" order.
2187 If the given string is shorter than what is needed to completely fill
2189 the given bit vector, the remaining (most significant) bytes of the
2190 bit vector are filled with zeros, i.e., the previous contents of the
2191 bit vector are always erased completely.
2192 If the given string is longer than what is needed to completely fill
2194 the given bit vector, the superfluous bytes are simply ignored.
2195 See "sysread" in perlfunc for how to read in the contents of "$buf‐
2197 fer" from a file prior to passing it to this method.
2198 · "$buffer = $vector->Block_Read();"
2200 This method allows you to export the contents of a given bit vector
2202 in one block.
2203 This is useful when you want to save the contents of a bit vector for
2205 later, for instance in a file.
2206 The advantage of this method is that it allows you to do so in the
2208 compactest possible format, in binary.
2209 The method returns a Perl string which contains an exact copy of the
2211 contents of the given bit vector in "low order byte first" order.
2212 See "syswrite" in perlfunc for how to write the data from this string
2214 to a file.
2215 · "$size = $vector->Word_Size();"
2217 Each bit vector is internally organized as an array of machine words.
2219 The methods whose names begin with "Word_" allow you to access this
2221 internal array of machine words.
2222 Note that because the size of a machine word may vary from system to
2224 system, these methods are inherently MACHINE-DEPENDENT!
2225 Therefore, DO NOT USE these methods unless you are absolutely certain
2227 that portability of your code is not an issue!
2228 You have been warned!
2230 To be machine-independent, use the methods whose names begin with
2232 ""Chunk_"" instead, with chunk sizes no greater than 32 bits.
2233 The method ""Word_Size()"" returns the number of machine words that
2235 the internal array of words of the given bit vector contains.
2236 This is similar in function to the term ""scalar(@array)"" for a Perl
2238 array.
2239 · "$vector->Word_Store($offset,$word);"
2241 This method allows you to store a given value "$word" at a given
2243 position "$offset" in the internal array of words of the given bit
2244 vector.
2245 Note that "$offset" must lie in the permitted range between "0" and
2247 ""$vector->Word_Size()-1"", or a fatal "offset out of range" error
2248 will occur.
2249 This method is similar in function to the expression ""$array[$off‐
2251 set] = $word;"" for a Perl array.
2252 · "$word = $vector->Word_Read($offset);"
2254 This method allows you to access the value of a given machine word at
2256 position "$offset" in the internal array of words of the given bit
2257 vector.
2258 Note that "$offset" must lie in the permitted range between "0" and
2260 ""$vector->Word_Size()-1"", or a fatal "offset out of range" error
2261 will occur.
2262 This method is similar in function to the expression ""$word =
2264 $array[$offset];"" for a Perl array.
2265 · "$vector->Word_List_Store(@words);"
2267 This method allows you to store a list of values "@words" in the
2269 internal array of machine words of the given bit vector.
2270 Thereby the LEFTMOST value in the list ("$words[0]") is stored in the
2272 LEAST significant word of the internal array of words (the one with
2273 offset "0"), the next value from the list ("$words[1]") is stored in
2274 the word with offset "1", and so on, as intuitively expected.
2275 If the list "@words" contains fewer elements than the internal array
2277 of words of the given bit vector contains machine words, the remain‐
2278 ing (most significant) words are filled with zeros.
2279 If the list "@words" contains more elements than the internal array
2281 of words of the given bit vector contains machine words, the super‐
2282 fluous values are simply ignored.
2283 This method is comparable in function to the expression ""@array =
2285 @words;"" for a Perl array.
2286 · "@words = $vector->Word_List_Read();"
2288 This method allows you to retrieve the internal array of machine
2290 words of the given bit vector all at once.
2291 Thereby the LEFTMOST value in the returned list ("$words[0]") is the
2293 LEAST significant word from the given bit vector, and the RIGHTMOST
2294 value in the returned list ("$words[$#words]") is the MOST signifi‐
2295 cant word of the given bit vector.
2296 This method is similar in function to the expression ""@words =
2298 @array;"" for a Perl array.
2299 · "$vector->Word_Insert($offset,$count);"
2301 This method inserts "$count" empty new machine words at position
2303 "$offset" in the internal array of words of the given bit vector.
2304 The "$count" most significant words are lost, and all words starting
2306 with word number "$offset" up to and including word number ""$vec‐
2307 tor->Word_Size()-$count-1"" are moved up by "$count" places.
2308 The now vacant "$count" words starting at word number "$offset" (up
2310 to and including word number ""$offset+$count-1"") are then set to
2311 zero (cleared).
2312 Note that this method does NOT increase the size of the given bit
2314 vector, i.e., the bit vector is NOT extended at its upper end to
2315 "rescue" the "$count" uppermost (most significant) words - instead,
2316 these words are lost forever.
2317 If you don't want this to happen, you have to increase the size of
2319 the given bit vector EXPLICITLY and BEFORE you perform the "Insert"
2320 operation, with a statement such as the following:
2321 $vector->Resize($vector->Size() + $count * Bit::Vector->Word_Bits());
2323 Note also that "$offset" must lie in the permitted range between "0"
2325 and ""$vector->Word_Size()-1"", or a fatal "offset out of range"
2326 error will occur.
2327 If the term ""$offset + $count"" exceeds ""$vector->Word_Size()-1"",
2329 all the words starting with word number "$offset" up to word number
2330 ""$vector->Word_Size()-1"" are simply cleared.
2331 · "$vector->Word_Delete($offset,$count);"
2333 This method deletes, i.e., removes the words starting at position
2335 "$offset" up to and including word number ""$offset+$count-1"" from
2336 the internal array of machine words of the given bit vector.
2337 The remaining uppermost words (starting at position ""$off‐
2339 set+$count"" up to and including word number ""$vec‐
2340 tor->Word_Size()-1"") are moved down by "$count" places.
2341 The now vacant uppermost (most significant) "$count" words are then
2343 set to zero (cleared).
2344 Note that this method does NOT decrease the size of the given bit
2346 vector, i.e., the bit vector is NOT clipped at its upper end to "get
2347 rid of" the vacant "$count" uppermost words.
2348 If you don't want this, i.e., if you want the bit vector to shrink
2350 accordingly, you have to do so EXPLICITLY and AFTER the "Delete"
2351 operation, with a couple of statements such as these:
2352 $bits = $vector->Size();
2354 $count *= Bit::Vector->Word_Bits();
2355 if ($count > $bits) { $count = $bits; }
2356 $vector->Resize($bits - $count);
2357 Note also that "$offset" must lie in the permitted range between "0"
2359 and ""$vector->Word_Size()-1"", or a fatal "offset out of range"
2360 error will occur.
2361 If the term ""$offset + $count"" exceeds ""$vector->Word_Size()-1"",
2363 all the words starting with word number "$offset" up to word number
2364 ""$vector->Word_Size()-1"" are simply cleared.
2365 · "$vector->Chunk_Store($chunksize,$offset,$chunk);"
2367 This method allows you to set more than one bit at a time with dif‐
2369 ferent values.
2370 You can access chunks (i.e., ranges of contiguous bits) between one
2372 and at most ""Bit::Vector->Long_Bits()"" bits wide.
2373 In order to be portable, though, you should never use chunk sizes
2375 larger than 32 bits.
2376 If the given "$chunksize" does not lie between "1" and ""Bit::Vec‐
2378 tor->Long_Bits()"", a fatal "chunk size out of range" error will
2379 occur.
2380 The method copies the "$chunksize" least significant bits from the
2382 value "$chunk" to the given bit vector, starting at bit position
2383 "$offset" and proceeding upwards until bit number ""$offset+$chunk‐
2384 size-1"".
2385 (I.e., bit number "0" of "$chunk" becomes bit number "$offset" in the
2387 given bit vector, and bit number ""$chunksize-1"" becomes bit number
2388 ""$offset+$chunksize-1"".)
2389 If the term ""$offset+$chunksize-1"" exceeds ""$vector->Size()-1"",
2391 the corresponding superfluous (most significant) bits from "$chunk"
2392 are simply ignored.
2393 Note that "$offset" itself must lie in the permitted range between
2395 "0" and ""$vector->Size()-1"", or a fatal "offset out of range" error
2396 will occur.
2397 This method (as well as the other ""Chunk_"" methods) is useful, for
2399 example, when you are reading in data in chunks of, say, 8 bits,
2400 which you need to access later, say, using 16 bits at a time (like
2401 audio CD wave files, for instance).
2402 · "$chunk = $vector->Chunk_Read($chunksize,$offset);"
2404 This method allows you to read the values of more than one bit at a
2406 time.
2407 You can read chunks (i.e., ranges of contiguous bits) between one and
2409 at most ""Bit::Vector->Long_Bits()"" bits wide.
2410 In order to be portable, though, you should never use chunk sizes
2412 larger than 32 bits.
2413 If the given "$chunksize" does not lie between "1" and ""Bit::Vec‐
2415 tor->Long_Bits()"", a fatal "chunk size out of range" error will
2416 occur.
2417 The method returns the "$chunksize" bits from the given bit vector
2419 starting at bit position "$offset" and proceeding upwards until bit
2420 number ""$offset+$chunksize-1"".
2421 (I.e., bit number "$offset" of the given bit vector becomes bit num‐
2423 ber "0" of the returned value, and bit number ""$offset+$chunk‐
2424 size-1"" becomes bit number ""$chunksize-1"".)
2425 If the term ""$offset+$chunksize-1"" exceeds ""$vector->Size()-1"",
2427 the non-existent bits are simply not returned.
2428 Note that "$offset" itself must lie in the permitted range between
2430 "0" and ""$vector->Size()-1"", or a fatal "offset out of range" error
2431 will occur.
2432 · "$vector->Chunk_List_Store($chunksize,@chunks);"
2434 This method allows you to fill the given bit vector with a list of
2436 data packets ("chunks") of any size ("$chunksize") you like (within
2437 certain limits).
2438 In fact the given "$chunksize" must lie in the range between "1" and
2440 ""Bit::Vector->Long_Bits()"", or a fatal "chunk size out of range"
2441 error will occur.
2442 In order to be portable, though, you should never use chunk sizes
2444 larger than 32 bits.
2445 The given bit vector is thereby filled in ascending order: The first
2447 chunk from the list (i.e., "$chunks[0]") fills the "$chunksize" least
2448 significant bits, the next chunk from the list ("$chunks[1]") fills
2449 the bits number "$chunksize" to number ""2*$chunksize-1"", the third
2450 chunk ("$chunks[2]") fills the bits number ""2*$chunksize"", to num‐
2451 ber ""3*$chunksize-1"", and so on.
2452 If there a less chunks in the list than are needed to fill the entire
2454 bit vector, the remaining (most significant) bits are cleared, i.e.,
2455 the previous contents of the given bit vector are always erased com‐
2456 pletely.
2457 If there are more chunks in the list than are needed to fill the
2459 entire bit vector, and/or if a chunk extends beyond ""$vec‐
2460 tor->Size()-1"" (which happens whenever ""$vector->Size()"" is not a
2461 multiple of "$chunksize"), the superfluous chunks and/or bits are
2462 simply ignored.
2463 The method is useful, for example (and among many other applica‐
2465 tions), for the conversion of packet sizes in a data stream.
2466 This method can also be used to store an octal string in a given bit
2468 vector:
2469 $vector->Chunk_List_Store(3, split(//, reverse $string));
2471 Note however that unlike the conversion methods ""from_Hex()"",
2473 ""from_Bin()"", ""from_Dec()"" and ""from_Enum()"", this statement
2474 does not include any syntax checking, i.e., it may fail silently,
2475 without warning.
2476 To perform syntax checking, add the following statements:
2478 if ($string =~ /^[0-7]+$/)
2480 {
2481 # okay, go ahead with conversion as shown above
2482 }
2483 else
2484 {
2485 # error, string contains other than octal characters
2486 }
2487 Another application is to store a repetitive pattern in a given bit
2489 vector:
2490 $pattern = 0xDEADBEEF;
2492 $length = 32; # = length of $pattern in bits
2493 $size = $vector->Size();
2494 $factor = int($size / $length);
2495 if ($size % $length) { $factor++; }
2496 $vector->Chunk_List_Store($length, ($pattern) x $factor);
2497 · "@chunks = $vector->Chunk_List_Read($chunksize);"
2499 This method allows you to access the contents of the given bit vector
2501 in form of a list of data packets ("chunks") of a size ("$chunksize")
2502 of your choosing (within certain limits).
2503 In fact the given "$chunksize" must lie in the range between "1" and
2505 ""Bit::Vector->Long_Bits()"", or a fatal "chunk size out of range"
2506 error will occur.
2507 In order to be portable, though, you should never use chunk sizes
2509 larger than 32 bits.
2510 The given bit vector is thereby read in ascending order: The "$chunk‐
2512 size" least significant bits (bits number "0" to ""$chunksize-1"")
2513 become the first chunk in the returned list (i.e., "$chunks[0]"). The
2514 bits number "$chunksize" to ""2*$chunksize-1"" become the next chunk
2515 in the list ("$chunks[1]"), and so on.
2516 If ""$vector->Size()"" is not a multiple of "$chunksize", the last
2518 chunk in the list will contain fewer bits than "$chunksize".
2519 BEWARE that for large bit vectors and/or small values of "$chunk‐
2521 size", the number of returned list elements can be extremely large!
2522 BE CAREFUL!
2523 You could blow up your application with lack of memory (each list
2525 element is a full-grown Perl scalar, internally, with an associated
2526 memory overhead for its administration!) or at least cause a notice‐
2527 able, more or less long-lasting "freeze" of your application!
2528 Possible applications:
2530 The method is especially useful in the conversion of packet sizes in
2532 a data stream.
2533 This method can also be used to convert a given bit vector to a
2535 string of octal numbers:
2536 $string = reverse join('', $vector->Chunk_List_Read(3));
2538 · "$vector->Index_List_Remove(@indices);"
2540 This method allows you to specify a list of indices of bits which
2542 should be turned off in the given bit vector.
2543 In fact this method is a shortcut for
2545 foreach $index (@indices)
2547 {
2548 $vector->Bit_Off($index);
2549 }
2550 In contrast to all other import methods in this module, this method
2552 does NOT clear the given bit vector before processing its list of
2553 arguments.
2554 Instead, this method allows you to accumulate the results of various
2556 consecutive calls.
2557 (The same holds for the method ""Index_List_Store()"". As a conse‐
2559 quence, you can "wipe out" what you did using the method
2560 ""Index_List_Remove()"" by passing the identical argument list to the
2561 method ""Index_List_Store()"".)
2562 · "$vector->Index_List_Store(@indices);"
2564 This method allows you to specify a list of indices of bits which
2566 should be turned on in the given bit vector.
2567 In fact this method is a shortcut for
2569 foreach $index (@indices)
2571 {
2572 $vector->Bit_On($index);
2573 }
2574 In contrast to all other import methods in this module, this method
2576 does NOT clear the given bit vector before processing its list of
2577 arguments.
2578 Instead, this method allows you to accumulate the results of various
2580 consecutive calls.
2581 (The same holds for the method ""Index_List_Remove()"". As a conse‐
2583 quence, you can "wipe out" what you did using the method
2584 ""Index_List_Store()"" by passing the identical argument list to the
2585 method ""Index_List_Remove()"".)
2586 · "@indices = $vector->Index_List_Read();"
2588 This method returns a list of Perl scalars.
2590 The list contains one scalar for each set bit in the given bit vec‐
2592 tor.
2593 BEWARE that for large bit vectors, this can result in a literally
2595 overwhelming number of list elements! BE CAREFUL! You could run out
2596 of memory or slow down your application considerably!
2597 Each scalar contains the number of the index corresponding to the bit
2599 in question.
2600 These indices are always returned in ascending order.
2602 If the given bit vector is empty (contains only cleared bits) or if
2604 it has a length of zero (if it contains no bits at all), the method
2605 returns an empty list.
2606 This method can be useful, for instance, to obtain a list of prime
2608 numbers:
2609 $limit = 1000; # or whatever
2611 $vector = Bit::Vector->new($limit+1);
2612 $vector->Primes();
2613 @primes = $vector->Index_List_Read();
2614 · "$vec3->Or($vec1,$vec2);"
2616 "$set3->Union($set1,$set2);"
2618 This method calculates the union of "$set1" and "$set2" and stores
2620 the result in "$set3".
2621 This is usually written as ""$set3 = $set1 u $set2"" in set theory
2623 (where "u" is the "cup" operator).
2624 (On systems where the "cup" character is unavailable this operator is
2626 often denoted by a plus sign "+".)
2627 In-place calculation is also possible, i.e., "$set3" may be identical
2629 with "$set1" or "$set2" or both.
2630 · "$vec3->And($vec1,$vec2);"
2632 "$set3->Intersection($set1,$set2);"
2634 This method calculates the intersection of "$set1" and "$set2" and
2636 stores the result in "$set3".
2637 This is usually written as ""$set3 = $set1 n $set2"" in set theory
2639 (where "n" is the "cap" operator).
2640 (On systems where the "cap" character is unavailable this operator is
2642 often denoted by an asterisk "*".)
2643 In-place calculation is also possible, i.e., "$set3" may be identical
2645 with "$set1" or "$set2" or both.
2646 · "$vec3->AndNot($vec1,$vec2);"
2648 "$set3->Difference($set1,$set2);"
2650 This method calculates the difference of "$set1" less "$set2" and
2652 stores the result in "$set3".
2653 This is usually written as ""$set3 = $set1 \ $set2"" in set theory
2655 (where "\" is the "less" operator).
2656 In-place calculation is also possible, i.e., "$set3" may be identical
2658 with "$set1" or "$set2" or both.
2659 · "$vec3->Xor($vec1,$vec2);"
2661 "$set3->ExclusiveOr($set1,$set2);"
2663 This method calculates the symmetric difference of "$set1" and
2665 "$set2" and stores the result in "$set3".
2666 This can be written as ""$set3 = ($set1 u $set2) \ ($set1 n $set2)""
2668 in set theory (the union of the two sets less their intersection).
2669 When sets are implemented as bit vectors then the above formula is
2671 equivalent to the exclusive-or between corresponding bits of the two
2672 bit vectors (hence the name of this method).
2673 Note that this method is also much more efficient than evaluating the
2675 above formula explicitly since it uses a built-in machine language
2676 instruction internally.
2677 In-place calculation is also possible, i.e., "$set3" may be identical
2679 with "$set1" or "$set2" or both.
2680 · "$vec2->Not($vec1);"
2682 "$set2->Complement($set1);"
2684 This method calculates the complement of "$set1" and stores the
2686 result in "$set2".
2687 In "big integer" arithmetic, this is equivalent to calculating the
2689 one's complement of the number stored in the bit vector "$set1" in
2690 binary representation.
2691 In-place calculation is also possible, i.e., "$set2" may be identical
2693 with "$set1".
2694 · "if ($set1->subset($set2))"
2696 Returns "true" ("1") if "$set1" is a subset of "$set2" (i.e., com‐
2698 pletely contained in "$set2") and "false" ("0") otherwise.
2699 This means that any bit which is set ("1") in "$set1" must also be
2701 set in "$set2", but "$set2" may contain set bits which are not set in
2702 "$set1", in order for the condition of subset relationship to be true
2703 between these two sets.
2704 Note that by definition, if two sets are identical, they are also
2706 subsets (and also supersets) of each other.
2707 · "$norm = $set->Norm();"
2709 Returns the norm (number of bits which are set) of the given vector.
2711 This is equivalent to the number of elements contained in the given
2713 set.
2714 Uses a byte lookup table for calculating the number of set bits per
2716 byte, and thus needs a time for evaluation (and a number of loops)
2717 linearly proportional to the length of the given bit vector (in
2718 bytes).
2719 This should be the fastest algorithm on average.
2721 · "$norm = $set->Norm2();"
2723 Returns the norm (number of bits which are set) of the given vector.
2725 This is equivalent to the number of elements contained in the given
2727 set.
2728 This does the same as the method ""Norm()"" above, only with a dif‐
2730 ferent algorithm:
2731 This method counts the number of set and cleared bits at the same
2733 time and will stop when either of them has been exhausted, thus need‐
2734 ing at most half as many loops per machine word as the total number
2735 of bits in a machine word - in fact it will need a number of loops
2736 equal to the minimum of the number of set bits and the number of
2737 cleared bits.
2738 This might be a faster algorithm than of the method ""Norm()"" above
2740 on some systems, depending on the system's architecture and the com‐
2741 piler and optimisation used, for bit vectors with sparse set bits and
2742 for bit vectors with sparse cleared bits (i.e., predominantly set
2743 bits).
2744 · "$norm = $set->Norm3();"
2746 Returns the norm (number of bits which are set) of the given vector.
2748 This is equivalent to the number of elements contained in the given
2750 set.
2751 This does the same as the two methods ""Norm()"" and ""Norm2()""
2753 above, however with a different algorithm.
2754 In fact this is the implementation of the method ""Norm()"" used in
2756 previous versions of this module.
2757 The method needs a number of loops per machine word equal to the num‐
2759 ber of set bits in that machine word.
2760 Only for bit vectors with sparse set bits will this method be fast;
2762 it will depend on a system's architecture and compiler whether the
2763 method will be faster than any of the two methods above in such
2764 cases.
2765 On average however, this is probably the slowest method of the three.
2767 · "$min = $set->Min();"
2769 Returns the minimum of the given set, i.e., the minimum of all
2771 indices of all set bits in the given bit vector "$set".
2772 If the set is empty (no set bits), plus infinity (represented by the
2774 constant "MAX_LONG" on your system) is returned.
2775 (This constant is usually 2 ^ (n-1) - 1, where ""n"" is the number of
2777 bits of an unsigned long on your machine.)
2778 · "$max = $set->Max();"
2780 Returns the maximum of the given set, i.e., the maximum of all
2782 indices of all set bits in the given bit vector "$set".
2783 If the set is empty (no set bits), minus infinity (represented by the
2785 constant "MIN_LONG" on your system) is returned.
2786 (This constant is usually -(2 ^ (n-1) - 1) or -(2 ^ (n-1)), where
2788 ""n"" is the number of bits of an unsigned long on your machine.)
2789 · "$m3->Multiplication($r3,$c3,$m1,$r1,$c1,$m2,$r2,$c2);"
2791 This method multiplies two boolean matrices (stored as bit vectors)
2793 "$m1" and "$m2" and stores the result in matrix "$m3".
2794 The method uses the binary "xor" operation (""^"") as the boolean
2796 addition operator (""+"").
2797 An exception is raised if the product of the number of rows and col‐
2799 umns of any of the three matrices differs from the actual size of
2800 their underlying bit vector.
2801 An exception is also raised if the numbers of rows and columns of the
2803 three matrices do not harmonize in the required manner:
2804 rows3 == rows1
2806 cols3 == cols2
2807 cols1 == rows2
2808 This method is used by the module "Math::MatrixBool".
2810 See Math::MatrixBool(3) for details.
2812 · "$m3->Product($r3,$c3,$m1,$r1,$c1,$m2,$r2,$c2);"
2814 This method multiplies two boolean matrices (stored as bit vectors)
2816 "$m1" and "$m2" and stores the result in matrix "$m3".
2817 This special method uses the binary "or" operation (""⎪"") as the
2819 boolean addition operator (""+"").
2820 An exception is raised if the product of the number of rows and col‐
2822 umns of any of the three matrices differs from the actual size of
2823 their underlying bit vector.
2824 An exception is also raised if the numbers of rows and columns of the
2826 three matrices do not harmonize in the required manner:
2827 rows3 == rows1
2829 cols3 == cols2
2830 cols1 == rows2
2831 This method is used by the module "Math::MatrixBool".
2833 See Math::MatrixBool(3) for details.
2835 · "$matrix->Closure($rows,$cols);"
2837 This method calculates the reflexive transitive closure of the given
2839 boolean matrix (stored as a bit vector) using Kleene's algoritm.
2840 (See Math::Kleene(3) for a brief introduction into the theory behind
2842 Kleene's algorithm.)
2843 The reflexive transitive closure answers the question whether a path
2845 exists between any two vertices of a graph whose edges are given as a
2846 matrix:
2847 If a (directed) edge exists going from vertex "i" to vertex "j", then
2849 the element in the matrix with coordinates (i,j) is set to "1" (oth‐
2850 erwise it remains set to "0").
2851 If the edges are undirected, the resulting matrix is symmetric, i.e.,
2853 elements (i,j) and (j,i) always contain the same value.
2854 The matrix representing the edges of the graph only answers the ques‐
2856 tion whether an EDGE exists between any two vertices of the graph or
2857 not, whereas the reflexive transitive closure answers the question
2858 whether a PATH (a series of adjacent edges) exists between any two
2859 vertices of the graph!
2860 Note that the contents of the given matrix are modified by this
2862 method, so make a copy of the initial matrix in time if you are going
2863 to need it again later.
2864 An exception is raised if the given matrix is not quadratic, i.e., if
2866 the number of rows and columns of the given matrix is not identical.
2867 An exception is also raised if the product of the number of rows and
2869 columns of the given matrix differs from the actual size of its
2870 underlying bit vector.
2871 This method is used by the module "Math::MatrixBool".
2873 See Math::MatrixBool(3) for details.
2875 · "$matrix2->Transpose($rows2,$cols2,$matrix1,$rows1,$cols1);"
2877 This method calculates the transpose of a boolean matrix "$matrix1"
2879 (stored as a bit vector) and stores the result in matrix "$matrix2".
2880 The transpose of a boolean matrix, representing the edges of a graph,
2882 can be used for finding the strongly connected components of that
2883 graph.
2884 An exception is raised if the product of the number of rows and col‐
2886 umns of any of the two matrices differs from the actual size of its
2887 underlying bit vector.
2888 An exception is also raised if the following conditions are not met:
2890 rows2 == cols1
2892 cols2 == rows1
2893 Note that in-place processing ("$matrix1" and "$matrix2" are identi‐
2895 cal) is only possible if the matrix is quadratic. Otherwise, a fatal
2896 "matrix is not quadratic" error will occur.
2897 This method is used by the module "Math::MatrixBool".
2899 See Math::MatrixBool(3) for details.
2901
2903 Bit::Vector::Overload(3), Bit::Vector::String(3).
2904 Set::IntRange(3), Math::MatrixBool(3), Math::MatrixReal(3),
2906 DFA::Kleene(3), Math::Kleene(3), Graph::Kruskal(3).
2907
2909 This man page documents "Bit::Vector" version 6.4.
2910
2912 Steffen Beyer
2913 mailto:sb@engelschall.com
2914 http://www.engelschall.com/u/sb/download/
2915
2917 Copyright (c) 1995 - 2004 by Steffen Beyer. All rights reserved.
2918
2920 This package is free software; you can redistribute it and/or modify it
2921 under the same terms as Perl itself, i.e., under the terms of the
2922 "Artistic License" or the "GNU General Public License".
2923 The C library at the core of this Perl module can additionally be
2925 redistributed and/or modified under the terms of the "GNU Library Gen‐
2926 eral Public License".
2927 Please refer to the files "Artistic.txt", "GNU_GPL.txt" and
2929 "GNU_LGPL.txt" in this distribution for details!
2930
2932 This package is distributed in the hope that it will be useful, but
2933 WITHOUT ANY WARRANTY; without even the implied warranty of MER‐
2934 CHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
2935 See the "GNU General Public License" for more details.
2937perl v5.8.8 2004-10-03 Vector(3)