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).
12 MORE STRING IMPORT/EXPORT
14 See Bit::Vector::String(3).
15 CLASS METHODS
17 Version
18 $version = Bit::Vector->Version();
19 Word_Bits
21 $bits = Bit::Vector->Word_Bits(); # bits in a machine word
22 Long_Bits
24 $bits = Bit::Vector->Long_Bits(); # bits in an unsigned long
25 new
27 $vector = Bit::Vector->new($bits); # bit vector constructor
28 @veclist = Bit::Vector->new($bits,$count);
30 new_Hex
32 $vector = Bit::Vector->new_Hex($bits,$string);
33 new_Bin
35 $vector = Bit::Vector->new_Bin($bits,$string);
36 new_Dec
38 $vector = Bit::Vector->new_Dec($bits,$string);
39 new_Enum
41 $vector = Bit::Vector->new_Enum($bits,$string);
42 Concat_List
44 $vector = Bit::Vector->Concat_List(@vectors);
45 OBJECT METHODS
47 new
48 $vec2 = $vec1->new($bits); # alternative call of constructor
49 @veclist = $vec->new($bits,$count);
51 Shadow
53 $vec2 = $vec1->Shadow(); # new vector, same size but empty
54 Clone
56 $vec2 = $vec1->Clone(); # new vector, exact duplicate
57 Concat
59 $vector = $vec1->Concat($vec2);
60 Concat_List
62 $vector = $vec1->Concat_List($vec2,$vec3,...);
63 Size
65 $bits = $vector->Size();
66 Resize
68 $vector->Resize($bits);
69 $vector->Resize($vector->Size()+5);
70 $vector->Resize($vector->Size()-5);
71 Copy
73 $vec2->Copy($vec1);
74 Empty
76 $vector->Empty();
77 Fill
79 $vector->Fill();
80 Flip
82 $vector->Flip();
83 Primes
85 $vector->Primes(); # Sieve of Erathostenes
86 Reverse
88 $vec2->Reverse($vec1);
89 Interval_Empty
91 $vector->Interval_Empty($min,$max);
92 Interval_Fill
94 $vector->Interval_Fill($min,$max);
95 Interval_Flip
97 $vector->Interval_Flip($min,$max);
98 Interval_Reverse
100 $vector->Interval_Reverse($min,$max);
101 Interval_Scan_inc
103 if (($min,$max) = $vector->Interval_Scan_inc($start))
104 Interval_Scan_dec
106 if (($min,$max) = $vector->Interval_Scan_dec($start))
107 Interval_Copy
109 $vec2->Interval_Copy($vec1,$offset2,$offset1,$length);
110 Interval_Substitute
112 $vec2->Interval_Substitute($vec1,$off2,$len2,$off1,$len1);
113 is_empty
115 if ($vector->is_empty())
116 is_full
118 if ($vector->is_full())
119 equal
121 if ($vec1->equal($vec2))
122 Lexicompare (unsigned)
124 if ($vec1->Lexicompare($vec2) == 0)
125 if ($vec1->Lexicompare($vec2) != 0)
126 if ($vec1->Lexicompare($vec2) < 0)
127 if ($vec1->Lexicompare($vec2) <= 0)
128 if ($vec1->Lexicompare($vec2) > 0)
129 if ($vec1->Lexicompare($vec2) >= 0)
130 Compare (signed)
132 if ($vec1->Compare($vec2) == 0)
133 if ($vec1->Compare($vec2) != 0)
134 if ($vec1->Compare($vec2) < 0)
135 if ($vec1->Compare($vec2) <= 0)
136 if ($vec1->Compare($vec2) > 0)
137 if ($vec1->Compare($vec2) >= 0)
138 to_Hex
140 $string = $vector->to_Hex();
141 from_Hex
143 $vector->from_Hex($string);
144 to_Bin
146 $string = $vector->to_Bin();
147 from_Bin
149 $vector->from_Bin($string);
150 to_Dec
152 $string = $vector->to_Dec();
153 from_Dec
155 $vector->from_Dec($string);
156 to_Enum
158 $string = $vector->to_Enum(); # e.g. "2,3,5-7,11,13-19"
159 from_Enum
161 $vector->from_Enum($string);
162 Bit_Off
164 $vector->Bit_Off($index);
165 Bit_On
167 $vector->Bit_On($index);
168 bit_flip
170 $bit = $vector->bit_flip($index);
171 bit_test
173 contains
174 $bit = $vector->bit_test($index);
175 $bit = $vector->contains($index);
176 if ($vector->bit_test($index))
177 if ($vector->contains($index))
178 Bit_Copy
180 $vector->Bit_Copy($index,$bit);
181 LSB (least significant bit)
183 $vector->LSB($bit);
184 MSB (most significant bit)
186 $vector->MSB($bit);
187 lsb (least significant bit)
189 $bit = $vector->lsb();
190 msb (most significant bit)
192 $bit = $vector->msb();
193 rotate_left
195 $carry = $vector->rotate_left();
196 rotate_right
198 $carry = $vector->rotate_right();
199 shift_left
201 $carry = $vector->shift_left($carry);
202 shift_right
204 $carry = $vector->shift_right($carry);
205 Move_Left
207 $vector->Move_Left($bits); # shift left "$bits" positions
208 Move_Right
210 $vector->Move_Right($bits); # shift right "$bits" positions
211 Insert
213 $vector->Insert($offset,$bits);
214 Delete
216 $vector->Delete($offset,$bits);
217 increment
219 $carry = $vector->increment();
220 decrement
222 $carry = $vector->decrement();
223 inc
225 $overflow = $vec2->inc($vec1);
226 dec
228 $overflow = $vec2->dec($vec1);
229 add
231 $carry = $vec3->add($vec1,$vec2,$carry);
232 ($carry,$overflow) = $vec3->add($vec1,$vec2,$carry);
233 subtract
235 $carry = $vec3->subtract($vec1,$vec2,$carry);
236 ($carry,$overflow) = $vec3->subtract($vec1,$vec2,$carry);
237 Neg
239 Negate
240 $vec2->Neg($vec1);
241 $vec2->Negate($vec1);
242 Abs
244 Absolute
245 $vec2->Abs($vec1);
246 $vec2->Absolute($vec1);
247 Sign
249 if ($vector->Sign() == 0)
250 if ($vector->Sign() != 0)
251 if ($vector->Sign() < 0)
252 if ($vector->Sign() <= 0)
253 if ($vector->Sign() > 0)
254 if ($vector->Sign() >= 0)
255 Multiply
257 $vec3->Multiply($vec1,$vec2);
258 Divide
260 $quot->Divide($vec1,$vec2,$rest);
261 GCD (Greatest Common Divisor)
263 $vecgcd->GCD($veca,$vecb);
264 $vecgcd->GCD($vecx,$vecy,$veca,$vecb);
265 Power
267 $vec3->Power($vec1,$vec2);
268 Block_Store
270 $vector->Block_Store($buffer);
271 Block_Read
273 $buffer = $vector->Block_Read();
274 Word_Size
276 $size = $vector->Word_Size(); # number of words in "$vector"
277 Word_Store
279 $vector->Word_Store($offset,$word);
280 Word_Read
282 $word = $vector->Word_Read($offset);
283 Word_List_Store
285 $vector->Word_List_Store(@words);
286 Word_List_Read
288 @words = $vector->Word_List_Read();
289 Word_Insert
291 $vector->Word_Insert($offset,$count);
292 Word_Delete
294 $vector->Word_Delete($offset,$count);
295 Chunk_Store
297 $vector->Chunk_Store($chunksize,$offset,$chunk);
298 Chunk_Read
300 $chunk = $vector->Chunk_Read($chunksize,$offset);
301 Chunk_List_Store
303 $vector->Chunk_List_Store($chunksize,@chunks);
304 Chunk_List_Read
306 @chunks = $vector->Chunk_List_Read($chunksize);
307 Index_List_Remove
309 $vector->Index_List_Remove(@indices);
310 Index_List_Store
312 $vector->Index_List_Store(@indices);
313 Index_List_Read
315 @indices = $vector->Index_List_Read();
316 Or
318 Union
319 $vec3->Or($vec1,$vec2);
320 $set3->Union($set1,$set2);
321 And
323 Intersection
324 $vec3->And($vec1,$vec2);
325 $set3->Intersection($set1,$set2);
326 AndNot
328 Difference
329 $vec3->AndNot($vec1,$vec2);
330 $set3->Difference($set1,$set2);
331 Xor
333 ExclusiveOr
334 $vec3->Xor($vec1,$vec2);
335 $set3->ExclusiveOr($set1,$set2);
336 Not
338 Complement
339 $vec2->Not($vec1);
340 $set2->Complement($set1);
341 subset
343 if ($set1->subset($set2)) # true if $set1 is subset of $set2
344 Norm
346 $norm = $set->Norm();
347 $norm = $set->Norm2();
348 $norm = $set->Norm3();
349 Min
351 $min = $set->Min();
352 Max
354 $max = $set->Max();
355 Multiplication
357 $matrix3->Multiplication($rows3,$cols3,
358 $matrix1,$rows1,$cols1,
359 $matrix2,$rows2,$cols2);
360 Product
362 $matrix3->Product($rows3,$cols3,
363 $matrix1,$rows1,$cols1,
364 $matrix2,$rows2,$cols2);
365 Closure
367 $matrix->Closure($rows,$cols);
368 Transpose
370 $matrix2->Transpose($rows2,$cols2,$matrix1,$rows1,$cols1);
371
373 • Method naming conventions
374 Method names completely in lower case indicate a boolean return
376 value.
377 (Except for the bit vector constructor method "new()", of course.)
379 • Boolean values
381 Boolean values in this module are always a numeric zero ("0") for
383 "false" and a numeric one ("1") for "true".
384 • Negative numbers
386 All numeric input parameters passed to any of the methods in this
388 module are regarded as being UNSIGNED (as opposed to the contents of
389 the bit vectors themselves, which are usually considered to be
390 SIGNED).
391 As a consequence, whenever you pass a negative number as an argument
393 to some method of this module, it will be treated as a (usually very
394 large) positive number due to its internal two's complement binary
395 representation, usually resulting in an "index out of range" error
396 message and program abortion.
397 • Bit order
399 Note that bit vectors are stored least order bit and least order word
401 first internally.
402 I.e., bit #0 of any given bit vector corresponds to bit #0 of word #0
404 in the array of machine words representing the bit vector.
405 (Where word #0 comes first in memory, i.e., it is stored at the least
407 memory address in the allocated block of memory holding the given bit
408 vector.)
409 Note however that machine words can be stored least order byte first
411 or last, depending on your system's implementation.
412 When you are exporting or importing a whole bit vector at once using
414 the methods "Block_Read()" and "Block_Store()" (the only time in this
415 module where this could make any difference), however, a conversion
416 to and from "least order byte first" order is automatically supplied.
417 In other words, what "Block_Read()" provides and what "Block_Store()"
419 expects is always in "least order byte first" order, regardless of
420 the order in which words are stored internally on your machine.
421 This is to make sure that what you export on one machine using
423 "Block_Read()" can always be read in correctly with "Block_Store()"
424 on a different machine.
425 Note further that whenever bit vectors are converted to and from
427 (binary or hexadecimal) strings, the RIGHTMOST bit is always the
428 LEAST SIGNIFICANT one, and the LEFTMOST bit is always the MOST
429 SIGNIFICANT bit.
430 This is because in our western culture, numbers are always
432 represented in this way (least significant to most significant digits
433 go from right to left).
434 Of course this requires an internal reversion of order, which the
436 corresponding conversion methods perform automatically (without any
437 additional overhead, it's just a matter of starting the internal loop
438 at the bottom or the top end).
439 • "Word" related methods
441 Note that all methods whose names begin with ""Word_"" are MACHINE-
443 DEPENDENT!
444 They depend on the size (number of bits) of an "unsigned int" (C
446 type) on your machine.
447 Therefore, you should only use these methods if you are ABSOLUTELY
449 CERTAIN that portability of your code is not an issue!
450 Note that you can use arbitrarily large chunks (i.e., fragments of
452 bit vectors) of up to 32 bits IN A PORTABLE WAY using the methods
453 whose names begin with ""Chunk_"".
454 • Chunk sizes
456 Note that legal chunk sizes for all methods whose names begin with
458 ""Chunk_"" range from "1" to ""Bit::Vector->Long_Bits();"" bits ("0"
459 is NOT allowed!).
460 In order to make your programs portable, however, you shouldn't use
462 chunk sizes larger than 32 bits, since this is the minimum size of an
463 "unsigned long" (C type) on all systems, as prescribed by ANSI C.
464 • Matching sizes
466 In general, for methods involving several bit vectors at the same
468 time, all bit vector arguments must have identical sizes (number of
469 bits), or a fatal "size mismatch" error will occur.
470 Exceptions from this rule are the methods "Concat()",
472 "Concat_List()", "Copy()", "Interval_Copy()" and
473 "Interval_Substitute()", where no conditions at all are imposed on
474 the size of their bit vector arguments.
475 In method "Multiply()", all three bit vector arguments must in
477 principle obey the rule of matching sizes, but the bit vector in
478 which the result of the multiplication is to be stored may be larger
479 than the two bit vector arguments containing the factors for the
480 multiplication.
481 In method "Power()", the bit vector for the result must be the same
483 size or greater than the base of the exponentiation term. The
484 exponent can be any size.
485 • Index ranges
487 All indices for any given bits must lie between "0" and
489 ""$vector->Size()-1"", or a fatal "index out of range" error will
490 occur.
491 • Object persistence
493 Since version 6.5, "Bit::Vector" objects can be serialized and de-
495 serialized automatically with "Storable", out-of-the-box, without
496 requiring any further user action for this to work.
497 This is also true for nested data structures (since version 6.8).
499 See the Storable(3) documentation for more details.
501
503 OVERLOADED OPERATORS
504 See Bit::Vector::Overload(3).
505 MORE STRING IMPORT/EXPORT
507 See Bit::Vector::String(3).
508 CLASS METHODS
510 • "$version = Bit::Vector->Version();"
511 Returns the current version number of this module.
513 • "$bits = Bit::Vector->Word_Bits();"
515 Returns the number of bits of an "unsigned int" (C type) on your
517 machine.
518 (An "unsigned int" is also called a "machine word", hence the name of
520 this method.)
521 • "$bits = Bit::Vector->Long_Bits();"
523 Returns the number of bits of an "unsigned long" (C type) on your
525 machine.
526 • "$vector = Bit::Vector->new($bits);"
528 This is the bit vector constructor method.
530 Call this method to create a new bit vector containing "$bits" bits
532 (with indices ranging from "0" to ""$bits-1"").
533 Note that - in contrast to previous versions - bit vectors of length
535 zero (i.e., with "$bits = 0") are permitted now.
536 The method returns a reference to the newly created bit vector.
538 A new bit vector is always initialized so that all bits are cleared
540 (turned off).
541 An exception will be raised if the method is unable to allocate the
543 necessary memory.
544 Note that if you specify a negative number for "$bits" it will be
546 interpreted as a large positive number due to its internal two's
547 complement binary representation.
548 In such a case, the bit vector constructor method will obediently
550 attempt to create a bit vector of that size, probably resulting in an
551 exception, as explained above.
552 • "@veclist = Bit::Vector->new($bits,$count);"
554 You can also create more than one bit vector at a time if you specify
556 the optional second parameter "$count".
557 The method returns a list of "$count" bit vectors which all have the
559 same number of bits "$bits" (and which are all initialized, i.e., all
560 bits are cleared).
561 If "$count" is zero, an empty list is returned.
563 If "$bits" is zero, a list of null-sized bit vectors is returned.
565 Note again that if you specify a negative number for "$count" it will
567 be interpreted as a large positive number due to its internal two's
568 complement binary representation.
569 In such a case, the bit vector constructor method will obediently
571 attempt to create that many bit vectors, probably resulting in an
572 exception ("out of memory").
573 • "$vector = Bit::Vector->new_Hex($bits,$string);"
575 This method is an alternative constructor which allows you to create
577 a new bit vector object (with "$bits" bits) and to initialize it all
578 in one go.
579 The method internally first calls the bit vector constructor method
581 "new()" and then passes the given string to the method "from_Hex()".
582 However, this method is more efficient than performing these two
584 steps separately: First because in this method, the memory area
585 occupied by the new bit vector is not initialized to zeros (which is
586 pointless in this case), and second because it saves you from the
587 associated overhead of one additional method invocation.
588 An exception will be raised if the necessary memory cannot be
590 allocated (see the description of the method "new()" immediately
591 above for possible causes) or if the given string cannot be converted
592 successfully (see the description of the method "from_Hex()" further
593 below for details).
594 In the latter case, the memory occupied by the new bit vector is
596 released first (i.e., "free"d) before the exception is actually
597 raised.
598 • "$vector = Bit::Vector->new_Bin($bits,$string);"
600 This method is an alternative constructor which allows you to create
602 a new bit vector object (with "$bits" bits) and to initialize it all
603 in one go.
604 The method internally first calls the bit vector constructor method
606 "new()" and then passes the given string to the method "from_Bin()".
607 However, this method is more efficient than performing these two
609 steps separately: First because in this method, the memory area
610 occupied 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
615 allocated (see the description of the method "new()" above for
616 possible causes) or if the given string cannot be converted
617 successfully (see the description of the method "from_Bin()" further
618 below for 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 "from_Dec()".
632 However, this method is more efficient than performing these two
634 steps separately: First because in this method, "new()" does not
635 initialize the memory area occupied by the new bit vector with zeros
636 (which is pointless in this case, because "from_Dec()" will do it
637 anyway), and second because it saves you from the associated overhead
638 of one additional method invocation.
639 An exception will be raised if the necessary memory cannot be
641 allocated (see the description of the method "new()" above for
642 possible causes) or if the given string cannot be converted
643 successfully (see the description of the method "from_Dec()" further
644 below for details).
645 In the latter case, the memory occupied by the new bit vector is
647 released first (i.e., "free"d) before the exception is actually
648 raised.
649 • "$vector = Bit::Vector->new_Enum($bits,$string);"
651 This method is an alternative constructor which allows you to create
653 a new bit vector object (with "$bits" bits) and to initialize it all
654 in one go.
655 The method internally first calls the bit vector constructor method
657 "new()" and then passes the given string to the method "from_Enum()".
658 However, this method is more efficient than performing these two
660 steps separately: First because in this method, "new()" does not
661 initialize the memory area occupied by the new bit vector with zeros
662 (which is pointless in this case, because "from_Enum()" will do it
663 anyway), and second because it saves you from the associated overhead
664 of one additional method invocation.
665 An exception will be raised if the necessary memory cannot be
667 allocated (see the description of the method "new()" above for
668 possible causes) or if the given string cannot be converted
669 successfully (see the description of the method "from_Enum()" further
670 below for details).
671 In the latter case, the memory occupied by the new bit vector is
673 released first (i.e., "free"d) before the exception is actually
674 raised.
675 • "$vector = Bit::Vector->Concat_List(@vectors);"
677 This method creates a new vector containing all bit vectors from the
679 argument list in concatenated form.
680 The argument list may contain any number of arguments (including
682 zero); the only condition is that all arguments must be bit vectors.
683 There is no condition concerning the length (in number of bits) of
685 these arguments.
686 The vectors from the argument list are not changed in any way.
688 If the argument list is empty or if all arguments have length zero,
690 the resulting bit vector will also have length zero.
691 Note that the RIGHTMOST bit vector from the argument list will become
693 the LEAST significant part of the resulting bit vector, and the
694 LEFTMOST bit vector from the argument list will become the MOST
695 significant part of the resulting bit vector.
696 OBJECT METHODS
698 • "$vec2 = $vec1->new($bits);"
699 "@veclist = $vec->new($bits);"
701 This is an alternative way of calling the bit vector constructor
703 method.
704 Vector "$vec1" (or "$vec") is not affected by this, it just serves as
706 an anchor for the method invocation mechanism.
707 In fact ALL class methods in this module can be called this way, even
709 though this is probably considered to be "politically incorrect" by
710 OO ("object-orientation") aficionados. ;-)
711 So even if you are too lazy to type ""Bit::Vector->"" instead of
713 ""$vec1->"" (and even though laziness is - allegedly - a programmer's
714 virtue ":-)"), maybe it is better not to use this feature if you
715 don't want to get booed at. ;-)
716 • "$vec2 = $vec1->Shadow();"
718 Creates a NEW bit vector "$vec2" of the SAME SIZE as "$vec1" but
720 which is EMPTY.
721 Just like a shadow that has the same shape as the object it
723 originates from, but is flat and has no volume, i.e., contains
724 nothing.
725 • "$vec2 = $vec1->Clone();"
727 Creates a NEW bit vector "$vec2" of the SAME SIZE as "$vec1" which is
729 an EXACT COPY of "$vec1".
730 • "$vector = $vec1->Concat($vec2);"
732 This method returns a new bit vector object which is the result of
734 the concatenation of the contents of "$vec1" and "$vec2".
735 Note that the contents of "$vec1" become the MOST significant part of
737 the resulting bit vector, and "$vec2" the LEAST significant part.
738 If both bit vector arguments have length zero, the resulting bit
740 vector will also have length zero.
741 • "$vector = $vec1->Concat_List($vec2,$vec3,...);"
743 This is an alternative way of calling this (class) method as an
745 object method.
746 The method returns a new bit vector object which is the result of the
748 concatenation of the contents of "$vec1 . $vec2 . $vec3 . ..."
749 See the section "class methods" above for a detailed description of
751 this method.
752 Note that the argument list may be empty and that all arguments must
754 be bit vectors if it isn't.
755 • "$bits = $vector->Size();"
757 Returns the size (number of bits) the given vector was created with
759 (or "Resize()"d to).
760 • "$vector->Resize($bits);"
762 Changes the size of the given vector to the specified number of bits.
764 This method allows you to change the size of an existing bit vector,
766 preserving as many bits from the old vector as will fit into the new
767 one (i.e., all bits with indices smaller than the minimum of the
768 sizes of both vectors, old and new).
769 If the number of machine words needed to store the new vector is
771 smaller than or equal to the number of words needed to store the old
772 vector, the memory allocated for the old vector is reused for the new
773 one, and only the relevant book-keeping information is adjusted
774 accordingly.
775 This means that even if the number of bits increases, new memory is
777 not necessarily being allocated (i.e., if the old and the new number
778 of bits fit into the same number of machine words).
779 If the number of machine words needed to store the new vector is
781 greater than the number of words needed to store the old vector, new
782 memory is allocated for the new vector, the old vector is copied to
783 the new one, the remaining bits in the new vector are cleared (turned
784 off) and the old vector is deleted, i.e., the memory that was
785 allocated for it is released.
786 (An exception will be raised if the method is unable to allocate the
788 necessary memory for the new vector.)
789 As a consequence, if you decrease the size of a given vector so that
791 it will use fewer machine words, and increase it again later so that
792 it will use more words than immediately before but still less than
793 the original vector, new memory will be allocated anyway because the
794 information about the size of the original vector is lost whenever
795 you resize it.
796 Note also that if you specify a negative number for "$bits" it will
798 be interpreted as a large positive number due to its internal two's
799 complement binary representation.
800 In such a case, "Resize()" will obediently attempt to create a bit
802 vector of that size, probably resulting in an exception, as explained
803 above.
804 Finally, note that - in contrast to previous versions - resizing a
806 bit vector to a size of zero bits (length zero) is now permitted.
807 • "$vec2->Copy($vec1);"
809 Copies the contents of bit vector "$vec1" to bit vector "$vec2".
811 The previous contents of bit vector "$vec2" get overwritten, i.e.,
813 are lost.
814 Both vectors must exist beforehand, i.e., this method does not CREATE
816 any new bit vector object.
817 The two vectors may be of any size.
819 If the source bit vector is larger than the target, this method will
821 copy as much of the least significant bits of the source vector as
822 will fit into the target vector, thereby discarding any extraneous
823 most significant bits.
824 BEWARE that this causes a brutal cutoff in the middle of your data,
826 and it will also leave you with an almost unpredictable sign if
827 subsequently the number in the target vector is going to be
828 interpreted as a number! (You have been warned!)
829 If the target bit vector is larger than the source, this method fills
831 up the remaining most significant bits in the target bit vector with
832 either 0's or 1's, depending on the sign (= the most significant bit)
833 of the source bit vector. This is also known as "sign extension".
834 This makes it possible to copy numbers from a smaller bit vector into
836 a larger one while preserving the number's absolute value as well as
837 its sign (due to the two's complement binary representation of
838 numbers).
839 • "$vector->Empty();"
841 Clears all bits in the given vector.
843 • "$vector->Fill();"
845 Sets all bits in the given vector.
847 • "$vector->Flip();"
849 Flips (i.e., complements) all bits in the given vector.
851 • "$vector->Primes();"
853 Clears the given bit vector and sets all bits whose indices are prime
855 numbers.
856 This method uses the algorithm known as the "Sieve of Erathostenes"
858 internally.
859 • "$vec2->Reverse($vec1);"
861 This method copies the given vector "$vec1" to the vector "$vec2",
863 thereby reversing the order of all bits.
864 I.e., the least significant bit of "$vec1" becomes the most
866 significant bit of "$vec2", whereas the most significant bit of
867 "$vec1" becomes the least significant bit of "$vec2", and so forth
868 for all bits in between.
869 Note that in-place processing is also possible, i.e., "$vec1" and
871 "$vec2" may be identical.
872 (Internally, this is the same as
874 "$vec1->Interval_Reverse(0,$vec1->Size()-1);".)
875 • "$vector->Interval_Empty($min,$max);"
877 Clears all bits in the interval "[$min..$max]" (including both
879 limits) in the given vector.
880 "$min" and "$max" may have the same value; this is the same as
882 clearing a single bit with "Bit_Off()" (but less efficient).
883 Note that "$vector->Interval_Empty(0,$vector->Size()-1);" is the same
885 as "$vector->Empty();" (but less efficient).
886 • "$vector->Interval_Fill($min,$max);"
888 Sets all bits in the interval "[$min..$max]" (including both limits)
890 in the given vector.
891 "$min" and "$max" may have the same value; this is the same as
893 setting a single bit with "Bit_On()" (but less efficient).
894 Note that "$vector->Interval_Fill(0,$vector->Size()-1);" is the same
896 as "$vector->Fill();" (but less efficient).
897 • "$vector->Interval_Flip($min,$max);"
899 Flips (i.e., complements) all bits in the interval "[$min..$max]"
901 (including both limits) in the given vector.
902 "$min" and "$max" may have the same value; this is the same as
904 flipping a single bit with "bit_flip()" (but less efficient).
905 Note that "$vector->Interval_Flip(0,$vector->Size()-1);" is the same
907 as "$vector->Flip();" and "$vector->Complement($vector);" (but less
908 efficient).
909 • "$vector->Interval_Reverse($min,$max);"
911 Reverses the order of all bits in the interval "[$min..$max]"
913 (including both limits) in the given vector.
914 I.e., bits "$min" and "$max" swap places, and so forth for all bits
916 in between.
917 "$min" and "$max" may have the same value; this has no effect
919 whatsoever, though.
920 • "if (($min,$max) = $vector->Interval_Scan_inc($start))"
922 Returns the minimum and maximum indices of the next contiguous block
924 of set bits (i.e., bits in the "on" state).
925 The search starts at index "$start" (i.e., "$min" >= "$start") and
927 proceeds upwards (i.e., "$max" >= "$min"), thus repeatedly increments
928 the search pointer "$start" (internally).
929 Note though that the contents of the variable (or scalar literal
931 value) "$start" is NOT altered. I.e., you have to set it to the
932 desired value yourself prior to each call to "Interval_Scan_inc()"
933 (see also the example given below).
934 Actually, the bit vector is not searched bit by bit, but one machine
936 word at a time, in order to speed up execution (which means that this
937 method is quite efficient).
938 An empty list is returned if no such block can be found.
940 Note that a single set bit (surrounded by cleared bits) is a valid
942 block by this definition. In that case the return values for "$min"
943 and "$max" are the same.
944 Typical use:
946 $start = 0;
948 while (($start < $vector->Size()) &&
949 (($min,$max) = $vector->Interval_Scan_inc($start)))
950 {
951 $start = $max + 2;
952 # do something with $min and $max
954 }
955 • "if (($min,$max) = $vector->Interval_Scan_dec($start))"
957 Returns the minimum and maximum indices of the next contiguous block
959 of set bits (i.e., bits in the "on" state).
960 The search starts at index "$start" (i.e., "$max" <= "$start") and
962 proceeds downwards (i.e., "$min" <= "$max"), thus repeatedly
963 decrements the search pointer "$start" (internally).
964 Note though that the contents of the variable (or scalar literal
966 value) "$start" is NOT altered. I.e., you have to set it to the
967 desired value yourself prior to each call to "Interval_Scan_dec()"
968 (see also the example given below).
969 Actually, the bit vector is not searched bit by bit, but one machine
971 word at a time, in order to speed up execution (which means that this
972 method is quite efficient).
973 An empty list is returned if no such block can be found.
975 Note that a single set bit (surrounded by cleared bits) is a valid
977 block by this definition. In that case the return values for "$min"
978 and "$max" are the same.
979 Typical use:
981 $start = $vector->Size() - 1;
983 while (($start >= 0) &&
984 (($min,$max) = $vector->Interval_Scan_dec($start)))
985 {
986 $start = $min - 2;
987 # do something with $min and $max
989 }
990 • "$vec2->Interval_Copy($vec1,$offset2,$offset1,$length);"
992 This method allows you to copy a stretch of contiguous bits (starting
994 at any position "$offset1" you choose, with a length of "$length"
995 bits) from a given "source" bit vector "$vec1" to another position
996 "$offset2" in a "target" bit vector "$vec2".
997 Note that the two bit vectors "$vec1" and "$vec2" do NOT need to have
999 the same (matching) size!
1000 Consequently, any of the two terms ""$offset1 + $length"" and
1002 ""$offset2 + $length"" (or both) may exceed the actual length of its
1003 corresponding bit vector (""$vec1->Size()"" and ""$vec2->Size()"",
1004 respectively).
1005 In such a case, the "$length" parameter is automatically reduced
1007 internally so that both terms above are bounded by the number of bits
1008 of their corresponding bit vector.
1009 This may even result in a length of zero, in which case nothing is
1011 copied at all.
1012 (Of course the value of the "$length" parameter, supplied by you in
1014 the initial method call, may also be zero right from the start!)
1015 Note also that "$offset1" and "$offset2" must lie within the range
1017 "0" and, respectively, ""$vec1->Size()-1"" or ""$vec2->Size()-1"", or
1018 a fatal "offset out of range" error will occur.
1019 Note further that "$vec1" and "$vec2" may be identical, i.e., you may
1021 copy a stretch of contiguous bits from one part of a given bit vector
1022 to another part.
1023 The source and the target interval may even overlap, in which case
1025 the copying is automatically performed in ascending or descending
1026 order (depending on the direction of the copy - downwards or upwards
1027 in the bit vector, respectively) to handle this situation correctly,
1028 i.e., so that no bits are being overwritten before they have been
1029 copied themselves.
1030 • "$vec2->Interval_Substitute($vec1,$off2,$len2,$off1,$len1);"
1032 This method is (roughly) the same for bit vectors (i.e., arrays of
1034 booleans) as what the "splice" function in Perl is for lists (i.e.,
1035 arrays of scalars).
1036 (See "splice" in perlfunc for more details about this function.)
1038 The method allows you to substitute a stretch of contiguous bits
1040 (defined by a position (offset) "$off1" and a length of "$len1" bits)
1041 from a given "source" bit vector "$vec1" for a different stretch of
1042 contiguous bits (defined by a position (offset) "$off2" and a length
1043 of "$len2" bits) in another, "target" bit vector "$vec2".
1044 Note that the two bit vectors "$vec1" and "$vec2" do NOT need to have
1046 the same (matching) size!
1047 Note further that "$off1" and "$off2" must lie within the range "0"
1049 and, respectively, ""$vec1->Size()"" or ""$vec2->Size()"", or a fatal
1050 "offset out of range" error will occur.
1051 Alert readers will have noticed that these upper limits are NOT
1053 ""$vec1->Size()-1"" and ""$vec2->Size()-1"", as they would be for any
1054 other method in this module, but that these offsets may actually
1055 point to one position PAST THE END of the corresponding bit vector.
1056 This is necessary in order to make it possible to APPEND a given
1058 stretch of bits to the target bit vector instead of REPLACING
1059 something in it.
1060 For reasons of symmetry and generality, the same applies to the
1062 offset in the source bit vector, even though such an offset (one
1063 position past the end of the bit vector) does not serve any practical
1064 purpose there (but does not cause any harm either).
1065 (Actually this saves you from the need of testing for this special
1067 case, in certain circumstances.)
1068 Note that whenever the term ""$off1 + $len1"" exceeds the size
1070 ""$vec1->Size()"" of bit vector "$vec1" (or if ""$off2 + $len2""
1071 exceeds ""$vec2->Size()""), the corresponding length ("$len1" or
1072 "$len2", respectively) is automatically reduced internally so that
1073 ""$off1 + $len1 <= $vec1->Size()"" (and ""$off2 + $len2 <=
1074 $vec2->Size()"") holds.
1075 (Note that this does NOT alter the intended result, even though this
1077 may seem counter-intuitive at first!)
1078 This may even result in a length ("$len1" or "$len2") of zero.
1080 A length of zero for the interval in the SOURCE bit vector (""$len1
1082 == 0"") means that the indicated stretch of bits in the target bit
1083 vector (starting at position "$off2") is to be replaced by NOTHING,
1084 i.e., is to be DELETED.
1085 A length of zero for the interval in the TARGET bit vector ("$len2 ==
1087 0") means that NOTHING is replaced, and that the stretch of bits from
1088 the source bit vector is simply INSERTED into the target bit vector
1089 at the indicated position ("$off2").
1090 If both length parameters are zero, nothing is done at all.
1092 Note that in contrast to any other method in this module (especially
1094 "Interval_Copy()", "Insert()" and "Delete()"), this method IMPLICITLY
1095 and AUTOMATICALLY adapts the length of the resulting bit vector as
1096 needed, as given by
1097 $size = $vec2->Size(); # before
1099 $size += $len1 - $len2; # after
1100 (The only other method in this module that changes the size of a bit
1102 vector is the method "Resize()".)
1103 In other words, replacing a given interval of bits in the target bit
1105 vector with a longer or shorter stretch of bits from the source bit
1106 vector, or simply inserting (""$len2 == 0"") a stretch of bits into
1107 or deleting (""$len1 == 0"") an interval of bits from the target bit
1108 vector will automatically increase or decrease, respectively, the
1109 size of the target bit vector accordingly.
1110 For the sake of generality, this may even result in a bit vector with
1112 a size of zero (containing no bits at all).
1113 This is also the reason why bit vectors of length zero are permitted
1115 in this module in the first place, starting with version 5.0.
1116 Finally, note that "$vec1" and "$vec2" may be identical, i.e., in-
1118 place processing is possible.
1119 (If you think about that for a while or if you look at the code, you
1121 will see that this is far from trivial!)
1122 • "if ($vector->is_empty())"
1124 Tests whether the given bit vector is empty, i.e., whether ALL of its
1126 bits are cleared (in the "off" state).
1127 In "big integer" arithmetic, this is equivalent to testing whether
1129 the number stored in the bit vector is zero ("0").
1130 Returns "true" ("1") if the bit vector is empty and "false" ("0")
1132 otherwise.
1133 Note that this method also returns "true" ("1") if the given bit
1135 vector has a length of zero, i.e., if it contains no bits at all.
1136 • "if ($vector->is_full())"
1138 Tests whether the given bit vector is full, i.e., whether ALL of its
1140 bits are set (in the "on" state).
1141 In "big integer" arithmetic, this is equivalent to testing whether
1143 the number stored in the bit vector is minus one ("-1").
1144 Returns "true" ("1") if the bit vector is full and "false" ("0")
1146 otherwise.
1147 If the given bit vector has a length of zero (i.e., if it contains no
1149 bits at all), this method returns "false" ("0").
1150 • "if ($vec1->equal($vec2))"
1152 Tests the two given bit vectors for equality.
1154 Returns "true" ("1") if the two bit vectors are exact copies of one
1156 another and "false" ("0") otherwise.
1157 • "$cmp = $vec1->Lexicompare($vec2);"
1159 Compares the two given bit vectors, which are regarded as UNSIGNED
1161 numbers in binary representation.
1162 The method returns "-1" if the first bit vector is smaller than the
1164 second bit vector, "0" if the two bit vectors are exact copies of one
1165 another and "1" if the first bit vector is greater than the second
1166 bit vector.
1167 • "$cmp = $vec1->Compare($vec2);"
1169 Compares the two given bit vectors, which are regarded as SIGNED
1171 numbers in binary representation.
1172 The method returns "-1" if the first bit vector is smaller than the
1174 second bit vector, "0" if the two bit vectors are exact copies of one
1175 another and "1" if the first bit vector is greater than the second
1176 bit vector.
1177 • "$string = $vector->to_Hex();"
1179 Returns a hexadecimal string representing the given bit vector.
1181 Note that this representation is quite compact, in that it only needs
1183 at most twice the number of bytes needed to store the bit vector
1184 itself, internally.
1185 Note also that since a hexadecimal digit is always worth four bits,
1187 the length of the resulting string is always a multiple of four bits,
1188 regardless of the true length (in bits) of the given bit vector.
1189 Finally, note that the LEAST significant hexadecimal digit is located
1191 at the RIGHT end of the resulting string, and the MOST significant
1192 digit at the LEFT end.
1193 • "$vector->from_Hex($string);"
1195 Allows to read in the contents of a bit vector from a hexadecimal
1197 string, such as returned by the method "to_Hex()" (see above).
1198 Remember that the least significant bits are always to the right of a
1200 hexadecimal string, and the most significant bits to the left.
1201 Therefore, the string is actually read in from right to left while
1202 the bit vector is filled accordingly, 4 bits at a time, starting with
1203 the least significant bits and going upward to the most significant
1204 bits.
1205 If the given string contains less hexadecimal digits than are needed
1207 to completely fill the given bit vector, the remaining (most
1208 significant) bits are all cleared.
1209 This also means that, even if the given string does not contain
1211 enough digits to completely fill the given bit vector, the previous
1212 contents of the bit vector are erased completely.
1213 If the given string is longer than it needs to fill the given bit
1215 vector, the superfluous characters are simply ignored.
1216 (In fact they are ignored completely - they are not even checked for
1218 proper syntax. See also below for more about that.)
1219 This behaviour is intentional so that you may read in the string
1221 representing one bit vector into another bit vector of different
1222 size, i.e., as much of it as will fit.
1223 If during the process of reading the given string any character is
1225 encountered which is not a hexadecimal digit, a fatal syntax error
1226 ensues ("input string syntax error").
1227 • "$string = $vector->to_Bin();"
1229 Returns a binary string representing the given bit vector.
1231 Example:
1233 $vector = Bit::Vector->new(8);
1235 $vector->Primes();
1236 $string = $vector->to_Bin();
1237 print "'$string'\n";
1238 This prints:
1240 '10101100'
1242 (Bits #7, #5, #3 and #2 are set.)
1244 Note that the LEAST significant bit is located at the RIGHT end of
1246 the resulting string, and the MOST significant bit at the LEFT end.
1247 • "$vector->from_Bin($string);"
1249 This method allows you to read in the contents of a bit vector from a
1251 binary string, such as returned by the method "to_Bin()" (see above).
1252 Note that this method assumes that the LEAST significant bit is
1254 located at the RIGHT end of the binary string, and the MOST
1255 significant bit at the LEFT end. Therefore, the string is actually
1256 read in from right to left while the bit vector is filled
1257 accordingly, one bit at a time, starting with the least significant
1258 bit and going upward to the most significant bit.
1259 If the given string contains less binary digits ("0" and "1") than
1261 are needed to completely fill the given bit vector, the remaining
1262 (most significant) bits are all cleared.
1263 This also means that, even if the given string does not contain
1265 enough digits to completely fill the given bit vector, the previous
1266 contents of the bit vector are erased completely.
1267 If the given string is longer than it needs to fill the given bit
1269 vector, the superfluous characters are simply ignored.
1270 (In fact they are ignored completely - they are not even checked for
1272 proper syntax. See also below for more about that.)
1273 This behaviour is intentional so that you may read in the string
1275 representing one bit vector into another bit vector of different
1276 size, i.e., as much of it as will fit.
1277 If during the process of reading the given string any character is
1279 encountered which is not either "0" or "1", a fatal syntax error
1280 ensues ("input string syntax error").
1281 • "$string = $vector->to_Dec();"
1283 This method returns a string representing the contents of the given
1285 bit vector converted to decimal (base 10).
1286 Note that this method assumes the given bit vector to be SIGNED (and
1288 to contain a number in two's complement binary representation).
1289 Consequently, whenever the most significant bit of the given bit
1291 vector is set, the number stored in it is regarded as being NEGATIVE.
1292 The resulting string can be fed into "from_Dec()" (see below) in
1294 order to copy the contents of this bit vector to another one (or to
1295 restore the contents of this one). This is not advisable, though,
1296 since this would be very inefficient (there are much more efficient
1297 methods for storing and copying bit vectors in this module).
1298 Note that such conversion from binary to decimal is inherently slow
1300 since the bit vector has to be repeatedly divided by 10 with
1301 remainder until the quotient becomes 0 (each remainder in turn
1302 represents a single decimal digit of the resulting string).
1303 This is also true for the implementation of this method in this
1305 module, even though a considerable effort has been made to speed it
1306 up: instead of repeatedly dividing by 10, the bit vector is
1307 repeatedly divided by the largest power of 10 that will fit into a
1308 machine word. The remainder is then repeatedly divided by 10 using
1309 only machine word arithmetics, which is much faster than dividing the
1310 whole bit vector ("divide and rule" principle).
1311 According to my own measurements, this resulted in an 8-fold speed
1313 increase over the straightforward approach.
1314 Still, conversion to decimal should be used only where absolutely
1316 necessary.
1317 Keep the resulting string stored in some variable if you need it
1319 again, instead of converting the bit vector all over again.
1320 Beware that if you set the configuration for overloaded operators to
1322 "output=decimal", this method will be called for every bit vector
1323 enclosed in double quotes!
1324 • "$vector->from_Dec($string);"
1326 This method allows you to convert a given decimal number, which may
1328 be positive or negative, into two's complement binary representation,
1329 which is then stored in the given bit vector.
1330 The decimal number should always be provided as a string, to avoid
1332 possible truncation (due to the limited precision of integers in
1333 Perl) or formatting (due to Perl's use of scientific notation for
1334 large numbers), which would lead to errors.
1335 If the binary representation of the given decimal number is too big
1337 to fit into the given bit vector (if the given bit vector does not
1338 contain enough bits to hold it), a fatal "numeric overflow error"
1339 occurs.
1340 If the input string contains other characters than decimal digits
1342 ("0-9") and an optional leading sign (""+"" or ""-""), a fatal "input
1343 string syntax error" occurs.
1344 Beware that large positive numbers which cause the most significant
1346 bit to be set (e.g. "255" in a bit vector with 8 bits) will be
1347 printed as negative numbers when converted back to decimal using the
1348 method "to_Dec()" (e.g. "-1", in our example), because numbers with
1349 the most significant bit set are considered to be negative in two's
1350 complement binary representation.
1351 Note also that while it is possible to thusly enter negative numbers
1353 as large positive numbers (e.g. "255" for "-1" in a bit vector with 8
1354 bits), the contrary isn't, i.e., you cannot enter "-255" for "+1", in
1355 our example. A fatal "numeric overflow error" will occur if you try
1356 to do so.
1357 If possible program abortion is unwanted or intolerable, use
1359 ""eval"", like this:
1360 eval { $vector->from_Dec("1152921504606846976"); };
1362 if ($@)
1363 {
1364 # an error occurred
1365 }
1366 There are four possible error messages:
1368 if ($@ =~ /item is not a string/)
1370 if ($@ =~ /input string syntax error/)
1372 if ($@ =~ /numeric overflow error/)
1374 if ($@ =~ /unable to allocate memory/)
1376 Note that the conversion from decimal to binary is costly in terms of
1378 processing time, since a lot of multiplications have to be carried
1379 out (in principle, each decimal digit must be multiplied with the
1380 binary representation of the power of 10 corresponding to its
1381 position in the decimal number, i.e., 1, 10, 100, 1000, 10000 and so
1382 on).
1383 This is not as time consuming as the opposite conversion, from binary
1385 to decimal (where successive divisions have to be carried out, which
1386 are even more expensive than multiplications), but still noticeable.
1387 Again (as in the case of "to_Dec()"), the implementation of this
1389 method in this module uses the principle of "divide and rule" in
1390 order to speed up the conversion, i.e., as many decimal digits as
1391 possible are first accumulated (converted) in a machine word and only
1392 then stored in the given bit vector.
1393 Even so, use this method only where absolutely necessary if speed is
1395 an important consideration in your application.
1396 Beware that if you set the configuration for overloaded operators to
1398 "input=decimal", this method will be called for every scalar operand
1399 you use!
1400 • "$string = $vector->to_Enum();"
1402 Converts the given bit vector or set into an enumeration of single
1404 indices and ranges of indices (".newsrc" style), representing the
1405 bits that are set ("1") in the bit vector.
1406 Example:
1408 $vector = Bit::Vector->new(20);
1410 $vector->Bit_On(2);
1411 $vector->Bit_On(3);
1412 $vector->Bit_On(11);
1413 $vector->Interval_Fill(5,7);
1414 $vector->Interval_Fill(13,19);
1415 print "'", $vector->to_Enum(), "'\n";
1416 which prints
1418 '2,3,5-7,11,13-19'
1420 If the given bit vector is empty, the resulting string will also be
1422 empty.
1423 Note, by the way, that the above example can also be written a little
1425 handier, perhaps, as follows:
1426 Bit::Vector->Configuration("out=enum");
1428 $vector = Bit::Vector->new(20);
1429 $vector->Index_List_Store(2,3,5,6,7,11,13,14,15,16,17,18,19);
1430 print "'$vector'\n";
1431 • "$vector->from_Enum($string);"
1433 This method first empties the given bit vector and then tries to set
1435 the bits and ranges of bits specified in the given string.
1436 The string "$string" must only contain unsigned integers or ranges of
1438 integers (two unsigned integers separated by a dash "-"), separated
1439 by commas (",").
1440 All other characters are disallowed (including white space!) and
1442 will lead to a fatal "input string syntax error".
1443 In each range, the first integer (the lower limit of the range) must
1445 always be less than or equal to the second integer (the upper limit),
1446 or a fatal "minimum > maximum index" error occurs.
1447 All integers must lie in the permitted range for the given bit
1449 vector, i.e., they must lie between "0" and ""$vector->Size()-1"".
1450 If this condition is not met, a fatal "index out of range" error
1452 occurs.
1453 If possible program abortion is unwanted or intolerable, use
1455 ""eval"", like this:
1456 eval { $vector->from_Enum("2,3,5-7,11,13-19"); };
1458 if ($@)
1459 {
1460 # an error occurred
1461 }
1462 There are four possible error messages:
1464 if ($@ =~ /item is not a string/)
1466 if ($@ =~ /input string syntax error/)
1468 if ($@ =~ /index out of range/)
1470 if ($@ =~ /minimum > maximum index/)
1472 Note that the order of the indices and ranges is irrelevant, i.e.,
1474 eval { $vector->from_Enum("11,5-7,3,13-19,2"); };
1476 results in the same vector as in the example above.
1478 Ranges and indices may also overlap.
1480 This is because each (single) index in the string is passed to the
1482 method "Bit_On()", internally, and each range to the method
1483 "Interval_Fill()".
1484 This means that the resulting bit vector is just the union of all the
1486 indices and ranges specified in the given string.
1487 • "$vector->Bit_Off($index);"
1489 Clears the bit with index "$index" in the given vector.
1491 • "$vector->Bit_On($index);"
1493 Sets the bit with index "$index" in the given vector.
1495 • "$vector->bit_flip($index)"
1497 Flips (i.e., complements) the bit with index "$index" in the given
1499 vector.
1500 Moreover, this method returns the NEW state of the bit in question,
1502 i.e., it returns "0" if the bit is cleared or "1" if the bit is set
1503 (AFTER flipping it).
1504 • "if ($vector->bit_test($index))"
1506 "if ($vector->contains($index))"
1508 Returns the current state of the bit with index "$index" in the given
1510 vector, i.e., returns "0" if it is cleared (in the "off" state) or
1511 "1" if it is set (in the "on" state).
1512 • "$vector->Bit_Copy($index,$bit);"
1514 Sets the bit with index "$index" in the given vector either to "0" or
1516 "1" depending on the boolean value "$bit".
1517 • "$vector->LSB($bit);"
1519 Allows you to set the least significant bit in the given bit vector
1521 to the value given by the boolean parameter "$bit".
1522 This is a (faster) shortcut for ""$vector->Bit_Copy(0,$bit);"".
1524 • "$vector->MSB($bit);"
1526 Allows you to set the most significant bit in the given bit vector to
1528 the value given by the boolean parameter "$bit".
1529 This is a (faster) shortcut for
1531 ""$vector->Bit_Copy($vector->Size()-1,$bit);"".
1532 • "$bit = $vector->lsb();"
1534 Returns the least significant bit of the given bit vector.
1536 This is a (faster) shortcut for ""$bit = $vector->bit_test(0);"".
1538 • "$bit = $vector->msb();"
1540 Returns the most significant bit of the given bit vector.
1542 This is a (faster) shortcut for ""$bit =
1544 $vector->bit_test($vector->Size()-1);"".
1545 • "$carry_out = $vector->rotate_left();"
1547 carry MSB vector: LSB
1549 out:
1550 +---+ +---+---+---+--- ---+---+---+---+
1551 | | <---+--- | | | | ... | | | | <---+
1552 +---+ | +---+---+---+--- ---+---+---+---+ |
1553 | |
1554 +------------------------------------------------+
1555 The least significant bit (LSB) is the bit with index "0", the most
1557 significant bit (MSB) is the bit with index ""$vector->Size()-1"".
1558 • "$carry_out = $vector->rotate_right();"
1560 MSB vector: LSB carry
1562 out:
1563 +---+---+---+--- ---+---+---+---+ +---+
1564 +---> | | | | ... | | | | ---+---> | |
1565 | +---+---+---+--- ---+---+---+---+ | +---+
1566 | |
1567 +------------------------------------------------+
1568 The least significant bit (LSB) is the bit with index "0", the most
1570 significant bit (MSB) is the bit with index ""$vector->Size()-1"".
1571 • "$carry_out = $vector->shift_left($carry_in);"
1573 carry MSB vector: LSB carry
1575 out: in:
1576 +---+ +---+---+---+--- ---+---+---+---+ +---+
1577 | | <--- | | | | ... | | | | <--- | |
1578 +---+ +---+---+---+--- ---+---+---+---+ +---+
1579 The least significant bit (LSB) is the bit with index "0", the most
1581 significant bit (MSB) is the bit with index ""$vector->Size()-1"".
1582 • "$carry_out = $vector->shift_right($carry_in);"
1584 carry MSB vector: LSB carry
1586 in: out:
1587 +---+ +---+---+---+--- ---+---+---+---+ +---+
1588 | | ---> | | | | ... | | | | ---> | |
1589 +---+ +---+---+---+--- ---+---+---+---+ +---+
1590 The least significant bit (LSB) is the bit with index "0", the most
1592 significant bit (MSB) is the bit with index ""$vector->Size()-1"".
1593 • "$vector->Move_Left($bits);"
1595 Shifts the given bit vector left by "$bits" bits, i.e., inserts
1597 "$bits" new bits at the lower end (least significant bit) of the bit
1598 vector, moving all other bits up by "$bits" places, thereby losing
1599 the "$bits" most significant bits.
1600 The inserted new bits are all cleared (set to the "off" state).
1602 This method does nothing if "$bits" is equal to zero.
1604 Beware that the whole bit vector is cleared WITHOUT WARNING if
1606 "$bits" is greater than or equal to the size of the given bit vector!
1607 In fact this method is equivalent to
1609 for ( $i = 0; $i < $bits; $i++ ) { $vector->shift_left(0); }
1611 except that it is much more efficient (for "$bits" greater than or
1613 equal to the number of bits in a machine word on your system) than
1614 this straightforward approach.
1615 • "$vector->Move_Right($bits);"
1617 Shifts the given bit vector right by "$bits" bits, i.e., deletes the
1619 "$bits" least significant bits of the bit vector, moving all other
1620 bits down by "$bits" places, thereby creating "$bits" new bits at the
1621 upper end (most significant bit) of the bit vector.
1622 These new bits are all cleared (set to the "off" state).
1624 This method does nothing if "$bits" is equal to zero.
1626 Beware that the whole bit vector is cleared WITHOUT WARNING if
1628 "$bits" is greater than or equal to the size of the given bit vector!
1629 In fact this method is equivalent to
1631 for ( $i = 0; $i < $bits; $i++ ) { $vector->shift_right(0); }
1633 except that it is much more efficient (for "$bits" greater than or
1635 equal to the number of bits in a machine word on your system) than
1636 this straightforward approach.
1637 • "$vector->Insert($offset,$bits);"
1639 This method inserts "$bits" fresh new bits at position "$offset" in
1641 the given bit vector.
1642 The "$bits" most significant bits are lost, and all bits starting
1644 with bit number "$offset" up to and including bit number
1645 ""$vector->Size()-$bits-1"" are moved up by "$bits" places.
1646 The now vacant "$bits" bits starting at bit number "$offset" (up to
1648 and including bit number ""$offset+$bits-1"") are then set to zero
1649 (cleared).
1650 Note that this method does NOT increase the size of the given bit
1652 vector, i.e., the bit vector is NOT extended at its upper end to
1653 "rescue" the "$bits" uppermost (most significant) bits - instead,
1654 these bits are lost forever.
1655 If you don't want this to happen, you have to increase the size of
1657 the given bit vector EXPLICITLY and BEFORE you perform the "Insert"
1658 operation, with a statement such as the following:
1659 $vector->Resize($vector->Size() + $bits);
1661 Or use the method "Interval_Substitute()" instead of "Insert()",
1663 which performs automatic growing and shrinking of its target bit
1664 vector.
1665 Note also that "$offset" must lie in the permitted range between "0"
1667 and ""$vector->Size()-1"", or a fatal "offset out of range" error
1668 will occur.
1669 If the term ""$offset + $bits"" exceeds ""$vector->Size()-1"", all
1671 the bits starting with bit number "$offset" up to bit number
1672 ""$vector->Size()-1"" are simply cleared.
1673 • "$vector->Delete($offset,$bits);"
1675 This method deletes, i.e., removes the bits starting at position
1677 "$offset" up to and including bit number ""$offset+$bits-1"" from the
1678 given bit vector.
1679 The remaining uppermost bits (starting at position ""$offset+$bits""
1681 up to and including bit number ""$vector->Size()-1"") are moved down
1682 by "$bits" places.
1683 The now vacant uppermost (most significant) "$bits" bits are then set
1685 to zero (cleared).
1686 Note that this method does NOT decrease the size of the given bit
1688 vector, i.e., the bit vector is NOT clipped at its upper end to "get
1689 rid of" the vacant "$bits" uppermost bits.
1690 If you don't want this, i.e., if you want the bit vector to shrink
1692 accordingly, you have to do so EXPLICITLY and AFTER the "Delete"
1693 operation, with a couple of statements such as these:
1694 $size = $vector->Size();
1696 if ($bits > $size) { $bits = $size; }
1697 $vector->Resize($size - $bits);
1698 Or use the method "Interval_Substitute()" instead of "Delete()",
1700 which performs automatic growing and shrinking of its target bit
1701 vector.
1702 Note also that "$offset" must lie in the permitted range between "0"
1704 and ""$vector->Size()-1"", or a fatal "offset out of range" error
1705 will occur.
1706 If the term ""$offset + $bits"" exceeds ""$vector->Size()-1"", all
1708 the bits starting with bit number "$offset" up to bit number
1709 ""$vector->Size()-1"" are simply cleared.
1710 • "$carry = $vector->increment();"
1712 This method increments the given bit vector.
1714 Note that this method regards bit vectors as being unsigned, i.e.,
1716 the largest possible positive number is directly followed by the
1717 smallest possible (or greatest possible, speaking in absolute terms)
1718 negative number:
1719 before: 2 ^ (b-1) - 1 (= "0111...1111")
1721 after: 2 ^ (b-1) (= "1000...0000")
1722 where ""b"" is the number of bits of the given bit vector.
1724 The method returns "false" ("0") in all cases except when a carry
1726 over occurs (in which case it returns "true", i.e., "1"), which
1727 happens when the number "1111...1111" is incremented, which gives
1728 "0000...0000" plus a carry over to the next higher (binary) digit.
1729 This can be used for the terminating condition of a "while" loop, for
1731 instance, in order to cycle through all possible values the bit
1732 vector can assume.
1733 • "$carry = $vector->decrement();"
1735 This method decrements the given bit vector.
1737 Note that this method regards bit vectors as being unsigned, i.e.,
1739 the smallest possible (or greatest possible, speaking in absolute
1740 terms) negative number is directly followed by the largest possible
1741 positive number:
1742 before: 2 ^ (b-1) (= "1000...0000")
1744 after: 2 ^ (b-1) - 1 (= "0111...1111")
1745 where ""b"" is the number of bits of the given bit vector.
1747 The method returns "false" ("0") in all cases except when a carry
1749 over occurs (in which case it returns "true", i.e., "1"), which
1750 happens when the number "0000...0000" is decremented, which gives
1751 "1111...1111" minus a carry over to the next higher (binary) digit.
1752 This can be used for the terminating condition of a "while" loop, for
1754 instance, in order to cycle through all possible values the bit
1755 vector can assume.
1756 • "$overflow = $vec2->inc($vec1);"
1758 This method copies the contents of bit vector "$vec1" to bit vector
1760 "$vec2" and increments the copy (not the original).
1761 If by incrementing the number its sign becomes invalid, the return
1763 value ("overflow" flag) will be true ("1"), or false ("0") if not.
1764 (See the description of the method "add()" below for a more in-depth
1765 explanation of what "overflow" means).
1766 Note that in-place operation is also possible, i.e., "$vec1" and
1768 "$vec2" may be identical.
1769 • "$overflow = $vec2->dec($vec1);"
1771 This method copies the contents of bit vector "$vec1" to bit vector
1773 "$vec2" and decrements the copy (not the original).
1774 If by decrementing the number its sign becomes invalid, the return
1776 value ("overflow" flag) will be true ("1"), or false ("0") if not.
1777 (See the description of the method "subtract()" below for a more in-
1778 depth explanation of what "overflow" means).
1779 Note that in-place operation is also possible, i.e., "$vec1" and
1781 "$vec2" may be identical.
1782 • "$carry = $vec3->add($vec1,$vec2,$carry);"
1784 "($carry,$overflow) = $vec3->add($vec1,$vec2,$carry);"
1786 This method adds the two numbers contained in bit vector "$vec1" and
1788 "$vec2" with carry "$carry" and stores the result in bit vector
1789 "$vec3".
1790 I.e.,
1792 $vec3 = $vec1 + $vec2 + $carry
1793 Note that the "$carry" parameter is a boolean value, i.e., only its
1795 least significant bit is taken into account. (Think of it as though
1796 ""$carry &= 1;"" was always executed internally.)
1797 In scalar context, the method returns a boolean value which indicates
1799 if a carry over (to the next higher bit position) has occured. In
1800 list context, the method returns the carry and the overflow flag (in
1801 this order).
1802 The overflow flag is true ("1") if the sign (i.e., the most
1804 significant bit) of the result is wrong. This can happen when adding
1805 two very large positive numbers or when adding two (by their absolute
1806 value) very large negative numbers. See also further below.
1807 The carry in- and output is needed mainly for cascading, i.e., to add
1809 numbers that are fragmented into several pieces.
1810 Example:
1812 # initialize
1814 for ( $i = 0; $i < $n; $i++ )
1816 {
1817 $a[$i] = Bit::Vector->new($bits);
1818 $b[$i] = Bit::Vector->new($bits);
1819 $c[$i] = Bit::Vector->new($bits);
1820 }
1821 # fill @a and @b
1823 # $a[ 0 ] is low order part,
1825 # $a[$n-1] is high order part,
1826 # and same for @b
1827 # add
1829 $carry = 0;
1831 for ( $i = 0; $i < $n; $i++ )
1832 {
1833 $carry = $c[$i]->add($a[$i],$b[$i],$carry);
1834 }
1835 Note that it makes no difference to this method whether the numbers
1837 in "$vec1" and "$vec2" are unsigned or signed (i.e., in two's
1838 complement binary representation).
1839 Note however that the return value (carry flag) is not meaningful
1841 when the numbers are SIGNED.
1842 Moreover, when the numbers are signed, a special type of error can
1844 occur which is commonly called an "overflow error".
1845 An overflow error occurs when the sign of the result (its most
1847 significant bit) is flipped (i.e., falsified) by a carry over from
1848 the next-lower bit position ("MSB-1").
1849 In fact matters are a bit more complicated than that: the overflow
1851 flag is set to "true" whenever there is a carry over from bit
1852 position MSB-1 to the most significant bit (MSB) but no carry over
1853 from the MSB to the output carry flag, or vice-versa, i.e., when
1854 there is no carry over from bit position MSB-1 to the most
1855 significant bit (MSB) but a carry over to the output carry flag.
1856 Thus the overflow flag is the result of an exclusive-or operation
1858 between incoming and outgoing carry over at the most significant bit
1859 position.
1860 • "$carry = $vec3->subtract($vec1,$vec2,$carry);"
1862 "($carry,$overflow) = $vec3->subtract($vec1,$vec2,$carry);"
1864 This method subtracts the two numbers contained in bit vector "$vec1"
1866 and "$vec2" with carry "$carry" and stores the result in bit vector
1867 "$vec3".
1868 I.e.,
1870 $vec3 = $vec1 - $vec2 - $carry
1871 Note that the "$carry" parameter is a boolean value, i.e., only its
1873 least significant bit is taken into account. (Think of it as though
1874 ""$carry &= 1;"" was always executed internally.)
1875 In scalar context, the method returns a boolean value which indicates
1877 if a carry over (to the next higher bit position) has occured. In
1878 list context, the method returns the carry and the overflow flag (in
1879 this order).
1880 The overflow flag is true ("1") if the sign (i.e., the most
1882 significant bit) of the result is wrong. This can happen when
1883 subtracting a very large negative number from a very large positive
1884 number or vice-versa. See also further below.
1885 The carry in- and output is needed mainly for cascading, i.e., to
1887 subtract numbers that are fragmented into several pieces.
1888 Example:
1890 # initialize
1892 for ( $i = 0; $i < $n; $i++ )
1894 {
1895 $a[$i] = Bit::Vector->new($bits);
1896 $b[$i] = Bit::Vector->new($bits);
1897 $c[$i] = Bit::Vector->new($bits);
1898 }
1899 # fill @a and @b
1901 # $a[ 0 ] is low order part,
1903 # $a[$n-1] is high order part,
1904 # and same for @b
1905 # subtract
1907 $carry = 0;
1909 for ( $i = 0; $i < $n; $i++ )
1910 {
1911 $carry = $c[$i]->subtract($a[$i],$b[$i],$carry);
1912 }
1913 Note that it makes no difference to this method whether the numbers
1915 in "$vec1" and "$vec2" are unsigned or signed (i.e., in two's
1916 complement binary representation).
1917 Note however that the return value (carry flag) is not meaningful
1919 when the numbers are SIGNED.
1920 Moreover, when the numbers are signed, a special type of error can
1922 occur which is commonly called an "overflow error".
1923 An overflow error occurs when the sign of the result (its most
1925 significant bit) is flipped (i.e., falsified) by a carry over from
1926 the next-lower bit position ("MSB-1").
1927 In fact matters are a bit more complicated than that: the overflow
1929 flag is set to "true" whenever there is a carry over from bit
1930 position MSB-1 to the most significant bit (MSB) but no carry over
1931 from the MSB to the output carry flag, or vice-versa, i.e., when
1932 there is no carry over from bit position MSB-1 to the most
1933 significant bit (MSB) but a carry over to the output carry flag.
1934 Thus the overflow flag is the result of an exclusive-or operation
1936 between incoming and outgoing carry over at the most significant bit
1937 position.
1938 • "$vec2->Neg($vec1);"
1940 "$vec2->Negate($vec1);"
1942 This method calculates the two's complement of the number in bit
1944 vector "$vec1" and stores the result in bit vector "$vec2".
1945 Calculating the two's complement of a given number in binary
1947 representation consists of inverting all bits and incrementing the
1948 result by one.
1949 This is the same as changing the sign of the given number from ""+""
1951 to ""-"" or vice-versa. In other words, applying this method twice on
1952 a given number yields the original number again.
1953 Note that in-place processing is also possible, i.e., "$vec1" and
1955 "$vec2" may be identical.
1956 Most importantly, beware that this method produces a counter-
1958 intuitive result if the number contained in bit vector "$vec1" is "2
1959 ^ (n-1)" (i.e., "1000...0000"), where ""n"" is the number of bits the
1960 given bit vector contains: The negated value of this number is the
1961 number itself!
1962 • "$vec2->Abs($vec1);"
1964 "$vec2->Absolute($vec1);"
1966 Depending on the sign (i.e., the most significant bit) of the number
1968 in bit vector "$vec1", the contents of bit vector "$vec1" are copied
1969 to bit vector "$vec2" either with the method "Copy()" (if the number
1970 in bit vector "$vec1" is positive), or with "Negate()" (if the number
1971 in bit vector "$vec1" is negative).
1972 In other words, this method calculates the absolute value of the
1974 number in bit vector "$vec1" and stores the result in bit vector
1975 "$vec2".
1976 Note that in-place processing is also possible, i.e., "$vec1" and
1978 "$vec2" may be identical.
1979 Most importantly, beware that this method produces a counter-
1981 intuitive result if the number contained in bit vector "$vec1" is "2
1982 ^ (n-1)" (i.e., "1000...0000"), where ""n"" is the number of bits the
1983 given bit vector contains: The absolute value of this number is the
1984 number itself, even though this number is still negative by
1985 definition (the most significant bit is still set)!
1986 • "$sign = $vector->Sign();"
1988 This method returns "0" if all bits in the given bit vector are
1990 cleared, i.e., if the given bit vector contains the number "0", or if
1991 the given bit vector has a length of zero (contains no bits at all).
1992 If not all bits are cleared, this method returns "-1" if the most
1994 significant bit is set (i.e., if the bit vector contains a negative
1995 number), or "1" otherwise (i.e., if the bit vector contains a
1996 positive number).
1997 • "$vec3->Multiply($vec1,$vec2);"
1999 This method multiplies the two numbers contained in bit vector
2001 "$vec1" and "$vec2" and stores the result in bit vector "$vec3".
2002 Note that this method regards its arguments as SIGNED.
2004 If you want to make sure that a large number can never be treated as
2006 being negative by mistake, make your bit vectors at least one bit
2007 longer than the largest number you wish to represent, right from the
2008 start, or proceed as follows:
2009 $msb1 = $vec1->msb();
2011 $msb2 = $vec2->msb();
2012 $vec1->Resize($vec1->Size()+1);
2013 $vec2->Resize($vec2->Size()+1);
2014 $vec3->Resize($vec3->Size()+1);
2015 $vec1->MSB($msb1);
2016 $vec2->MSB($msb2);
2017 $vec3->Multiply($vec1,$vec2);
2018 Note also that all three bit vector arguments must in principle obey
2020 the rule of matching sizes, but that the bit vector "$vec3" may be
2021 larger than the two factors "$vec1" and "$vec2".
2022 In fact multiplying two binary numbers with ""n"" bits may yield a
2024 result which is at most ""2n"" bits long.
2025 Therefore, it is usually a good idea to let bit vector "$vec3" have
2027 twice the size of bit vector "$vec1" and "$vec2", unless you are
2028 absolutely sure that the result will fit into a bit vector of the
2029 same size as the two factors.
2030 If you are wrong, a fatal "numeric overflow error" will occur.
2032 Finally, note that in-place processing is possible, i.e., "$vec3" may
2034 be identical with "$vec1" or "$vec2", or both.
2035 • "$quot->Divide($vec1,$vec2,$rest);"
2037 This method divides the two numbers contained in bit vector "$vec1"
2039 and "$vec2" and stores the quotient in bit vector "$quot" and the
2040 remainder in bit vector "$rest".
2041 I.e.,
2043 $quot = $vec1 / $vec2; # div
2044 $rest = $vec1 % $vec2; # mod
2045 Therefore, "$quot" and "$rest" must be two DISTINCT bit vectors, or a
2047 fatal "result vector(s) must be distinct" error will occur.
2048 Note also that a fatal "division by zero error" will occur if "$vec2"
2050 is equal to zero.
2051 Note further that this method regards its arguments as SIGNED.
2053 If you want to make sure that a large number can never be treated as
2055 being negative by mistake, make your bit vectors at least one bit
2056 longer than the largest number you wish to represent, right from the
2057 start, or proceed as follows:
2058 $msb1 = $vec1->msb();
2060 $msb2 = $vec2->msb();
2061 $vec1->Resize($vec1->Size()+1);
2062 $vec2->Resize($vec2->Size()+1);
2063 $quot->Resize($quot->Size()+1);
2064 $rest->Resize($rest->Size()+1);
2065 $vec1->MSB($msb1);
2066 $vec2->MSB($msb2);
2067 $quot->Divide($vec1,$vec2,$rest);
2068 Finally, note that in-place processing is possible, i.e., "$quot" may
2070 be identical with "$vec1" or "$vec2" or both, and "$rest" may also be
2071 identical with "$vec1" or "$vec2" or both, as long as "$quot" and
2072 "$rest" are distinct. (!)
2073 • "$vecgcd->GCD($veca,$vecb);"
2075 This method calculates the "Greatest Common Divisor" of the two
2077 numbers contained in bit vector "$veca" and "$vecb" and stores the
2078 result in bit vector "$vecgcd".
2079 The method uses Euklid's algorithm internally:
2081 int GCD(int a, int b)
2083 {
2084 int t;
2085 while (b != 0)
2087 {
2088 t = a % b; /* = remainder of (a div b) */
2089 a = b;
2090 b = t;
2091 }
2092 return(a);
2093 }
2094 Note that "GCD(z,0) == GCD(0,z) == z".
2096 • "$vecgcd->GCD($vecx,$vecy,$veca,$vecb);"
2098 This variant of the "GCD" method calculates the "Greatest Common
2100 Divisor" of the two numbers contained in bit vector "$veca" and
2101 "$vecb" and stores the result in bit vector "$vecgcd".
2102 Moreover, it determines the two factors which are necessary in order
2104 to represent the greatest common divisor as a linear combination of
2105 its two arguments, i.e., the two factors "x" and "y" so that
2106 "GCD(a,b) == x * a + y * b", and stores them in bit vector "$vecx"
2107 and "$vecy", respectively.
2108 For example:
2110 a = 2322
2112 b = 654
2113 GCD( 2322, 654 ) == 6
2115 x = 20
2117 y = -71
2118 20 * 2322 - 71 * 654 == 6
2120 Please see http://www.cut-the-knot.org/blue/extension.shtml for an
2122 explanation of how this extension of Euklid's algorithm works.
2123 • "$vec3->Power($vec1,$vec2);"
2125 This method calculates the exponentiation of base "$vec1" elevated to
2127 the "$vec2" power, i.e., ""$vec1 ** $vec2"", and stores the result in
2128 bit vector "$vec3".
2129 The method uses an efficient divide-and-conquer algorithm:
2131 Suppose the exponent is (decimal) 13, for example. The binary
2133 representation of this exponent is "1101".
2134 This means we want to calculate
2136 $vec1 * $vec1 * $vec1 * $vec1 * $vec1 * $vec1 * $vec1 * $vec1 *
2138 $vec1 * $vec1 * $vec1 * $vec1 *
2139 $vec1
2140 That is, "$vec1" multiplied with itself 13 times. The grouping into
2142 lines above is no coincidence. The first line comprises 8 factors,
2143 the second contains 4, and the last line just one. This just happens
2144 to be the binary representation of 13. ";-)"
2145 We then calculate a series of squares (of squares of squares...) of
2147 the base, i.e.,
2148 $power[0] = $vec1;
2150 $power[1] = $vec1 * $vec1;
2151 $power[2] = $power[1] * $power[1];
2152 $power[3] = $power[2] * $power[2];
2153 etc.
2154 To calculate the power of our example, we simply initialize our
2156 result with 1 and consecutively multiply it with the items of the
2157 series of powers we just calculated, if the corresponding bit of the
2158 binary representation of the exponent is set:
2159 $result = 1;
2161 $result *= $power[0] if ($vec2 & 1);
2162 $result *= $power[1] if ($vec2 & 2);
2163 $result *= $power[2] if ($vec2 & 4);
2164 $result *= $power[3] if ($vec2 & 8);
2165 etc.
2166 The bit vector "$vec3" must be of the same size as the base "$vec1"
2168 or greater. "$vec3" and "$vec1" may be the same vector (i.e., in-
2169 place calculation as in ""$vec1 **= $vec2;"" is possible), but
2170 "$vec3" and "$vec2" must be distinct. Finally, the exponent "$vec2"
2171 must be positive. A fatal error occurs if any of these conditions is
2172 not met.
2173 • "$vector->Block_Store($buffer);"
2175 This method allows you to load the contents of a given bit vector in
2177 one go.
2178 This is useful when you store the contents of a bit vector in a file,
2180 for instance (using method "Block_Read()"), and when you want to
2181 restore the previously saved bit vector.
2182 For this, "$buffer" MUST be a string (NO automatic conversion from
2184 numeric to string is provided here as would normally in Perl!)
2185 containing the bit vector in "low order byte first" order.
2186 If the given string is shorter than what is needed to completely fill
2188 the given bit vector, the remaining (most significant) bytes of the
2189 bit vector are filled with zeros, i.e., the previous contents of the
2190 bit vector are always erased completely.
2191 If the given string is longer than what is needed to completely fill
2193 the given bit vector, the superfluous bytes are simply ignored.
2194 See "sysread" in perlfunc for how to read in the contents of
2196 "$buffer" from a file prior to passing it to this method.
2197 • "$buffer = $vector->Block_Read();"
2199 This method allows you to export the contents of a given bit vector
2201 in one block.
2202 This is useful when you want to save the contents of a bit vector for
2204 later, for instance in a file.
2205 The advantage of this method is that it allows you to do so in the
2207 compactest possible format, in binary.
2208 The method returns a Perl string which contains an exact copy of the
2210 contents of the given bit vector in "low order byte first" order.
2211 See "syswrite" in perlfunc for how to write the data from this string
2213 to a file.
2214 • "$size = $vector->Word_Size();"
2216 Each bit vector is internally organized as an array of machine words.
2218 The methods whose names begin with "Word_" allow you to access this
2220 internal array of machine words.
2221 Note that because the size of a machine word may vary from system to
2223 system, these methods are inherently MACHINE-DEPENDENT!
2224 Therefore, DO NOT USE these methods unless you are absolutely certain
2226 that portability of your code is not an issue!
2227 You have been warned!
2229 To be machine-independent, use the methods whose names begin with
2231 ""Chunk_"" instead, with chunk sizes no greater than 32 bits.
2232 The method "Word_Size()" returns the number of machine words that the
2234 internal array of words of the given bit vector contains.
2235 This is similar in function to the term "scalar(@array)" for a Perl
2237 array.
2238 • "$vector->Word_Store($offset,$word);"
2240 This method allows you to store a given value "$word" at a given
2242 position "$offset" in the internal array of words of the given bit
2243 vector.
2244 Note that "$offset" must lie in the permitted range between "0" and
2246 ""$vector->Word_Size()-1"", or a fatal "offset out of range" error
2247 will occur.
2248 This method is similar in function to the expression
2250 ""$array[$offset] = $word;"" for a Perl array.
2251 • "$word = $vector->Word_Read($offset);"
2253 This method allows you to access the value of a given machine word at
2255 position "$offset" in the internal array of words of the given bit
2256 vector.
2257 Note that "$offset" must lie in the permitted range between "0" and
2259 ""$vector->Word_Size()-1"", or a fatal "offset out of range" error
2260 will occur.
2261 This method is similar in function to the expression ""$word =
2263 $array[$offset];"" for a Perl array.
2264 • "$vector->Word_List_Store(@words);"
2266 This method allows you to store a list of values "@words" in the
2268 internal array of machine words of the given bit vector.
2269 Thereby the LEFTMOST value in the list ("$words[0]") is stored in the
2271 LEAST significant word of the internal array of words (the one with
2272 offset "0"), the next value from the list ("$words[1]") is stored in
2273 the word with offset "1", and so on, as intuitively expected.
2274 If the list "@words" contains fewer elements than the internal array
2276 of words of the given bit vector contains machine words, the
2277 remaining (most significant) words are filled with zeros.
2278 If the list "@words" contains more elements than the internal array
2280 of words of the given bit vector contains machine words, the
2281 superfluous values are simply ignored.
2282 This method is comparable in function to the expression ""@array =
2284 @words;"" for a Perl array.
2285 • "@words = $vector->Word_List_Read();"
2287 This method allows you to retrieve the internal array of machine
2289 words of the given bit vector all at once.
2290 Thereby the LEFTMOST value in the returned list ("$words[0]") is the
2292 LEAST significant word from the given bit vector, and the RIGHTMOST
2293 value in the returned list ("$words[$#words]") is the MOST
2294 significant word of the given bit vector.
2295 This method is similar in function to the expression ""@words =
2297 @array;"" for a Perl array.
2298 • "$vector->Word_Insert($offset,$count);"
2300 This method inserts "$count" empty new machine words at position
2302 "$offset" in the internal array of words of the given bit vector.
2303 The "$count" most significant words are lost, and all words starting
2305 with word number "$offset" up to and including word number
2306 ""$vector->Word_Size()-$count-1"" are moved up by "$count" places.
2307 The now vacant "$count" words starting at word number "$offset" (up
2309 to and including word number ""$offset+$count-1"") are then set to
2310 zero (cleared).
2311 Note that this method does NOT increase the size of the given bit
2313 vector, i.e., the bit vector is NOT extended at its upper end to
2314 "rescue" the "$count" uppermost (most significant) words - instead,
2315 these words are lost forever.
2316 If you don't want this to happen, you have to increase the size of
2318 the given bit vector EXPLICITLY and BEFORE you perform the "Insert"
2319 operation, with a statement such as the following:
2320 $vector->Resize($vector->Size() + $count * Bit::Vector->Word_Bits());
2322 Note also that "$offset" must lie in the permitted range between "0"
2324 and ""$vector->Word_Size()-1"", or a fatal "offset out of range"
2325 error will occur.
2326 If the term ""$offset + $count"" exceeds ""$vector->Word_Size()-1"",
2328 all the words starting with word number "$offset" up to word number
2329 ""$vector->Word_Size()-1"" are simply cleared.
2330 • "$vector->Word_Delete($offset,$count);"
2332 This method deletes, i.e., removes the words starting at position
2334 "$offset" up to and including word number ""$offset+$count-1"" from
2335 the internal array of machine words of the given bit vector.
2336 The remaining uppermost words (starting at position
2338 ""$offset+$count"" up to and including word number
2339 ""$vector->Word_Size()-1"") are moved down by "$count" places.
2340 The now vacant uppermost (most significant) "$count" words are then
2342 set to zero (cleared).
2343 Note that this method does NOT decrease the size of the given bit
2345 vector, i.e., the bit vector is NOT clipped at its upper end to "get
2346 rid of" the vacant "$count" uppermost words.
2347 If you don't want this, i.e., if you want the bit vector to shrink
2349 accordingly, you have to do so EXPLICITLY and AFTER the "Delete"
2350 operation, with a couple of statements such as these:
2351 $bits = $vector->Size();
2353 $count *= Bit::Vector->Word_Bits();
2354 if ($count > $bits) { $count = $bits; }
2355 $vector->Resize($bits - $count);
2356 Note also that "$offset" must lie in the permitted range between "0"
2358 and ""$vector->Word_Size()-1"", or a fatal "offset out of range"
2359 error will occur.
2360 If the term ""$offset + $count"" exceeds ""$vector->Word_Size()-1"",
2362 all the words starting with word number "$offset" up to word number
2363 ""$vector->Word_Size()-1"" are simply cleared.
2364 • "$vector->Chunk_Store($chunksize,$offset,$chunk);"
2366 This method allows you to set more than one bit at a time with
2368 different values.
2369 You can access chunks (i.e., ranges of contiguous bits) between one
2371 and at most ""Bit::Vector->Long_Bits()"" bits wide.
2372 In order to be portable, though, you should never use chunk sizes
2374 larger than 32 bits.
2375 If the given "$chunksize" does not lie between "1" and
2377 ""Bit::Vector->Long_Bits()"", a fatal "chunk size out of range" error
2378 will occur.
2379 The method copies the "$chunksize" least significant bits from the
2381 value "$chunk" to the given bit vector, starting at bit position
2382 "$offset" and proceeding upwards until bit number
2383 ""$offset+$chunksize-1"".
2384 (I.e., bit number "0" of "$chunk" becomes bit number "$offset" in the
2386 given bit vector, and bit number ""$chunksize-1"" becomes bit number
2387 ""$offset+$chunksize-1"".)
2388 If the term ""$offset+$chunksize-1"" exceeds ""$vector->Size()-1"",
2390 the corresponding superfluous (most significant) bits from "$chunk"
2391 are simply ignored.
2392 Note that "$offset" itself must lie in the permitted range between
2394 "0" and ""$vector->Size()-1"", or a fatal "offset out of range" error
2395 will occur.
2396 This method (as well as the other ""Chunk_"" methods) is useful, for
2398 example, when you are reading in data in chunks of, say, 8 bits,
2399 which you need to access later, say, using 16 bits at a time (like
2400 audio CD wave files, for instance).
2401 • "$chunk = $vector->Chunk_Read($chunksize,$offset);"
2403 This method allows you to read the values of more than one bit at a
2405 time.
2406 You can read chunks (i.e., ranges of contiguous bits) between one and
2408 at most ""Bit::Vector->Long_Bits()"" bits wide.
2409 In order to be portable, though, you should never use chunk sizes
2411 larger than 32 bits.
2412 If the given "$chunksize" does not lie between "1" and
2414 ""Bit::Vector->Long_Bits()"", a fatal "chunk size out of range" error
2415 will occur.
2416 The method returns the "$chunksize" bits from the given bit vector
2418 starting at bit position "$offset" and proceeding upwards until bit
2419 number ""$offset+$chunksize-1"".
2420 (I.e., bit number "$offset" of the given bit vector becomes bit
2422 number "0" of the returned value, and bit number
2423 ""$offset+$chunksize-1"" becomes bit number ""$chunksize-1"".)
2424 If the term ""$offset+$chunksize-1"" exceeds ""$vector->Size()-1"",
2426 the non-existent bits are simply not returned.
2427 Note that "$offset" itself must lie in the permitted range between
2429 "0" and ""$vector->Size()-1"", or a fatal "offset out of range" error
2430 will occur.
2431 • "$vector->Chunk_List_Store($chunksize,@chunks);"
2433 This method allows you to fill the given bit vector with a list of
2435 data packets ("chunks") of any size ("$chunksize") you like (within
2436 certain limits).
2437 In fact the given "$chunksize" must lie in the range between "1" and
2439 ""Bit::Vector->Long_Bits()"", or a fatal "chunk size out of range"
2440 error will occur.
2441 In order to be portable, though, you should never use chunk sizes
2443 larger than 32 bits.
2444 The given bit vector is thereby filled in ascending order: The first
2446 chunk from the list (i.e., "$chunks[0]") fills the "$chunksize" least
2447 significant bits, the next chunk from the list ("$chunks[1]") fills
2448 the bits number "$chunksize" to number ""2*$chunksize-1"", the third
2449 chunk ("$chunks[2]") fills the bits number ""2*$chunksize"", to
2450 number ""3*$chunksize-1"", and so on.
2451 If there a less chunks in the list than are needed to fill the entire
2453 bit vector, the remaining (most significant) bits are cleared, i.e.,
2454 the previous contents of the given bit vector are always erased
2455 completely.
2456 If there are more chunks in the list than are needed to fill the
2458 entire bit vector, and/or if a chunk extends beyond
2459 ""$vector->Size()-1"" (which happens whenever ""$vector->Size()"" is
2460 not a multiple of "$chunksize"), the superfluous chunks and/or bits
2461 are simply ignored.
2462 The method is useful, for example (and among many other
2464 applications), for the conversion of packet sizes in a data stream.
2465 This method can also be used to store an octal string in a given bit
2467 vector:
2468 $vector->Chunk_List_Store(3, split(//, reverse $string));
2470 Note however that unlike the conversion methods "from_Hex()",
2472 "from_Bin()", "from_Dec()" and "from_Enum()", this statement does not
2473 include any syntax checking, i.e., it may fail silently, without
2474 warning.
2475 To perform syntax checking, add the following statements:
2477 if ($string =~ /^[0-7]+$/)
2479 {
2480 # okay, go ahead with conversion as shown above
2481 }
2482 else
2483 {
2484 # error, string contains other than octal characters
2485 }
2486 Another application is to store a repetitive pattern in a given bit
2488 vector:
2489 $pattern = 0xDEADBEEF;
2491 $length = 32; # = length of $pattern in bits
2492 $size = $vector->Size();
2493 $factor = int($size / $length);
2494 if ($size % $length) { $factor++; }
2495 $vector->Chunk_List_Store($length, ($pattern) x $factor);
2496 • "@chunks = $vector->Chunk_List_Read($chunksize);"
2498 This method allows you to access the contents of the given bit vector
2500 in form of a list of data packets ("chunks") of a size ("$chunksize")
2501 of your choosing (within certain limits).
2502 In fact the given "$chunksize" must lie in the range between "1" and
2504 ""Bit::Vector->Long_Bits()"", or a fatal "chunk size out of range"
2505 error will occur.
2506 In order to be portable, though, you should never use chunk sizes
2508 larger than 32 bits.
2509 The given bit vector is thereby read in ascending order: The
2511 "$chunksize" least significant bits (bits number "0" to
2512 ""$chunksize-1"") become the first chunk in the returned list (i.e.,
2513 "$chunks[0]"). The bits number "$chunksize" to ""2*$chunksize-1""
2514 become the next chunk in the list ("$chunks[1]"), and so on.
2515 If ""$vector->Size()"" is not a multiple of "$chunksize", the last
2517 chunk in the list will contain fewer bits than "$chunksize".
2518 BEWARE that for large bit vectors and/or small values of
2520 "$chunksize", the number of returned list elements can be extremely
2521 large! BE CAREFUL!
2522 You could blow up your application with lack of memory (each list
2524 element is a full-grown Perl scalar, internally, with an associated
2525 memory overhead for its administration!) or at least cause a
2526 noticeable, more or less long-lasting "freeze" of your application!
2527 Possible applications:
2529 The method is especially useful in the conversion of packet sizes in
2531 a data stream.
2532 This method can also be used to convert a given bit vector to a
2534 string of octal numbers:
2535 $string = reverse join('', $vector->Chunk_List_Read(3));
2537 • "$vector->Index_List_Remove(@indices);"
2539 This method allows you to specify a list of indices of bits which
2541 should be turned off in the given bit vector.
2542 In fact this method is a shortcut for
2544 foreach $index (@indices)
2546 {
2547 $vector->Bit_Off($index);
2548 }
2549 In contrast to all other import methods in this module, this method
2551 does NOT clear the given bit vector before processing its list of
2552 arguments.
2553 Instead, this method allows you to accumulate the results of various
2555 consecutive calls.
2556 (The same holds for the method "Index_List_Store()". As a
2558 consequence, you can "wipe out" what you did using the method
2559 "Index_List_Remove()" by passing the identical argument list to the
2560 method "Index_List_Store()".)
2561 • "$vector->Index_List_Store(@indices);"
2563 This method allows you to specify a list of indices of bits which
2565 should be turned on in the given bit vector.
2566 In fact this method is a shortcut for
2568 foreach $index (@indices)
2570 {
2571 $vector->Bit_On($index);
2572 }
2573 In contrast to all other import methods in this module, this method
2575 does NOT clear the given bit vector before processing its list of
2576 arguments.
2577 Instead, this method allows you to accumulate the results of various
2579 consecutive calls.
2580 (The same holds for the method "Index_List_Remove()". As a
2582 consequence, you can "wipe out" what you did using the method
2583 "Index_List_Store()" by passing the identical argument list to the
2584 method "Index_List_Remove()".)
2585 • "@indices = $vector->Index_List_Read();"
2587 This method returns a list of Perl scalars.
2589 The list contains one scalar for each set bit in the given bit
2591 vector.
2592 BEWARE that for large bit vectors, this can result in a literally
2594 overwhelming number of list elements! BE CAREFUL! You could run out
2595 of memory or slow down your application considerably!
2596 Each scalar contains the number of the index corresponding to the bit
2598 in question.
2599 These indices are always returned in ascending order.
2601 If the given bit vector is empty (contains only cleared bits) or if
2603 it has a length of zero (if it contains no bits at all), the method
2604 returns an empty list.
2605 This method can be useful, for instance, to obtain a list of prime
2607 numbers:
2608 $limit = 1000; # or whatever
2610 $vector = Bit::Vector->new($limit+1);
2611 $vector->Primes();
2612 @primes = $vector->Index_List_Read();
2613 • "$vec3->Or($vec1,$vec2);"
2615 "$set3->Union($set1,$set2);"
2617 This method calculates the union of "$set1" and "$set2" and stores
2619 the result in "$set3".
2620 This is usually written as ""$set3 = $set1 u $set2"" in set theory
2622 (where "u" is the "cup" operator).
2623 (On systems where the "cup" character is unavailable this operator is
2625 often denoted by a plus sign "+".)
2626 In-place calculation is also possible, i.e., "$set3" may be identical
2628 with "$set1" or "$set2" or both.
2629 • "$vec3->And($vec1,$vec2);"
2631 "$set3->Intersection($set1,$set2);"
2633 This method calculates the intersection of "$set1" and "$set2" and
2635 stores the result in "$set3".
2636 This is usually written as ""$set3 = $set1 n $set2"" in set theory
2638 (where "n" is the "cap" operator).
2639 (On systems where the "cap" character is unavailable this operator is
2641 often denoted by an asterisk "*".)
2642 In-place calculation is also possible, i.e., "$set3" may be identical
2644 with "$set1" or "$set2" or both.
2645 • "$vec3->AndNot($vec1,$vec2);"
2647 "$set3->Difference($set1,$set2);"
2649 This method calculates the difference of "$set1" less "$set2" and
2651 stores the result in "$set3".
2652 This is usually written as ""$set3 = $set1 \ $set2"" in set theory
2654 (where "\" is the "less" operator).
2655 In-place calculation is also possible, i.e., "$set3" may be identical
2657 with "$set1" or "$set2" or both.
2658 • "$vec3->Xor($vec1,$vec2);"
2660 "$set3->ExclusiveOr($set1,$set2);"
2662 This method calculates the symmetric difference of "$set1" and
2664 "$set2" and stores the result in "$set3".
2665 This can be written as ""$set3 = ($set1 u $set2) \ ($set1 n $set2)""
2667 in set theory (the union of the two sets less their intersection).
2668 When sets are implemented as bit vectors then the above formula is
2670 equivalent to the exclusive-or between corresponding bits of the two
2671 bit vectors (hence the name of this method).
2672 Note that this method is also much more efficient than evaluating the
2674 above formula explicitly since it uses a built-in machine language
2675 instruction internally.
2676 In-place calculation is also possible, i.e., "$set3" may be identical
2678 with "$set1" or "$set2" or both.
2679 • "$vec2->Not($vec1);"
2681 "$set2->Complement($set1);"
2683 This method calculates the complement of "$set1" and stores the
2685 result in "$set2".
2686 In "big integer" arithmetic, this is equivalent to calculating the
2688 one's complement of the number stored in the bit vector "$set1" in
2689 binary representation.
2690 In-place calculation is also possible, i.e., "$set2" may be identical
2692 with "$set1".
2693 • "if ($set1->subset($set2))"
2695 Returns "true" ("1") if "$set1" is a subset of "$set2" (i.e.,
2697 completely contained in "$set2") and "false" ("0") otherwise.
2698 This means that any bit which is set ("1") in "$set1" must also be
2700 set in "$set2", but "$set2" may contain set bits which are not set in
2701 "$set1", in order for the condition of subset relationship to be true
2702 between these two sets.
2703 Note that by definition, if two sets are identical, they are also
2705 subsets (and also supersets) of each other.
2706 • "$norm = $set->Norm();"
2708 Returns the norm (number of bits which are set) of the given vector.
2710 This is equivalent to the number of elements contained in the given
2712 set.
2713 Uses a byte lookup table for calculating the number of set bits per
2715 byte, and thus needs a time for evaluation (and a number of loops)
2716 linearly proportional to the length of the given bit vector (in
2717 bytes).
2718 This should be the fastest algorithm on average.
2720 • "$norm = $set->Norm2();"
2722 Returns the norm (number of bits which are set) of the given vector.
2724 This is equivalent to the number of elements contained in the given
2726 set.
2727 This does the same as the method "Norm()" above, only with a
2729 different algorithm:
2730 This method counts the number of set and cleared bits at the same
2732 time and will stop when either of them has been exhausted, thus
2733 needing at most half as many loops per machine word as the total
2734 number of bits in a machine word - in fact it will need a number of
2735 loops equal to the minimum of the number of set bits and the number
2736 of cleared bits.
2737 This might be a faster algorithm than of the method "Norm()" above on
2739 some systems, depending on the system's architecture and the compiler
2740 and optimisation used, for bit vectors with sparse set bits and for
2741 bit vectors with sparse cleared bits (i.e., predominantly set bits).
2742 • "$norm = $set->Norm3();"
2744 Returns the norm (number of bits which are set) of the given vector.
2746 This is equivalent to the number of elements contained in the given
2748 set.
2749 This does the same as the two methods "Norm()" and "Norm2()" above,
2751 however with a different algorithm.
2752 In fact this is the implementation of the method "Norm()" used in
2754 previous versions of this module.
2755 The method needs a number of loops per machine word equal to the
2757 number of set bits in that machine word.
2758 Only for bit vectors with sparse set bits will this method be fast;
2760 it will depend on a system's architecture and compiler whether the
2761 method will be faster than any of the two methods above in such
2762 cases.
2763 On average however, this is probably the slowest method of the three.
2765 • "$min = $set->Min();"
2767 Returns the minimum of the given set, i.e., the minimum of all
2769 indices of all set bits in the given bit vector "$set".
2770 If the set is empty (no set bits), plus infinity (represented by the
2772 constant "MAX_LONG" on your system) is returned.
2773 (This constant is usually 2 ^ (n-1) - 1, where ""n"" is the number of
2775 bits of an unsigned long on your machine.)
2776 • "$max = $set->Max();"
2778 Returns the maximum of the given set, i.e., the maximum of all
2780 indices of all set bits in the given bit vector "$set".
2781 If the set is empty (no set bits), minus infinity (represented by the
2783 constant "MIN_LONG" on your system) is returned.
2784 (This constant is usually -(2 ^ (n-1) - 1) or -(2 ^ (n-1)), where
2786 ""n"" is the number of bits of an unsigned long on your machine.)
2787 • "$m3->Multiplication($r3,$c3,$m1,$r1,$c1,$m2,$r2,$c2);"
2789 This method multiplies two boolean matrices (stored as bit vectors)
2791 "$m1" and "$m2" and stores the result in matrix "$m3".
2792 The method uses the binary "xor" operation (""^"") as the boolean
2794 addition operator (""+"").
2795 An exception is raised if the product of the number of rows and
2797 columns of any of the three matrices differs from the actual size of
2798 their underlying bit vector.
2799 An exception is also raised if the numbers of rows and columns of the
2801 three matrices do not harmonize in the required manner:
2802 rows3 == rows1
2804 cols3 == cols2
2805 cols1 == rows2
2806 This method is used by the module "Math::MatrixBool".
2808 See Math::MatrixBool(3) for details.
2810 • "$m3->Product($r3,$c3,$m1,$r1,$c1,$m2,$r2,$c2);"
2812 This method multiplies two boolean matrices (stored as bit vectors)
2814 "$m1" and "$m2" and stores the result in matrix "$m3".
2815 This special method uses the binary "or" operation (""|"") as the
2817 boolean addition operator (""+"").
2818 An exception is raised if the product of the number of rows and
2820 columns of any of the three matrices differs from the actual size of
2821 their underlying bit vector.
2822 An exception is also raised if the numbers of rows and columns of the
2824 three matrices do not harmonize in the required manner:
2825 rows3 == rows1
2827 cols3 == cols2
2828 cols1 == rows2
2829 This method is used by the module "Math::MatrixBool".
2831 See Math::MatrixBool(3) for details.
2833 • "$matrix->Closure($rows,$cols);"
2835 This method calculates the reflexive transitive closure of the given
2837 boolean matrix (stored as a bit vector) using Kleene's algoritm.
2838 (See Math::Kleene(3) for a brief introduction into the theory behind
2840 Kleene's algorithm.)
2841 The reflexive transitive closure answers the question whether a path
2843 exists between any two vertices of a graph whose edges are given as a
2844 matrix:
2845 If a (directed) edge exists going from vertex "i" to vertex "j", then
2847 the element in the matrix with coordinates (i,j) is set to "1"
2848 (otherwise it remains set to "0").
2849 If the edges are undirected, the resulting matrix is symmetric, i.e.,
2851 elements (i,j) and (j,i) always contain the same value.
2852 The matrix representing the edges of the graph only answers the
2854 question whether an EDGE exists between any two vertices of the graph
2855 or not, whereas the reflexive transitive closure answers the question
2856 whether a PATH (a series of adjacent edges) exists between any two
2857 vertices of the graph!
2858 Note that the contents of the given matrix are modified by this
2860 method, so make a copy of the initial matrix in time if you are going
2861 to need it again later.
2862 An exception is raised if the given matrix is not quadratic, i.e., if
2864 the number of rows and columns of the given matrix is not identical.
2865 An exception is also raised if the product of the number of rows and
2867 columns of the given matrix differs from the actual size of its
2868 underlying bit vector.
2869 This method is used by the module "Math::MatrixBool".
2871 See Math::MatrixBool(3) for details.
2873 • "$matrix2->Transpose($rows2,$cols2,$matrix1,$rows1,$cols1);"
2875 This method calculates the transpose of a boolean matrix "$matrix1"
2877 (stored as a bit vector) and stores the result in matrix "$matrix2".
2878 The transpose of a boolean matrix, representing the edges of a graph,
2880 can be used for finding the strongly connected components of that
2881 graph.
2882 An exception is raised if the product of the number of rows and
2884 columns of any of the two matrices differs from the actual size of
2885 its underlying bit vector.
2886 An exception is also raised if the following conditions are not met:
2888 rows2 == cols1
2890 cols2 == rows1
2891 Note that in-place processing ("$matrix1" and "$matrix2" are
2893 identical) is only possible if the matrix is quadratic. Otherwise, a
2894 fatal "matrix is not quadratic" error will occur.
2895 This method is used by the module "Math::MatrixBool".
2897 See Math::MatrixBool(3) for details.
2899
2901 Bit::Vector::Overload(3), Bit::Vector::String(3), Storable(3).
2902 Set::IntRange(3), Math::MatrixBool(3), Math::MatrixReal(3),
2904 DFA::Kleene(3), Math::Kleene(3), Graph::Kruskal(3).
2905
2907 This man page documents "Bit::Vector" version 7.4.
2908
2910 Steffen Beyer
2911 mailto:STBEY@cpan.org
2912 http://www.engelschall.com/u/sb/download/
2913
2915 Copyright (c) 1995 - 2013 by Steffen Beyer. All rights reserved.
2916
2918 This package is free software; you can redistribute it and/or modify it
2919 under the same terms as Perl itself, i.e., under the terms of the
2920 "Artistic License" or the "GNU General Public License".
2921 The C library at the core of this Perl module can additionally be
2923 redistributed and/or modified under the terms of the "GNU Library
2924 General Public License".
2925 Please refer to the files "Artistic.txt", "GNU_GPL.txt" and
2927 "GNU_LGPL.txt" in this distribution for details!
2928
2930 This package is distributed in the hope that it will be useful, but
2931 WITHOUT ANY WARRANTY; without even the implied warranty of
2932 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
2933 See the "GNU General Public License" for more details.
2935perl v5.36.0 2023-01-20 Vector(3)