Source Edit

This module implements a series of low level methods for bit manipulation.

By default, compiler intrinsics are used where possible to improve performance on supported compilers: GCC, LLVM_GCC, CLANG, VCC, ICC.

The module will fallback to pure nim procs in case the backend is not supported. You can also use the flag noIntrinsicsBitOpts to disable compiler intrinsics.

This module is also compatible with other backends: JavaScript, NimScript as well as the compiletime VM.

As a result of using optimized functions/intrinsics, some functions can return undefined results if the input is invalid. You can use the flag noUndefinedBitOpts to force predictable behaviour for all input, causing a small performance hit.

At this time only fastLog2, firstSetBit, countLeadingZeroBits and countTrailingZeroBits may return undefined and/or platform dependent values if given invalid input.

Imports

macros, since, bitops_utils, countbits_impl

Types

BitsRange[T] = range[0 .. sizeof(T) * 8 - 1]

A range with all bit positions for type T. Source Edit

Procs

func bitnot[T: SomeInteger](x: T): T {.magic: "BitnotI", ...raises: [], tags: [],
                                       forbids: [].}

Computes the bitwise complement of the integer x. Source Edit

proc bitslice[T: SomeInteger](v: var T; slice: Slice[int]) {.inline.}

Mutates v into an extracted (and shifted) slice of bits from v.

Example:

var x = 0b101110
x.bitslice(2 .. 4)
doAssert x == 0b011

Source Edit

func bitsliced[T: SomeInteger](v: T; slice: Slice[int]): T {.inline.}

Returns an extracted (and shifted) slice of bits from v.

Example:

doAssert 0b10111.bitsliced(2 .. 4) == 0b101
doAssert 0b11100.bitsliced(0 .. 2) == 0b100
doAssert 0b11100.bitsliced(0 ..< 3) == 0b100

Source Edit

proc clearBit[T: SomeInteger](v: var T; bit: BitsRange[T]) {.inline.}

Mutates v, with the bit at position bit set to 0.

Example:

