bitops

nimony/lib/std/bitops.nim

This module implements a series of low-level bit manipulation procedures over the fixed-width unsigned integers uint8, uint16, uint32 and uint64 -- or any type that satifies the BitInteger concept.

The procedures are generic and constrained by the BitInteger concept below, which lists exactly the bitwise and shift operators the algorithms rely on. The bodies are written against those operations only (plus a runtime sizeof to recover the bit width), so they lower cleanly to C, LLVM and JS alike, and any type providing the operator set is accepted.

Bit indices are 0-based and, for the rotate procedures, the shift amount is taken modulo the bit width so any amount is well defined.

type BitInteger = concept
  func and(x: Self, y: Self): Self
  func or(x: Self, y: Self): Self
  func xor(x: Self, y: Self): Self
  func not(x: Self): Self
  func shl(x: Self, y: int64): Self
  func shr(x: Self, y: int64): Self
  func -(x: Self, y: Self): Self
  func ==(x: Self, y: Self): bool

func countSetBits(x: T): int64
Counts the set bits in x (the Hamming weight / population count).
func popcount(x: T): int64
Alias for countSetBits.
func parityBits(x: T): int64
Returns 1 when x has an odd number of set bits, otherwise 0.
func firstSetBit(x: T): int64
Returns the 1-based index of the least-significant set bit of x. Returns 0 when x is 0.
func trailingZeroBits(x: T): int64
Returns the number of trailing zero bits of x, or the bit width when x is 0.
func leadingZeroBits(x: T): int64
Returns the number of leading (most-significant) zero bits of x, or the bit width when x is 0.
func bitand(x: T; y: T): T
Computes the and of x and y.
func bitor(x: T; y: T): T
Computes the or of x and y.
func bitxor(x: T; y: T): T
Computes the xor of x and y.
func bitnot(x: T): T
Computes the bitwise complement of x.
func rotateLeftBits(v: T; amount: int64): T
Rotates the bits of v left by amount positions (taken modulo the bit width).
func rotateRightBits(v: T; amount: int64): T
Rotates the bits of v right by amount positions (taken modulo the bit width).
func setBit(v: var T; bit: int64)
Sets the bit at position bit of v to 1.
func clearBit(v: var T; bit: int64)
Clears the bit at position bit of v to 0.
func flipBit(v: var T; bit: int64)
Toggles the bit at position bit of v.
func testBit(v: T; bit: int64): bool
Returns true when the bit at position bit of v is set.