bitarray_example.C File Reference

BitArray in Aleph-w (bit operations, set algebra, sieve demo, and memory/performance notes). More...

#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <tclap/CmdLine.h>
#include <bitArray.H>
#include <htlist.H>
#include <ahFunctional.H>

Include dependency graph for bitarray_example.C:

Go to the source code of this file.

Functions
void	print_section (const string &title)
void	print_subsection (const string &title)
void	print_bits (const string &label, const BitArray &ba, size_t max_show=64)
void	demo_basic_operations ()
void	demo_bitwise_operations ()
void	demo_set_operations ()
void	demo_sieve_of_eratosthenes (size_t n)
void	demo_subset_enumeration ()
void	demo_simple_bloom_filter ()
void	demo_performance ()
int	main (int argc, char *argv[])

Detailed Description

BitArray in Aleph-w (bit operations, set algebra, sieve demo, and memory/performance notes).

Overview

This example demonstrates Aleph-w's BitArray: a compact bitset structure supporting fast bitwise operations and typical set algebra (union/intersection, etc.).

The program runs a suite of demos covering:

• basic bit manipulation
• bitwise operators and set-style operations
• a Sieve of Eratosthenes prime demo (parameterized by CLI)
• simple Bloom-filter-like usage
• a small memory savings comparison

Data model used by this example

• Container: BitArray from bitArray.H
• Index domain: [0, n) where n is the bitarray size

Usage / CLI

This example uses TCLAP. Options:

• --sieve-size / -n <size_t>: size used for the Sieve of Eratosthenes demo (default: 100).
• --help: show help.

# Run all demonstrations
./bitarray_example
 
# Configure sieve size
./bitarray_example --sieve-size 1000
./bitarray_example -n 1000
 
# Show help
./bitarray_example --help

Complexity

Let N be the number of bits.

• single-bit read/write: O(1)
• bitwise operations (AND/OR/XOR/NOT, shifts): O(N)

(In practice, bulk operations run on machine words, so the constant factors are low.)

Pitfalls and edge cases

• Bulk operations scale linearly with the number of words; large bitarrays are fast but not constant time.
• The sieve size affects runtime and output volume.

References / see also

• bitArray.H (BitArray implementation)
• bloom_filter_example.C (Bloom filter using BitArray)

Author

Leandro Rabindranath León

Date

2024

Copyright

GNU General Public License

Definition in file bitarray_example.C.

Function Documentation

demo_basic_operations()

void demo_basic_operations

(

)

Definition at line 116 of file bitarray_example.C.

References Aleph::maps(), print_bits(), print_section(), print_subsection(), and Aleph::HTList::size().

Referenced by main().

demo_bitwise_operations()

void demo_bitwise_operations

(

)

Definition at line 173 of file bitarray_example.C.

References Aleph::maps(), print_bits(), print_section(), print_subsection(), Aleph::BitArray::read_bit(), Aleph::BitArray::size(), and Aleph::BitArray::write_bit().

Referenced by main().

demo_performance()

void demo_performance

(

)

Definition at line 467 of file bitarray_example.C.

References Aleph::DynList< T >::append(), FunctionalMethods< Container, T >::for_each(), Aleph::maps(), and print_section().

Referenced by main().

demo_set_operations()

void demo_set_operations

(

)

Definition at line 234 of file bitarray_example.C.

References Aleph::maps(), print_section(), print_subsection(), and Aleph::HTList::size().

Referenced by main().

demo_sieve_of_eratosthenes()

void demo_sieve_of_eratosthenes

(

size_t

n

)

Definition at line 308 of file bitarray_example.C.

References Aleph::DynList< T >::append(), FunctionalMethods< Container, T >::for_each(), Aleph::maps(), primes, print_section(), Aleph::HTList::size(), and sqrt().

Referenced by main().

demo_simple_bloom_filter()

void demo_simple_bloom_filter

(

)

Definition at line 401 of file bitarray_example.C.

References Aleph::DynList< T >::append(), FunctionalMethods< Container, T >::for_each(), h, Aleph::maps(), print_bits(), and print_section().

Referenced by main().

demo_subset_enumeration()

void demo_subset_enumeration

(

)

Definition at line 362 of file bitarray_example.C.

References Aleph::DynList< T >::append(), FunctionalMethods< Container, T >::for_each(), Aleph::maps(), and print_section().

Referenced by main().

main()

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 504 of file bitarray_example.C.

References demo_basic_operations(), demo_bitwise_operations(), demo_performance(), demo_set_operations(), demo_sieve_of_eratosthenes(), demo_simple_bloom_filter(), demo_subset_enumeration(), and Aleph::maps().

print_bits()

void print_bits	(	const string &	label,
		const BitArray &	ba,
		size_t	max_show = 64
	)

Definition at line 101 of file bitarray_example.C.

References Aleph::maps(), min(), and Aleph::HTList::size().

Referenced by demo_basic_operations(), demo_bitwise_operations(), and demo_simple_bloom_filter().

print_section()

void print_section

(

const string &

title

)

Definition at line 89 of file bitarray_example.C.

References Aleph::maps().

Referenced by demo_basic_operations(), demo_bitwise_operations(), demo_performance(), demo_set_operations(), demo_sieve_of_eratosthenes(), demo_simple_bloom_filter(), and demo_subset_enumeration().

print_subsection()

void print_subsection

(

const string &

title

)

Definition at line 96 of file bitarray_example.C.

References Aleph::maps().

Referenced by demo_basic_operations(), demo_bitwise_operations(), and demo_set_operations().