BitsArray Type

bits is a sequence of BlockInt (uint64/uint32/uint16/uint8, depending on CPU)

len is the number of bits

BitsArray is saved in BlockInt blocks. For example, on a 64-bit machine, memory layout of BitsArray.bits is

Bits are left aligned, so when (len mod 64 != 0), the last (64 - len mod 64) bits memory is wasted.

You may change the underlying BlockInt definition (in utils) to force define BlockInt to a different len, say 16-bits on a 64-bits CPU.

NOTE: Bits are left aligned, so least significant bit is at location 0. As a result, 10000110 is equal to 127 ('a'), rather than 134. Use proc reverseBits when necessary.

Imports

bitarray/utils

Types

BitsArray = ref object bits*: seq[BlockInt] len*: int: Source Edit

Procs

proc newBitsArray(len: int): BitsArray {...}{.raises: [], tags: [].}

Construct a new BitsArray with len bits. Source Edit

proc blocks(bit_arr: BitsArray): int {...}{.raises: [], tags: [].}

Get the number of blocks (BlockInt) saved. For example, a 70 bits array takes 2 blocks. Source Edit

proc `$`(bit_arr: BitsArray): string {...}{.raises: [], tags: [].}

Return the 0-1 string representation of the BitsArray. Source Edit

proc get_bit_position(loc: int): (int, int) {...}{.raises: [], tags: [].}

Given a bit location (0<=loc<=len)

return: (block location: int, location inside the block: int)

Source Edit

proc setBit(bit_arr: BitsArray; loc: int) {...}{.raises: [], tags: [].}

Set bit value at location loc to be 1.

With macros from bitops, you may use setBits to set multiple bits.

Source Edit

proc clearBit(bit_arr: BitsArray; loc: int) {...}{.raises: [], tags: [].}

Set bit value at location loc to be 0.

With macros from bitops, you may use setBits to clear multiple bits.

Source Edit

proc flipBit(bit_arr: BitsArray; loc: int) {...}{.raises: [], tags: [].}

Flip bit value at location loc.

With macros from bitops, you may use setBits to flip multiple bits.

Source Edit

proc testBit(bit_arr: BitsArray; loc: int): bool {...}{.raises: [], tags: [].}

Check whether bit value at location loc is equal to 1. Source Edit

proc countSetBits(bit_arr: BitsArray): int {...}{.raises: [], tags: [].}

Counts the set bits in integer. (also called Hamming weight.) Source Edit

proc `&`(a, b: BitsArray): BitsArray {...}{.raises: [], tags: [].}

Computes the bitwise and of a and b. Source Edit

proc `|`(a, b: BitsArray): BitsArray {...}{.raises: [], tags: [].}

Computes the bitwise or of a and b. Source Edit

proc `~`(a: BitsArray): BitsArray {...}{.raises: [], tags: [].}

Computes the bitwise not of a. Source Edit

proc `^`(a, b: BitsArray): BitsArray {...}{.raises: [], tags: [].}

Computes the bitwise xor of a and b. Source Edit

proc `[]`(a: BitsArray; loc: int): bool {...}{.raises: [], tags: [].}

Test bit value at loc. Source Edit

proc `[]`(a: BitsArray; locs: openArray[int]): BitsArray {...}{.raises: [], tags: [].}

Slice the BitsArray with the given locs. Source Edit

proc `[]`(a: BitsArray; locs: HSlice): BitsArray

Slice the BitsArray with the given locs. Source Edit

proc `[]=`(a: BitsArray; loc: int; value: bool) {...}{.raises: [], tags: [].}

Assign bit at loc to value. Source Edit

proc `[]=`(a: BitsArray; locs: openArray[int]; value: bool) {...}{.raises: [], tags: [].}

Assign bit at locs to value. Source Edit

proc `[]=`(a: BitsArray; locs: HSlice; value: bool)

Assign bit at locs to value. Source Edit

proc copy(a: BitsArray): BitsArray {...}{.raises: [], tags: [].}

Make a new copy of BitsArray (different memory locations). Source Edit

proc swap(a, b: BitsArray) {...}{.raises: [], tags: [].}

Swap a and b. Source Edit

