☰

# std/bitops

Theme:

- Manual
- Standard library
- Index
- Compiler docs
- Fusion docs
- devel, stable

Search:
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