bitops

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

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

The module will fallback to pure nim procs incase 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 function/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, countTrailingZeroBits may return undefined and/or platform dependent value if given invalid input.

Imports

macros, since

Types

BitsRange[T] = range[0 .. sizeof(T) * 8 - 1]
A range with all bit positions for type T Source Edit

Procs

proc bitnot[T: SomeInteger](x: T): T {...}{.magic: "BitnotI", noSideEffect.}
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
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:

var v = 0b0000_0011'u8
doAssert v.masked(0b0000_1010'u8) == 0b0000_0010'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 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
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
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
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 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 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 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:

var v = 0b0000_1111'u8
doAssert v.testBit(0)
doAssert not v.testBit(7)
Source Edit
proc countSetBits(x: SomeInteger): int {...}{.inline, noSideEffect.}
Counts the set bits in integer. (also called Hamming weight.)

Example:

doAssert countSetBits(0b0000_0011'u8) == 2
doAssert countSetBits(0b1010_1010'u8) == 4
Source Edit
proc popcount(x: SomeInteger): int {...}{.inline, noSideEffect.}
Alias for for countSetBits. (Hamming weight.) Source Edit
proc parityBits(x: SomeInteger): int {...}{.inline, noSideEffect.}
Calculate the bit parity in integer. If number of 1-bit is odd 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
proc firstSetBit(x: SomeInteger): int {...}{.inline, noSideEffect.}
Returns the 1-based index of the least significant set bit of x. If x is zero, when noUndefinedBitOpts is set, result is 0, otherwise 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 fastLog2(x: SomeInteger): int {...}{.inline, noSideEffect.}
Quickly find the log base 2 of an integer. If x is zero, when noUndefinedBitOpts is set, result is -1, otherwise 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
proc countLeadingZeroBits(x: SomeInteger): int {...}{.inline, noSideEffect.}

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

See also:

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
proc countTrailingZeroBits(x: SomeInteger): int {...}{.inline, noSideEffect.}

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

See also:

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
proc rotateLeftBits(value: uint8; amount: range[0 .. 8]): uint8 {...}{.inline,
    noSideEffect, raises: [], tags: [].}
Left-rotate bits in a 8-bits value.

Example:

doAssert rotateLeftBits(0b0000_0001'u8, 1) == 0b0000_0010'u8
doAssert rotateLeftBits(0b0000_0001'u8, 2) == 0b0000_0100'u8
doAssert rotateLeftBits(0b0100_0001'u8, 1) == 0b1000_0010'u8
doAssert rotateLeftBits(0b0100_0001'u8, 2) == 0b0000_0101'u8
Source Edit
proc rotateLeftBits(value: uint16; amount: range[0 .. 16]): uint16 {...}{.inline,
    noSideEffect, raises: [], tags: [].}

Left-rotate bits in a 16-bits value.

See also:

Source Edit
proc rotateLeftBits(value: uint32; amount: range[0 .. 32]): uint32 {...}{.inline,
    noSideEffect, raises: [], tags: [].}

Left-rotate bits in a 32-bits value.

See also:

Source Edit
proc rotateLeftBits(value: uint64; amount: range[0 .. 64]): uint64 {...}{.inline,
    noSideEffect, raises: [], tags: [].}

Left-rotate bits in a 64-bits value.

See also:

Source Edit
proc rotateRightBits(value: uint8; amount: range[0 .. 8]): uint8 {...}{.inline,
    noSideEffect, raises: [], tags: [].}
Right-rotate bits in a 8-bits value.

Example:

doAssert rotateRightBits(0b0000_0001'u8, 1) == 0b1000_0000'u8
doAssert rotateRightBits(0b0000_0001'u8, 2) == 0b0100_0000'u8
doAssert rotateRightBits(0b0100_0001'u8, 1) == 0b1010_0000'u8
doAssert rotateRightBits(0b0100_0001'u8, 2) == 0b0101_0000'u8
Source Edit
proc rotateRightBits(value: uint16; amount: range[0 .. 16]): uint16 {...}{.inline,
    noSideEffect, raises: [], tags: [].}

Right-rotate bits in a 16-bits value.

See also:

Source Edit
proc rotateRightBits(value: uint32; amount: range[0 .. 32]): uint32 {...}{.inline,
    noSideEffect, raises: [], tags: [].}

Right-rotate bits in a 32-bits value.

See also:

Source Edit
proc rotateRightBits(value: uint64; amount: range[0 .. 64]): uint64 {...}{.inline,
    noSideEffect, raises: [], tags: [].}

Right-rotate bits in a 64-bits value.

See also:

Source Edit
proc reverseBits[T: SomeUnsignedInt](x: T): T {...}{.noSideEffect.}
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

Funcs

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
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
func masked[T: SomeInteger](v: T; slice: Slice[int]): T {...}{.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
doAssert v.masked(1 .. 3) == 0b0000_1010'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:

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

var v = 0b0000_0011'u8
doAssert v.setMasked(2 .. 3) == 0b0000_1111'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:

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

var v = 0b0000_0011'u8
doAssert v.clearMasked(1 .. 3) == 0b0000_0001'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:

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

var v = 0b0000_0011'u8
doAssert v.flipMasked(1 .. 3) == 0b0000_1101'u8
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 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
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

© 2006–2021 Andreas Rumpf
Licensed under the MIT License.
https://nim-lang.org/docs/bitops.html