- 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
|<---64 bits--->|<---64 bits--->|<---64 bits--->|...|<---64 bits--->|
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.
Procs
proc newBitsArray(len: int): BitsArray {...}{.raises: [], tags: [].}
- Construct a new BitsArray with len bits.
proc blocks(bit_arr: BitsArray): int {...}{.raises: [], tags: [].}
- Get the number of blocks (BlockInt) saved. For example, a 70 bits array takes 2 blocks.
proc `$`(bit_arr: BitsArray): string {...}{.raises: [], tags: [].}
- Return the 0-1 string representation of the BitsArray.
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)
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.
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.
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.
proc testBit(bit_arr: BitsArray; loc: int): bool {...}{.raises: [], tags: [].}
- Check whether bit value at location loc is equal to 1.
proc countSetBits(bit_arr: BitsArray): int {...}{.raises: [], tags: [].}
- Counts the set bits in integer. (also called Hamming weight.)
proc `&`(a, b: BitsArray): BitsArray {...}{.raises: [], tags: [].}
- Computes the bitwise and of a and b.
proc `|`(a, b: BitsArray): BitsArray {...}{.raises: [], tags: [].}
- Computes the bitwise or of a and b.
proc `~`(a: BitsArray): BitsArray {...}{.raises: [], tags: [].}
- Computes the bitwise not of a.
proc `^`(a, b: BitsArray): BitsArray {...}{.raises: [], tags: [].}
- Computes the bitwise xor of a and b.
proc `[]`(a: BitsArray; loc: int): bool {...}{.raises: [], tags: [].}
- Test bit value at loc.
proc `[]`(a: BitsArray; locs: openArray[int]): BitsArray {...}{.raises: [], tags: [].}
- Slice the BitsArray with the given locs.
proc `[]`(a: BitsArray; locs: HSlice): BitsArray
- Slice the BitsArray with the given locs.
proc `[]=`(a: BitsArray; loc: int; value: bool) {...}{.raises: [], tags: [].}
- Assign bit at loc to value.
proc `[]=`(a: BitsArray; locs: openArray[int]; value: bool) {...}{.raises: [], tags: [].}
- Assign bit at locs to value.
proc `[]=`(a: BitsArray; locs: HSlice; value: bool)
- Assign bit at locs to value.
proc copy(a: BitsArray): BitsArray {...}{.raises: [], tags: [].}
- Make a new copy of BitsArray (different memory locations).
proc swap(a, b: BitsArray) {...}{.raises: [], tags: [].}
- Swap a and b.
proc setAll(a: BitsArray) {...}{.raises: [], tags: [].}
- Set all bits to be 1.
proc clearAll(a: BitsArray) {...}{.raises: [], tags: [].}
- Set all bits to be 0.
proc flipAll(a: BitsArray) {...}{.raises: [], tags: [].}
- Flip all bits.
proc sum(a: BitsArray): int {...}{.raises: [], tags: [].}
- Return number of bits of value 1.
proc nbytes(a: BitsArray): int {...}{.raises: [], tags: [].}
- Return number of bytes (8 * bits) taken by the BitsArray.bits.
proc `shl`(a: BitsArray; steps: SomeInteger): BitsArray
-
Return a new BitsArray, where bits are shifted left by steps.
Examples:
var a = newBitsArray(70) a.setBits(69) var b = a.shl(69) doAssert a.`$` == "0000000000000000000000000000000000000000000000000000000000000000000001" doAssert b.`$` == "1000000000000000000000000000000000000000000000000000000000000000000000"
proc `shr`(a: BitsArray; steps: SomeInteger): BitsArray
-
Return a new BitsArray, where bits are shifted right by steps.
Examples:
var a = newBitsArray(70) a.setBits(0) var b = a.shr(69) doAssert a.`$` == "1000000000000000000000000000000000000000000000000000000000000000000000" doAssert b.`$` == "0000000000000000000000000000000000000000000000000000000000000000000001"
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.
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.
proc countLeadingZeroBits(a: BitsArray): int {...}{.raises: [], tags: [].}
- Return number of leading zero bits.
proc countTrailingZeroBits(a: BitsArray): int {...}{.raises: [], tags: [].}
- Return number of trailing zero bits.
proc expand(a: BitsArray; len: int) {...}{.raises: [], tags: [].}
- Expand BitsArray to be of length len.
proc concat(a, b: BitsArray): BitsArray {...}{.raises: [], tags: [].}
-
Concatenate b to the right of a.
Examples:
doAssert "a".toBitsArray.`$` == "10000110" doAssert "b".toBitsArray.`$` == "01000110" doAssert ("a".toBitsArray).concat("b".toBitsArray).`$` == "1000011001000110"
proc toBitsArray[T: not string](a: T): BitsArray
-
Convert any basic type, such as int,float,bool, to a BitsArray.
Examples:
doAssert true.toBitsArray.`$` == "10000000" doAssert int8.low.toBitsArray.`$` == "00000001"
proc toBitsArray(a: string): BitsArray {...}{.raises: [], tags: [].}
-
Convert string to its bits representation.
Examples:
doAssert "a".toBitsArray.`$` == "10000110" doAssert "b".toBitsArray.`$` == "01000110" doAssert "ab".toBitsArray.`$` == "1000011001000110"
proc binToBitsArray(a: string): BitsArray {...}{.raises: [], tags: [].}
-
Convert a binary representation string to BitsArray
Examples:
doAssert "010101".binToBitsArray.`$` == "010101"
proc reverseBits(a: BitsArray): BitsArray {...}{.raises: [], tags: [].}
-
Return the bit reversal of a.
Examples:
doAssert 7.uint16.toBitsArray.`$` == "1110000000000000" doAssert 7.uint16.toBitsArray.reverseBits.`$` == "0000000000000111"