var v = 0b0000_0011'u8
v.clearBit(1'u8)
doAssert v == 0b0000_0001'u8

Source Edit

proc clearMask[T: SomeInteger](v: var T; mask: T) {.inline.}

Mutates v, with all the 1 bits from mask set to 0.

Effectively maps to a bitand operation with an inverted mask.

Example:

var v = 0b0000_0011'u8
v.clearMask(0b0000_1010'u8)
doAssert v == 0b0000_0001'u8

Source Edit

proc clearMask[T: SomeInteger](v: var T; slice: Slice[int]) {.inline.}

Mutates v, with all the 1 bits in the range of slice set to 0.

Effectively maps to a bitand operation with an inverted mask.

Example:

var v = 0b0000_0011'u8
v.clearMask(1 .. 3)
doAssert v == 0b0000_0001'u8

Source Edit

func clearMasked[T: SomeInteger](v, mask: T): T {.inline.}

Returns v, with all the 1 bits from mask set to 0.

Effectively maps to a bitand operation with an inverted mask.

Example:

let v = 0b0000_0011'u8
doAssert v.clearMasked(0b0000_1010'u8) == 0b0000_0001'u8

Source Edit

func clearMasked[T: SomeInteger](v: T; slice: Slice[int]): T {.inline.}

Returns v, with all the 1 bits in the range of slice set to 0.

Effectively maps to a bitand operation with an inverted mask.

Example:

let v = 0b0000_0011'u8
doAssert v.clearMasked(1 .. 3) == 0b0000_0001'u8

Source Edit

func countLeadingZeroBits(x: SomeInteger): int {.inline.}

Returns the number of leading zero bits in an integer. If x is zero, when noUndefinedBitOpts is set, the result is 0, otherwise the result is undefined.

See also:

• countTrailingZeroBits proc

Example:

doAssert countLeadingZeroBits(0b0000_0001'u8) == 7
doAssert countLeadingZeroBits(0b0000_0010'u8) == 6
doAssert countLeadingZeroBits(0b0000_0100'u8) == 5
doAssert countLeadingZeroBits(0b0000_1000'u8) == 4
doAssert countLeadingZeroBits(0b0000_1111'u8) == 4

Source Edit

func countSetBits(x: SomeInteger): int {.inline.}

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

Example:

doAssert countSetBits(0b0000_0011'u8) == 2
doAssert countSetBits(0b1010_1010'u8) == 4

Source Edit

func countTrailingZeroBits(x: SomeInteger): int {.inline.}

Returns the number of trailing zeros in an integer. If x is zero, when noUndefinedBitOpts is set, the result is 0, otherwise the result is undefined.

See also:

• countLeadingZeroBits proc

Example:

doAssert countTrailingZeroBits(0b0000_0001'u8) == 0
doAssert countTrailingZeroBits(0b0000_0010'u8) == 1
doAssert countTrailingZeroBits(0b0000_0100'u8) == 2
doAssert countTrailingZeroBits(0b0000_1000'u8) == 3
doAssert countTrailingZeroBits(0b0000_1111'u8) == 0

Source Edit

func fastLog2(x: SomeInteger): int {.inline.}

Quickly find the log base 2 of an integer. If x is zero, when noUndefinedBitOpts is set, the result is -1, otherwise the result is undefined.

Example:

doAssert fastLog2(0b0000_0001'u8) == 0
doAssert fastLog2(0b0000_0010'u8) == 1
doAssert fastLog2(0b0000_0100'u8) == 2
doAssert fastLog2(0b0000_1000'u8) == 3
doAssert fastLog2(0b0000_1111'u8) == 3

Source Edit

func firstSetBit(x: SomeInteger): int {.inline.}

Returns the 1-based index of the least significant set bit of x. If x is zero, when noUndefinedBitOpts is set, the result is 0, otherwise the result is undefined.

Example:

doAssert firstSetBit(0b0000_0001'u8) == 1
doAssert firstSetBit(0b0000_0010'u8) == 2
doAssert firstSetBit(0b0000_0100'u8) == 3
doAssert firstSetBit(0b0000_1000'u8) == 4
doAssert firstSetBit(0b0000_1111'u8) == 1

Source Edit

proc flipBit[T: SomeInteger](v: var T; bit: BitsRange[T]) {.inline.}

Mutates v, with the bit at position bit flipped.

Example:

var v = 0b0000_0011'u8
v.flipBit(1'u8)
doAssert v == 0b0000_0001'u8
v = 0b0000_0011'u8
v.flipBit(2'u8)
doAssert v == 0b0000_0111'u8

Source Edit

proc flipMask[T: SomeInteger](v: var T; mask: T) {.inline.}

Mutates v, with all the 1 bits from mask flipped.

Effectively maps to a bitxor operation.

Example:

var v = 0b0000_0011'u8
v.flipMask(0b0000_1010'u8)
doAssert v == 0b0000_1001'u8

Source Edit

proc flipMask[T: SomeInteger](v: var T; slice: Slice[int]) {.inline.}

Mutates v, with all the 1 bits in the range of slice flipped.

Effectively maps to a bitxor operation.

Example:

var v = 0b0000_0011'u8
v.flipMask(1 .. 3)
doAssert v == 0b0000_1101'u8

Source Edit

func flipMasked[T: SomeInteger](v, mask: T): T {.inline.}

Returns v, with all the 1 bits from mask flipped.

Effectively maps to a bitxor operation.

Example:

let v = 0b0000_0011'u8
doAssert v.flipMasked(0b0000_1010'u8) == 0b0000_1001'u8

Source Edit

func flipMasked[T: SomeInteger](v: T; slice: Slice[int]): T {.inline.}

Returns v, with all the 1 bits in the range of slice flipped.

Effectively maps to a bitxor operation.

Example:

let v = 0b0000_0011'u8
doAssert v.flipMasked(1 .. 3) == 0b0000_1101'u8

Source Edit

proc mask[T: SomeInteger](v: var T; mask: T) {.inline.}

Mutates v, with only the 1 bits from mask matching those of v set to 1.

Effectively maps to a bitand operation.

Example:

var v = 0b0000_0011'u8
v.mask(0b0000_1010'u8)
doAssert v == 0b0000_0010'u8

Source Edit

proc mask[T: SomeInteger](v: var T; slice: Slice[int]) {.inline.}

Mutates v, with only the 1 bits in the range of slice matching those of v set to 1.

Effectively maps to a bitand operation.

Example:

var v = 0b0000_1011'u8
v.mask(1 .. 3)
doAssert v == 0b0000_1010'u8

Source Edit

proc masked[T: SomeInteger](v, mask: T): T {.inline.}

Returns v, with only the 1 bits from mask matching those of v set to 1.

Effectively maps to a bitand operation.

Example:

let v = 0b0000_0011'u8
doAssert v.masked(0b0000_1010'u8) == 0b0000_0010'u8

Source Edit

func masked[T: SomeInteger](v: T; slice: Slice[int]): T {.inline.}

Returns v, with only the 1 bits in the range of slice matching those of v set to 1.

Effectively maps to a bitand operation.

Example:

let v = 0b0000_1011'u8
doAssert v.masked(1 .. 3) == 0b0000_1010'u8

Source Edit

func parityBits(x: SomeInteger): int {.inline.}

Calculate the bit parity in an integer. If the number of 1-bits is odd, the parity is 1, otherwise 0.

Example:

doAssert parityBits(0b0000_0000'u8) == 0
doAssert parityBits(0b0101_0001'u8) == 1
doAssert parityBits(0b0110_1001'u8) == 0
doAssert parityBits(0b0111_1111'u8) == 1

Source Edit

func popcount(x: SomeInteger): int {.inline.}

Alias for countSetBits (Hamming weight). Source Edit

func reverseBits[T: SomeUnsignedInt](x: T): T

Return the bit reversal of x.

Example:

doAssert reverseBits(0b10100100'u8) == 0b00100101'u8
doAssert reverseBits(0xdd'u8) == 0xbb'u8
doAssert reverseBits(0xddbb'u16) == 0xddbb'u16
doAssert reverseBits(0xdeadbeef'u32) == 0xf77db57b'u32

Source Edit

func rotateLeftBits[T: SomeUnsignedInt](value: T;
                                        shift: range[0 .. (sizeof(T) * 8)]): T {.
    inline.}

Left-rotate bits in a value.

Example:

doAssert rotateLeftBits(0b0110_1001'u8, 4) == 0b1001_0110'u8
doAssert rotateLeftBits(0b00111100_11000011'u16, 8) ==
  0b11000011_00111100'u16
doAssert rotateLeftBits(0b0000111111110000_1111000000001111'u32, 16) ==
  0b1111000000001111_0000111111110000'u32
doAssert rotateLeftBits(0b00000000111111111111111100000000_11111111000000000000000011111111'u64, 32) ==
  0b11111111000000000000000011111111_00000000111111111111111100000000'u64

Source Edit

func rotateRightBits[T: SomeUnsignedInt](value: T;
    shift: range[0 .. (sizeof(T) * 8)]): T {.inline.}

Right-rotate bits in a value.

Example:

doAssert rotateRightBits(0b0110_1001'u8, 4) == 0b1001_0110'u8
doAssert rotateRightBits(0b00111100_11000011'u16, 8) ==
  0b11000011_00111100'u16
doAssert rotateRightBits(0b0000111111110000_1111000000001111'u32, 16) ==
  0b1111000000001111_0000111111110000'u32
doAssert rotateRightBits(0b00000000111111111111111100000000_11111111000000000000000011111111'u64, 32) ==
  0b11111111000000000000000011111111_00000000111111111111111100000000'u64

Source Edit

proc setBit[T: SomeInteger](v: var T; bit: BitsRange[T]) {.inline.}

Mutates v, with the bit at position bit set to 1.

Example:

var v = 0b0000_0011'u8
v.setBit(5'u8)
doAssert v == 0b0010_0011'u8

Source Edit

proc setMask[T: SomeInteger](v: var T; mask: T) {.inline.}

Mutates v, with all the 1 bits from mask set to 1.

Effectively maps to a bitor operation.

Example:

var v = 0b0000_0011'u8
v.setMask(0b0000_1010'u8)
doAssert v == 0b0000_1011'u8

Source Edit

proc setMask[T: SomeInteger](v: var T; slice: Slice[int]) {.inline.}

Mutates v, with all the 1 bits in the range of slice set to 1.

Effectively maps to a bitor operation.

Example:

var v = 0b0000_0011'u8
v.setMask(2 .. 3)
doAssert v == 0b0000_1111'u8

Source Edit

func setMasked[T: SomeInteger](v, mask: T): T {.inline.}

Returns v, with all the 1 bits from mask set to 1.

Effectively maps to a bitor operation.

Example:

let v = 0b0000_0011'u8
doAssert v.setMasked(0b0000_1010'u8) == 0b0000_1011'u8

Source Edit

func setMasked[T: SomeInteger](v: T; slice: Slice[int]): T {.inline.}

Returns v, with all the 1 bits in the range of slice set to 1.

Effectively maps to a bitor operation.

Example:

let v = 0b0000_0011'u8
doAssert v.setMasked(2 .. 3) == 0b0000_1111'u8

Source Edit

proc testBit[T: SomeInteger](v: T; bit: BitsRange[T]): bool {.inline.}

Returns true if the bit in v at positions bit is set to 1.

Example:

let v = 0b0000_1111'u8
doAssert v.testBit(0)
doAssert not v.testBit(7)

Source Edit

func toMask[T: SomeInteger](slice: Slice[int]): T {.inline.}

Creates a bitmask based on a slice of bits.

Example:

doAssert toMask[int32](1 .. 3) == 0b1110'i32
doAssert toMask[int32](0 .. 3) == 0b1111'i32

Source Edit

Macros

macro bitand[T: SomeInteger](x, y: T; z: varargs[T]): T

Computes the bitwise and of all arguments collectively. Source Edit

macro bitor[T: SomeInteger](x, y: T; z: varargs[T]): T

Computes the bitwise or of all arguments collectively. Source Edit

macro bitxor[T: SomeInteger](x, y: T; z: varargs[T]): T

Computes the bitwise xor of all arguments collectively. Source Edit

macro clearBits(v: typed; bits: varargs[typed]): untyped

Mutates v, with the bits at positions bits set to 0.

Example:

var v = 0b1111_1111'u8
v.clearBits(1, 3, 5, 7)
doAssert v == 0b0101_0101'u8

Source Edit

macro flipBits(v: typed; bits: varargs[typed]): untyped

Mutates v, with the bits at positions bits set to 0.

Example:

var v = 0b0000_1111'u8
v.flipBits(1, 3, 5, 7)
doAssert v == 0b1010_0101'u8

Source Edit

macro setBits(v: typed; bits: varargs[typed]): untyped

Mutates v, with the bits at positions bits set to 1.

Example:

var v = 0b0000_0011'u8
v.setBits(3, 5, 7)
doAssert v == 0b1010_1011'u8

Source Edit