A helper for implementing bitwise operators on Nat.
Each bit of the resulting Nat is the result of applying f to the corresponding bits of the input
Nats, up to the position of the highest set bit in either input.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Shifts the binary representation of a value left by the specified number of bits. Usually accessed
via the <<< operator.
Examples:
1 <<< 2 = 41 <<< 3 = 80 <<< 3 = 00xf1 <<< 4 = 0xf10
Instances For
Shifts the binary representation of a value right by the specified number of bits. Usually accessed
via the >>> operator.
Examples:
4 >>> 2 = 18 >>> 2 = 28 >>> 3 = 10 >>> 3 = 00xf13a >>> 8 = 0xf1
Equations
- x✝.shiftRight 0 = x✝
- x✝.shiftRight m.succ = x✝.shiftRight m / 2
Instances For
Equations
- Nat.instAndOp = { and := Nat.land }
Equations
- Nat.instXorOp = { xor := Nat.xor }
Equations
- Nat.instShiftLeft = { shiftLeft := Nat.shiftLeft }
Equations
- Nat.instShiftRight = { shiftRight := Nat.shiftRight }
testBit #
We define an operation for testing individual bits in the binary representation of a number.
Asserts that the (n+1)th least significant bit of m is not set.
(This definition is used by Lean internally for compact bitmaps.)
Equations
- m.hasNotBit n = (Nat.land 1 (m.shiftRight n) ≠ 1)
Instances For
The number of zero bits below the least significant set bit of n, or zero if n = 0.
See Nat.trailingZeros_def for a simple recursive characterization.
The kernel skips zero 64-bit blocks, then counts bits in the first nonzero block. At runtime this scans the low machine words without allocating or dividing the input.
Equations
- One or more equations did not get rendered due to their size.