# man > Bit::Vector

---
type: CommandReference
command: Bit::Vector
mode: perldoc
section: 3pm
source: perldoc
---

## Quick Reference
- `$v = Bit::Vector->new($bits)` — create a bit vector of `$bits` bits
- `$v->Bit_On($idx)` / `$v->Bit_Off($idx)` — set/clear a single bit
- `if ($v->bit_test($idx)) { ... }` — test a bit (also `contains`)
- `$v->to_Hex()` / `$v->from_Hex($str)` — convert to/from hex string
- `$v->increment()` — increment unsigned number, returns carry
- `$v3->add($v1, $v2, $carry)` — addition with carry
- `$v3->Or($v1, $v2)` — union of two sets
- `$v->Interval_Fill($min, $max)` — set all bits in an interval

## Name
Bit::Vector – Efficient bit vector, set of integers and "big int" math library

## Synopsis
perl
use Bit::Vector;

# Construction
$vec = Bit::Vector->new(8);
$vec = Bit::Vector->new_Hex(8, 'FF');
$vec = Bit::Vector->Concat_List(@vecs);

# Bit manipulation
$vec->Bit_On(5);
$vec->Bit_Off(3);
$bit = $vec->bit_flip(2);
if ($vec->bit_test(0)) { ... }

# Arithmetic (signed/unsigned)
$carry = $vec->increment();
$vec3->Multiply($vec1, $vec2);
$vec3->add($vec1, $vec2, 0);

# Set operations
$union->Or($set1, $set2);
$intersect->And($set1, $set2);

# Import/export
$hex = $vec->to_Hex();
$vec->from_Bin('10101100');
$vec->Block_Store($buffer);
Overloaded operators are documented in `Bit::Vector::Overload`. Extended string I/O in `Bit::Vector::String`.

## Notes
- **Boolean returns** – Method names in lower case return a boolean (0/1).
- **Unsigned parameters** – All numeric arguments are treated as unsigned; negative values become large positive numbers.
- **Bit order** – Least significant bit is index 0. Strings have the **rightmost** character as LSB; conversion methods handle internal reversal automatically.
- **Word methods** – Methods with `Word_` prefix are machine-dependent; use `Chunk_` methods for portability (chunk size ≤ 32 bits).
- **Size matching** – Most methods that involve multiple vectors require equal sizes; exceptions: `Concat`, `Copy`, `Interval_Copy`, `Interval_Substitute`.
- **Memory** – Bit vectors of length zero are allowed.

## Methods

### Creation
- `Bit::Vector->new($bits)` – Constructor; returns zeroed vector of `$bits` bits.
- `Bit::Vector->new($bits, $count)` – Returns a list of `$count` zeroed vectors.
- `$vec->Shadow()` – New empty vector of same size.
- `$vec->Clone()` – Exact duplicate.
- `$vec1->Concat($vec2)` – New vector = `$vec1` + `$vec2` (most to least significant).
- `$vec1->Concat_List($vec2, ...)` – Concatenates multiple vectors.
- `Bit::Vector->new_Hex($bits, $string)` – Vector initialized from hex.
- `Bit::Vector->new_Bin($bits, $string)` – From binary string.
- `Bit::Vector->new_Dec($bits, $string)` – From decimal string.
- `Bit::Vector->new_Enum($bits, $string)` – From enumeration (e.g., `"2,3,5-7"`).

### Size, Resize, Copy
- `$v->Size()` – Number of bits.
- `$v->Resize($bits)` – Change size; excess bits cleared/lost.
- `$v2->Copy($v1)` – Copies contents with sign extension if target larger, truncation if smaller.

### Bulk Operations
- `$v->Empty()` – Clear all bits.
- `$v->Fill()` – Set all bits.
- `$v->Flip()` – Complement all bits.
- `$v->Primes()` – Clear vector, then set bits at prime indices (Sieve of Eratosthenes).
- `$v2->Reverse($v1)` – Reverse bit order; may be in-place.

### Interval Operations
- `$v->Interval_Empty($min, $max)` – Clear interval.
- `$v->Interval_Fill($min, $max)` – Set interval.
- `$v->Interval_Flip($min, $max)` – Complement interval.
- `$v->Interval_Reverse($min, $max)` – Reverse bits within interval.
- `($min, $max) = $v->Interval_Scan_inc($start)` – Find next upward contiguous block of set bits.
- `($min, $max) = $v->Interval_Scan_dec($start)` – Same, downwards.
- `$v2->Interval_Copy($v1, $off2, $off1, $len)` – Copy a stretch of bits; sizes may differ.
- `$v2->Interval_Substitute($v1, $off2, $len2, $off1, $len1)` – Splice‑like substitution; target vector auto‑resizes.

