The Algorithms// Original Author: Christian Bender
// Class: BitArray
//
// implements IComparable, ICloneable, IEnumerator, IEnumerable
//
// This class implements a bit-array and provides some
// useful functions/operations to deal with this type of
// data structure. You see a overview about the functionality, below.
//
//
// Overview
//
// Constructor (N : int)
// The constructor receives a length (N) of the to create bit-field.
//
// Constructor (sequence : string)
// setups the array with the input sequence.
// assumes: the sequence may only be allowed contains onese or zeros.
//
// Constructor (bits : bool[] )
// setups the bit-field with the input array.
//
// Compile(sequence : string)
// compiles a string sequence of 0's and 1's in the inner structure.
// assumes: the sequence may only be allowed contains onese or zeros.
//
// Compile (number : int)
// compiles a positive integer number in the inner data structure.
//
// Compile (number : long)
// compiles a positive long integer number in the inner data structure.
//
// ToString ()
// returns a string representation of the inner structure.
// The returned string is a sequence of 0's and 1's.
//
// Length : int
// Is a property that returns the length of the bit-field.
//
// Indexer : bool
// indexer for selecting the individual bits of the bit array.
//
// NumberOfOneBits() : int
// returns the number of One-bits.
//
// NumberOfZeroBits() : int
// returns the number of Zero-Bits.
//
// EvenParity() : bool
// returns true if parity is even, otherwise false.
//
// OddParity() : bool
// returns true if parity is odd, otherwise false.
//
// ToInt64() : long
// returns a long integer representation of the bit-array.
// assumes: the bit-array length must been smaller or equal to 64 bit.
//
// ToInt32() : int
// returns a integer representation of the bit-array.
// assumes: the bit-array length must been smaller or equal to 32 bit.
//
// ResetField() : void
// sets all bits on false.
//
// SetAll(flag : bool) : void
// sets all bits on the value of the flag.
//
// GetHashCode() : int
// returns hash-code (ToInt32())
//
// Equals (other : Object) : bool
// returns true if there inputs are equal otherwise false.
// assumes: the input bit-arrays must have same length.
//
// CompareTo (other : Object) : int (interface IComparable)
// output: 0 - if the bit-arrays a equal.
// -1 - if this bit-array is smaller.
// 1 - if this bit-array is greater.
// assumes: bit-array lentgh must been smaller or equal to 64 bit
//
// Clone () : object
// returns a copy of this bit-array
//
// Current : object
// returns the current selected bit.
//
// MoveNext() : bool
// purpose: increases the position of the enumerator
// returns true if 'position' successful increased otherwise false.
//
// Reset() : void
// resets the position of the enumerator.
//
// GetEnumerator() : IEnumerator
// returns a enumerator for this BitArray-object.
//
// Operations:
//
// & bitwise AND
// | bitwise OR
// ~ bitwise NOT
// >> bitwise shift right
// >> bitwise shift left
// ^ bitwise XOR
//
// Each operation (above) returns a new BitArray-object.
//
// == equal operator. : bool
// returns true if there inputs are equal otherwise false.
// assumes: the input bit-arrays must have same length.
//
// != not-equal operator : bool
// returns true if there inputs aren't equal otherwise false.
// assumes: the input bit-arrays must have same length.
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DataStructures
{
/// <summary>
/// This class implements a bit-array and provides some
/// useful functions/operations to deal with this type of
/// data structure.
/// </summary>
public sealed class BitArray : ICloneable, IEnumerator<bool>, IEnumerable<bool>
{
private readonly bool[] field; // the actual bit-field
private int position = -1; // position for enumerator
/// <summary>
/// Initializes a new instance of the <see cref="BitArray" /> class.
/// setups the array with false-values.
/// </summary>
/// <param name="n">length of the array.</param>
public BitArray(int n)
{
if (n < 1)
{
field = new bool[0];
}
field = new bool[n];
}
/// <summary>
/// Initializes a new instance of the <see cref="BitArray" /> class.
/// Setups the array with the input sequence.
/// purpose: Setups the array with the input sequence.
/// assumes: sequence must been greater or equal to 1.
/// the sequence may only contain ones or zeros.
/// </summary>
/// <param name="sequence">A string sequence of 0's and 1's.</param>
public BitArray(string sequence)
{
// precondition I
if (sequence.Length <= 0)
{
throw new ArgumentException("Sequence must been greater than or equal to 1");
}
// precondition II
ThrowIfSequenceIsInvalid(sequence);
field = new bool[sequence.Length];
Compile(sequence);
}
/// <summary>
/// Initializes a new instance of the <see cref="BitArray" /> class.
/// Setups the bit-array with the input array.
/// </summary>
/// <param name="bits">A boolean array of bits.</param>
public BitArray(bool[] bits) => field = bits;
/// <summary>
/// Gets the length of the current bit array.
/// </summary>
private int Length => field.Length;
/// <summary>
/// Gets element given an offset.
/// </summary>
/// <param name="offset">Position.</param>
/// <returns>Element on array.</returns>
public bool this[int offset]
{
get => field[offset];
private set => field[offset] = value;
}
/// <summary>
/// Returns a copy of the current bit-array.
/// </summary>
/// <returns>Bit-array clone.</returns>
public object Clone()
{
var theClone = new BitArray(Length);
for (var i = 0; i < Length; i++)
{
theClone[i] = field[i];
}
return theClone;
}
/// <summary>
/// Gets a enumerator for this BitArray-Object.
/// </summary>
/// <returns>Returns a enumerator for this BitArray-Object.</returns>
public IEnumerator<bool> GetEnumerator() => this;
/// <summary>
/// Gets a enumerator for this BitArray-Object.
/// </summary>
/// <returns>Returns a enumerator for this BitArray-Object.</returns>
IEnumerator IEnumerable.GetEnumerator() => this;
/// <summary>
/// Gets a value indicating whether the current bit of the array is set.
/// </summary>
public bool Current => field[position];
/// <summary>
/// Gets a value indicating whether the current bit of the array is set.
/// </summary>
object IEnumerator.Current => field[position];
/// <summary>
/// MoveNext (for interface IEnumerator).
/// </summary>
/// <returns>Returns True if 'position' successful increased; False otherwise.</returns>
public bool MoveNext()
{
if (position + 1 >= field.Length)
{
return false;
}
position++;
return true;
}
/// <summary>
/// Resets the position of the enumerator.
/// Reset (for interface IEnumerator).
/// </summary>
public void Reset() => position = -1;
/// <summary>
/// Disposes object, nothing to dispose here though.
/// </summary>
public void Dispose()
{
// Done
}
/// <summary>
/// Returns a bit-array that represents the bit by bit AND (&).
/// Assumes arrays have the same length.
/// </summary>
/// <param name="one">First bit-array.</param>
/// <param name="two">Second bit-array.</param>
/// <returns>bit-array.</returns>
public static BitArray operator &(BitArray one, BitArray two)
{
var sequence1 = one.ToString();
var sequence2 = two.ToString();
var result = new StringBuilder();
var tmp = new StringBuilder();
// for scaling of same length.
if (one.Length != two.Length)
{
int difference;
if (one.Length > two.Length)
{
// one is greater
difference = one.Length - two.Length;
// fills up with 0's
for (var i = 0; i < difference; i++)
{
tmp.Append('0');
}
tmp.Append(two);
sequence2 = tmp.ToString();
}
else
{
// two is greater
difference = two.Length - one.Length;
// fills up with 0's
for (var i = 0; i < difference; i++)
{
tmp.Append('0');
}
tmp.Append(one);
sequence1 = tmp.ToString();
}
} // end scaling
var len = one.Length > two.Length ? one.Length : two.Length;
var ans = new BitArray(len);
for (var i = 0; i < one.Length; i++)
{
result.Append(sequence1[i].Equals('1') && sequence2[i].Equals('1') ? '1' : '0');
}
ans.Compile(result.ToString().Trim());
return ans;
}
/// <summary>
/// Returns a bit-array that represents the bit by bit OR.
/// Assumes arrays have the same length.
/// </summary>
/// <param name="one">First bit-array.</param>
/// <param name="two">Second bit-array.</param>
/// <returns>bit-array that represents the bit by bit OR.</returns>
public static BitArray operator |(BitArray one, BitArray two)
{
var sequence1 = one.ToString();
var sequence2 = two.ToString();
var result = string.Empty;
var tmp = string.Empty;
// for scaling of same length.
if (one.Length != two.Length)
{
int difference;
if (one.Length > two.Length)
{
// one is greater
difference = one.Length - two.Length;
// fills up with 0's
for (var i = 0; i < difference; i++)
{
tmp += '0';
}
tmp += two.ToString();
sequence2 = tmp;
}
else
{
// two is greater
difference = two.Length - one.Length;
// fills up with 0's
for (var i = 0; i < difference; i++)
{
tmp += '0';
}
tmp += one.ToString();
sequence1 = tmp;
}
} // end scaling
var len = one.Length > two.Length ? one.Length : two.Length;
var ans = new BitArray(len);
for (var i = 0; i < len; i++)
{
result += sequence1[i].Equals('0') && sequence2[i].Equals('0') ? '0' : '1';
}
result = result.Trim();
ans.Compile(result);
return ans;
}
/// <summary>
/// Returns a bit-array that represents the operator ~ (NOT).
/// Assumes arrays have the same length.
/// </summary>
/// <param name="one">Bit-array.</param>
/// <returns>bitwise not.</returns>
public static BitArray operator ~(BitArray one)
{
var ans = new BitArray(one.Length);
var sequence = one.ToString();
var result = string.Empty;
foreach (var ch in sequence)
{
if (ch == '1')
{
result += '0';
}
else
{
result += '1';
}
}
result = result.Trim();
ans.Compile(result);
return ans;
}
/// <summary>
/// Returns a bit-array that represents bitwise shift left (>>).
/// Assumes arrays have the same length.
/// </summary>
/// <param name="other">Bit-array.</param>
/// <param name="n">Number of bits.</param>
/// <returns>Bitwise shifted BitArray.</returns>
public static BitArray operator <<(BitArray other, int n)
{
var ans = new BitArray(other.Length + n);
// actual shifting process
for (var i = 0; i < other.Length; i++)
{
ans[i] = other[i];
}
return ans;
}
/// <summary>
/// Returns a bit-array that represents the bit by bit XOR.
/// Assumes arrays have the same length.
/// </summary>
/// <param name="one">First bit-array.</param>
/// <param name="two">Second bit-array.</param>
/// <returns>bit-array.</returns>
public static BitArray operator ^(BitArray one, BitArray two)
{
var sequence1 = one.ToString();
var sequence2 = two.ToString();
var tmp = string.Empty;
// for scaling of same length.
if (one.Length != two.Length)
{
int difference;
if (one.Length > two.Length)
{
// one is greater
difference = one.Length - two.Length;
// fills up with 0's
for (var i = 0; i < difference; i++)
{
tmp += '0';
}
tmp += two.ToString();
sequence2 = tmp;
}
else
{
// two is greater
difference = two.Length - one.Length;
// fills up with 0's
for (var i = 0; i < difference; i++)
{
tmp += '0';
}
tmp += one.ToString();
sequence1 = tmp;
}
} // end scaling
var len = one.Length > two.Length ? one.Length : two.Length;
var ans = new BitArray(len);
var sb = new StringBuilder();
for (var i = 0; i < len; i++)
{
_ = sb.Append(sequence1[i] == sequence2[i] ? '0' : '1');
}
var result = sb.ToString().Trim();
ans.Compile(result);
return ans;
}
/// <summary>
/// Returns a bit-array that represents bitwise shift right (>>).
/// Assumes arrays have the same length.
/// </summary>
/// <param name="other">Bit-array.</param>
/// <param name="n">Number of bits.</param>
/// <returns>Bitwise shifted BitArray.</returns>
public static BitArray operator >>(BitArray other, int n)
{
var ans = new BitArray(other.Length - n);
// actual shifting process.
for (var i = 0; i < other.Length - n; i++)
{
ans[i] = other[i];
}
return ans;
}
/// <summary>
/// Checks if both arrays are == (equal).
/// The input assumes arrays have the same length.
/// </summary>
/// <param name="one">First bit-array.</param>
/// <param name="two">Second bit-array.</param>
/// <returns>Returns True if there inputs are equal; False otherwise.</returns>
public static bool operator ==(BitArray one, BitArray two)
{
if (ReferenceEquals(one, two))
{
return true;
}
if (one.Length != two.Length)
{
return false;
}
var status = true;
for (var i = 0; i < one.Length; i++)
{
if (one[i] != two[i])
{
status = false;
break;
}
}
return status;
}
/// <summary>
/// Checks if both arrays are != (not-equal).
/// The input assumes arrays have the same length.
/// </summary>
/// <param name="one">First bit-array.</param>
/// <param name="two">Second bit-array.</param>
/// <returns>Returns True if there inputs aren't equal; False otherwise.</returns>
public static bool operator !=(BitArray one, BitArray two) => !(one == two);
/// <summary>
/// Compiles the binary sequence into the inner data structure.
/// The sequence must have the same length, as the bit-array.
/// The sequence may only be allowed contains ones or zeros.
/// </summary>
/// <param name="sequence">A string sequence of 0's and 1's.</param>
public void Compile(string sequence)
{
// precondition I
if (sequence.Length > field.Length)
{
throw new ArgumentException($"{nameof(sequence)} must be not longer than the bit array length");
}
// precondition II
ThrowIfSequenceIsInvalid(sequence);
// for appropriate scaling
var tmp = string.Empty;
if (sequence.Length < field.Length)
{
var difference = field.Length - sequence.Length;
for (var i = 0; i < difference; i++)
{
tmp += '0';
}
tmp += sequence;
sequence = tmp;
}
// actual compile procedure.
for (var i = 0; i < sequence.Length; i++)
{
field[i] = sequence[i] == '1';
}
}
/// <summary>
/// Compiles integer number into the inner data structure.
/// Assumes: the number must have the same bit length.
/// </summary>
/// <param name="number">A positive integer number.</param>
public void Compile(int number)
{
var tmp = string.Empty;
// precondition I
if (number <= 0)
{
throw new ArgumentException($"{nameof(number)} must be positive");
}
// converts to binary representation
var binaryNumber = Convert.ToString(number, 2);
// precondition II
if (binaryNumber.Length > field.Length)
{
throw new ArgumentException("Provided number is too big");
}
// for appropriate scaling
if (binaryNumber.Length < field.Length)
{
var difference = field.Length - binaryNumber.Length;
for (var i = 0; i < difference; i++)
{
tmp += '0';
}
tmp += binaryNumber;
binaryNumber = tmp;
}
// actual compile procedure.
for (var i = 0; i < binaryNumber.Length; i++)
{
field[i] = binaryNumber[i] == '1';
}
}
/// <summary>
/// Compiles integer number into the inner data structure.
/// The number must have the same bit length.
/// </summary>
/// <param name="number">A positive long integer number.</param>
public void Compile(long number)
{
var tmp = string.Empty;
// precondition I
if (number <= 0)
{
throw new ArgumentException($"{nameof(number)} must be positive");
}
// converts to binary representation
var binaryNumber = Convert.ToString(number, 2);
// precondition II
if (binaryNumber.Length > field.Length)
{
throw new ArgumentException("Provided number is too big");
}
// for appropriate scaling
if (binaryNumber.Length < field.Length)
{
var difference = field.Length - binaryNumber.Length;
for (var i = 0; i < difference; i++)
{
tmp += '0';
}
tmp += binaryNumber;
binaryNumber = tmp;
}
// actual compile procedure.
for (var i = 0; i < binaryNumber.Length; i++)
{
field[i] = binaryNumber[i] == '1';
}
}
/// <summary>
/// Is the opposit of the Compile(...) method.
/// </summary>
/// <returns>Returns a string representation of the inner data structure.</returns>
public override string ToString()
{
// creates return-string
return field.Aggregate(string.Empty, (current, t) => current + (t ? "1" : "0"));
}
/// <summary>
/// Gets the number of one-bits in the field.
/// </summary>
/// <returns>quantity of bits in current bit-array.</returns>
public int NumberOfOneBits()
{
// counting one-bits.
return field.Count(bit => bit);
}
/// <summary>
/// Gets the number of zero-bits in the field.
/// </summary>
/// <returns>quantity of bits.</returns>
public int NumberOfZeroBits()
{
// counting zero-bits
return field.Count(bit => !bit);
}
/// <summary>
/// To check for even parity.
/// </summary>
/// <returns>Returns True if parity is even; False otherwise.</returns>
public bool EvenParity() => NumberOfOneBits() % 2 == 0;
/// <summary>
/// To check for odd parity.
/// </summary>
/// <returns>Returns True if parity is odd; False otherwise.</returns>
public bool OddParity() => NumberOfOneBits() % 2 != 0;
/// <summary>
/// Returns a long integer representation of the bit-array.
/// Assumes the bit-array length must been smaller or equal to 64 bit.
/// </summary>
/// <returns>Long integer array.</returns>
public long ToInt64()
{
// Precondition
if (field.Length > 64)
{
throw new InvalidOperationException("Value is too big to fit into Int64");
}
var sequence = ToString();
return Convert.ToInt64(sequence, 2);
}
/// <summary>
/// Returns a long integer representation of the bit-array.
/// Assumes the bit-array length must been smaller or equal to 32 bit.
/// </summary>
/// <returns>integer array.</returns>
public int ToInt32()
{
// Precondition
if (field.Length > 32)
{
throw new InvalidOperationException("Value is too big to fit into Int32");
}
var sequence = ToString();
return Convert.ToInt32(sequence, 2);
}
/// <summary>
/// Sets all bits on false.
/// </summary>
public void ResetField()
{
for (var i = 0; i < field.Length; i++)
{
field[i] = false;
}
}
/// <summary>
/// Sets all bits on the value of the flag.
/// </summary>
/// <param name="flag">Bollean flag (false-true).</param>
public void SetAll(bool flag)
{
for (var i = 0; i < field.Length; i++)
{
field[i] = flag;
}
}
/// <summary>
/// Checks if bit-array are equal.
/// Assumes the input bit-arrays must have same length.
/// </summary>
/// <param name="obj">Bit-array object.</param>
/// <returns>Returns true if there inputs are equal otherwise false.</returns>
public override bool Equals(object? obj)
{
if (obj is null)
{
return false;
}
var otherBitArray = (BitArray)obj;
if (Length != otherBitArray.Length)
{
return false;
}
for (var i = 0; i < Length; i++)
{
if (field[i] != otherBitArray[i])
{
return false;
}
}
return true;
}
/// <summary>
/// Gets has-code of bit-array.
/// Assumes bit-array length must been smaller or equal to 32.
/// </summary>
/// <returns>hash-code for this BitArray instance.</returns>
public override int GetHashCode() => ToInt32();
private static void ThrowIfSequenceIsInvalid(string sequence)
{
if (!Match(sequence))
{
throw new ArgumentException("The sequence may only contain ones or zeros");
}
}
/// <summary>
/// Utility method foir checking a given sequence contains only zeros and ones.
/// This method will used in Constructor (sequence : string) and Compile(sequence : string).
/// </summary>
/// <param name="sequence">String sequence.</param>
/// <returns>returns True if sequence contains only zeros and ones; False otherwise.</returns>
private static bool Match(string sequence) => sequence.All(ch => ch == '0' || ch == '1');
}
}
Bit Array
c
C
1
A