proc setAll(a: BitsArray) {...}{.raises: [], tags: [].}

Set all bits to be 1. Source Edit

proc clearAll(a: BitsArray) {...}{.raises: [], tags: [].}

Set all bits to be 0. Source Edit

proc flipAll(a: BitsArray) {...}{.raises: [], tags: [].}

Flip all bits. Source Edit

proc sum(a: BitsArray): int {...}{.raises: [], tags: [].}

Return number of bits of value 1. Source Edit

proc nbytes(a: BitsArray): int {...}{.raises: [], tags: [].}

Return number of bytes (8 * bits) taken by the BitsArray.bits. Source Edit

proc `shl`(a: BitsArray; steps: SomeInteger): BitsArray

Return a new BitsArray, where bits are shifted left by steps.

Example:

var a = newBitsArray(70)
a.setBits(69)
var b = a.shl(69)
doAssert a.`$` == "0000000000000000000000000000000000000000000000000000000000000000000001"
doAssert b.`$` == "1000000000000000000000000000000000000000000000000000000000000000000000"

Source Edit

proc `shr`(a: BitsArray; steps: SomeInteger): BitsArray

Return a new BitsArray, where bits are shifted right by steps.

Example:

var a = newBitsArray(70)
a.setBits(0)
var b = a.shr(69)
doAssert a.`$` == "1000000000000000000000000000000000000000000000000000000000000000000000"
doAssert b.`$` == "0000000000000000000000000000000000000000000000000000000000000000000001"

Source Edit

proc firstSetBit(a: BitsArray): int {...}{.raises: [], tags: [].}

Return first location of first bit of value 1. If no bit is of value 1, -1 is returned. Source Edit

proc lastSetBit(a: BitsArray): int {...}{.raises: [], tags: [].}

Return last location of first bit of value 1. If no bit is of value 1, -1 is returned. Source Edit

proc countLeadingZeroBits(a: BitsArray): int {...}{.raises: [], tags: [].}

Return number of leading zero bits. Source Edit

proc countTrailingZeroBits(a: BitsArray): int {...}{.raises: [], tags: [].}

Return number of trailing zero bits. Source Edit

proc expand(a: BitsArray; len: int) {...}{.raises: [], tags: [].}

Expand BitsArray to be of length len. Source Edit

proc concat(a, b: BitsArray): BitsArray {...}{.raises: [], tags: [].}

Concatenate b to the right of a.

Example:

doAssert "a".toBitsArray.`$` == "10000110"
doAssert "b".toBitsArray.`$` == "01000110"
doAssert ("a".toBitsArray).concat("b".toBitsArray).`$` == "1000011001000110"

Source Edit

proc toBitsArray[T: not string](a: T): BitsArray

Convert any basic type, such as int,float,bool, to a BitsArray.

Example:

doAssert true.toBitsArray.`$` == "10000000"
doAssert int8.low.toBitsArray.`$` == "00000001"

Source Edit

proc toBitsArray(a: string): BitsArray {...}{.raises: [], tags: [].}

Convert string to its bits representation.

Example:

doAssert "a".toBitsArray.`$` == "10000110"
doAssert "b".toBitsArray.`$` == "01000110"
doAssert "ab".toBitsArray.`$` == "1000011001000110"

Source Edit

proc binToBitsArray(a: string): BitsArray {...}{.raises: [], tags: [].}

Convert a binary representation string to BitsArray '0' for low bit, '1' and other non-'0' for high bit

Example:

doAssert "010101".binToBitsArray.`$` == "010101"
doAssert "01010a".binToBitsArray.`$` == "010101"

Source Edit

proc reverseBits(a: BitsArray): BitsArray {...}{.raises: [], tags: [].}

Return the bit reversal of a.

Example:

doAssert 7.uint16.toBitsArray.`$` == "1110000000000000"
doAssert 7.uint16.toBitsArray.reverseBits.`$` == "0000000000000111"

Source Edit

proc version(): string {...}{.raises: [], tags: [].}

Source Edit

Exports

BLOCK_TAILS_BITS, toBin, BLOCK_HEADS_BITS, BLOCK_LEN_POWER_2, BLOCK_LEN, BlockInt