### Bit Access
- `$v->Bit_Off($idx)` – Clear bit.
- `$v->Bit_On($idx)` – Set bit.
- `$v->bit_flip($idx)` – Toggle bit; returns new state.
- `$v->bit_test($idx)` / `$v->contains($idx)` – Return bit state (0/1).
- `$v->Bit_Copy($idx, $bit)` – Set bit to 0 or 1.
- `$v->LSB($bit)` / `$v->MSB($bit)` – Set least/most significant bit.
- `$v->lsb()` / `$v->msb()` – Return least/most significant bit.

### Shifts and Rotations
- `$carry = $v->rotate_left()` – Rotate left; LSB gets carry, MSB becomes new carry.
- `$carry = $v->rotate_right()` – Rotate right.
- `$carry = $v->shift_left($carry_in)` – Shift left; LSB from carry, MSB to carry.
- `$carry = $v->shift_right($carry_in)` – Shift right.
- `$v->Move_Left($bits)` – Shift left by `$bits`; new LSBs cleared, MSBs lost.
- `$v->Move_Right($bits)` – Shift right; new MSBs cleared.

### Insert/Delete
- `$v->Insert($offset, $bits)` – Insert `$bits` zero bits at offset; upper bits lost (no resize).
- `$v->Delete($offset, $bits)` – Remove `$bits` bits; upper bits shifted down, zero‑filled (no resize).

### Arithmetic (Unsigned/Signed)
- `$carry = $v->increment()` – Unsigned increment; carry 1 on overflow.
- `$carry = $v->decrement()` – Unsigned decrement; carry 1 on underflow.
- `$overflow = $v2->inc($v1)` – Copy and increment; returns overflow flag.
- `$overflow = $v2->dec($v1)` – Copy and decrement.
- `$carry = $v3->add($v1, $v2, $carry)` / `($carry, $overflow) = $v3->add(...)` – Addition with carry.
- `$carry = $v3->subtract($v1, $v2, $carry)` / `($carry, $overflow) = ...` – Subtraction with carry.
- `$v2->Neg($v1)` / `Negate` – Two's complement negation.
- `$v2->Abs($v1)` / `Absolute` – Absolute value.
- `$sign = $v->Sign()` – Returns 0, -1, or 1 (negative if MSB set).
- `$v3->Multiply($v1, $v2)` – Signed multiplication; result may be larger.
- `$quot->Divide($v1, $v2, $rest)` – Signed division; `$quot` and `$rest` must be distinct.
- `$gcd->GCD($va, $vb)` – Greatest common divisor (Euklid).
- `$gcd->GCD($x, $y, $va, $vb)` – Extends GCD to find Bézout coefficients.
- `$v3->Power($v1, $v2)` – Exponentiation (`$v1 ** $v2`), exponent must be positive.

### Block/Word/Chunk I/O
- `$v->Block_Store($buffer)` – Load entire vector from packed string (LSB first).
- `$buffer = $v->Block_Read()` – Export entire vector to packed string.
- `$size = $v->Word_Size()` – Number of machine words (machine‑dependent).
- `$v->Word_Store($off, $word)` – Store a machine word.
- `$word = $v->Word_Read($off)` – Read a machine word.
- `$v->Word_List_Store(@words)` – Store list of words (LSW first).
- `@words = $v->Word_List_Read()` – Read as list.
- `$v->Word_Insert($off, $count)` – Insert empty words (upper lost).
- `$v->Word_Delete($off, $count)` – Delete words (upper shifted, zero‑filled).
- `$v->Chunk_Store($chunksize, $off, $chunk)` – Store up to 32 bits (portable) at offset.
- `$chunk = $v->Chunk_Read($chunksize, $off)` – Read a chunk.
- `$v->Chunk_List_Store($chunksize, @chunks)` – Fill vector from list of chunks.
- `@chunks = $v->Chunk_List_Read($chunksize)` – Read vector as list of chunks.

### Index List Operations
- `$v->Index_List_Remove(@indices)` – Clear bits at given indices (accumulative).
- `$v->Index_List_Store(@indices)` – Set bits at given indices (accumulative).
- `@indices = $v->Index_List_Read()` – Return sorted indices of all set bits.

### Set Operations
- `$v3->Or($v1, $v2)` / `Union` – Union.
- `$v3->And($v1, $v2)` / `Intersection` – Intersection.
- `$v3->AndNot($v1, $v2)` / `Difference` – Set difference (`$v1 \ $v2`).
- `$v3->Xor($v1, $v2)` / `ExclusiveOr` – Symmetric difference.
- `$v2->Not($v1)` / `Complement` – Ones' complement.
- `$set1->subset($set2)` – True if `$set1` is subset of `$set2`.
- `$norm = $set->Norm()` / `Norm2` / `Norm3` – Number of set bits (three algorithms).
- `$min = $set->Min()` – Smallest set index (or `MAX_LONG` if empty).
- `$max = $set->Max()` – Largest set index (or `MIN_LONG` if empty).

### Matrix Operations
- `$m3->Multiplication($r3,$c3, $m1,$r1,$c1, $m2,$r2,$c2)` – Boolean matrix multiplication with XOR as addition.
- `$m3->Product(...)` – Boolean matrix multiplication with OR as addition.
- `$matrix->Closure($rows, $cols)` – Reflexive transitive closure (Kleene's algorithm); modifies matrix.
- `$m2->Transpose($r2,$c2, $m1,$r1,$c1)` – Transpose a boolean matrix.

### Predicates
- `$v->is_empty()` – All bits cleared (also true for length 0).
- `$v->is_full()` – All bits set (false for length 0).
- `$v1->equal($v2)` – True if identical.
- `$v1->Lexicompare($v2)` – Unsigned comparison; returns -1, 0, 1.
- `$v1->Compare($v2)` – Signed comparison; returns -1, 0, 1.

### String Conversion
- `$str = $v->to_Hex()` – Hex string (least significant digit right).
- `$v->from_Hex($str)` – Parse hex; ignores extra characters.
- `$str = $v->to_Bin()` – Binary string (LSB right).
- `$v->from_Bin($str)` – Parse binary.
- `$str = $v->to_Dec()` – Signed decimal string (slow).
- `$v->from_Dec($str)` – Parse decimal (signed); raises errors on overflow/syntax.
- `$str = $v->to_Enum()` – Enumeration like `"2,3,5-7,11"`.
- `$v->from_Enum($str)` – Parse enumeration; clears vector first.

## Examples
perl
# Sieve of Eratosthenes
$limit = 1000;
$primes = Bit::Vector->new($limit+1);
$primes->Primes();
@prime_list = $primes->Index_List_Read();
print join(',', @prime_list), "\n";

# Set operations
$set1 = Bit::Vector->new(64);
$set2 = Bit::Vector->new(64);
$set1->Index_List_Store(1,3,5,7);
$set2->Index_List_Store(3,5,8,9);
$union = $set1->Clone()->Or($set1, $set2);
$intersection = $set1->Clone()->And($set1, $set2);
print "Union: ", $union->to_Enum(), "\n";
print "Intersection: ", $intersection->to_Enum(), "\n";

# Large integer arithmetic (signed)
$a = Bit::Vector->new(128);
$b = Bit::Vector->new(128);
$c = Bit::Vector->new(128);
$a->from_Dec("-12345678901234567890");
$b->from_Dec("98765432109876543210");
$c->add($a, $b, 0);
print "Sum: ", $c->to_Dec(), "\n";

# Block I/O (save/load)
$vec = Bit::Vector->new(256);
$vec->Interval_Fill(50,199);
$data = $vec->Block_Read();
# ... write $data to a file, later read back ...
$vec2 = Bit::Vector->new(256);
$vec2->Block_Store($data);
print "Equal? ", $vec->equal($vec2), "\n";
## See Also
- [Bit::Vector::Overload(3)](http://localhost/phpMan.php/man/Overload/3/markdown) – Overloaded operators
- [Bit::Vector::String(3)](http://localhost/phpMan.php/man/String/3/markdown) – Extended string I/O
- [Storable(3)](http://localhost/phpMan.php/man/Storable/3/markdown) – Serialization
- [Set::IntRange(3)](http://localhost/phpMan.php/man/IntRange/3/markdown)
- [Math::MatrixBool(3)](http://localhost/phpMan.php/man/MatrixBool/3/markdown)
- [Math::MatrixReal(3)](http://localhost/phpMan.php/man/MatrixReal/3/markdown)
- [DFA::Kleene(3)](http://localhost/phpMan.php/man/Kleene/3/markdown)
- [Math::Kleene(3)](http://localhost/phpMan.php/man/Kleene/3/markdown)
- [Graph::Kruskal(3)](http://localhost/phpMan.php/man/Kruskal/3/markdown)

## Exit Codes
_Nothing documented._