Introduce a new opcode, CLZ(x), which pops x from the stack and pushes the number of leading zero bits in x to the stack. If x is zero, pushes 256.
Count leading zeros (CLZ) is a native opcode in many processor architectures (even in RISC architectures like ARM).
It is a basic building block used in math operations, byte operations, compression algorithms, data structures:
A new opcode is introduced: CLZ (0x1e).
/// @dev Count leading zeros.
/// Returns the number of zeros preceding the most significant one bit.
/// If `x` is zero, returns 256.
/// This is the fastest known `clz` implementation in Solidity and uses about 184 gas.
function clz(uint256 x) internal pure returns (uint256 r) {
/// @solidity memory-safe-assembly
assembly {
r := shl(7, lt(0xffffffffffffffffffffffffffffffff, x))
r := or(r, shl(6, lt(0xffffffffffffffff, shr(r, x))))
r := or(r, shl(5, lt(0xffffffff, shr(r, x))))
r := or(r, shl(4, lt(0xffff, shr(r, x))))
r := or(r, shl(3, lt(0xff, shr(r, x))))
// forgefmt: disable-next-item
r := add(xor(r, byte(and(0x1f, shr(shr(r, x), 0x8421084210842108cc6318c6db6d54be)),
0xf8f9f9faf9fdfafbf9fdfcfdfafbfcfef9fafdfafcfcfbfefafafcfbffffffff)), iszero(x))
}
}
Or in Python,
def clz(x):
"""Returns the number of zeros preceding the most significant one bit."""
if x < 0:
raise ValueError("clz is undefined for negative numbers")
if x > 2**256 - 1:
raise ValueError("clz is undefined for numbers larger than 2**256 - 1")
if x == 0:
return 256
# Convert to binary string and remove any '0b' prefix.
bin_str = bin(x).replace('0b', '')
return 256 - len(bin_str)
The cost of the opcode is 3, the same as add.
256 is the smallest number after 255. Returning a small number allows the result to be compared with minimal additional bytecode.
For byte scanning operations, one can get the number of bytes to be skipped for a zero word by simply computing 256 >> 3, which gives 32.
Computing the least significant bit can be easily implemented with CLZ by isolating the smallest bit via x & -x.
We have benchmarked the clz and add implementation in the intx library. clz uses approximately the same amount of compute cycles as add.
This is a new opcode not present prior.
PUSH32 0x000000000000000000000000000000000000000000000000000000000000000
CLZ
---
0x0000000000000000000000000000000000000000000000000000000000000100
PUSH32 0x8000000000000000000000000000000000000000000000000000000000000000
CLZ
---
0x0000000000000000000000000000000000000000000000000000000000000000
PUSH32 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
CLZ
---
0x0000000000000000000000000000000000000000000000000000000000000000
PUSH32 0x4000000000000000000000000000000000000000000000000000000000000000
CLZ
---
0x0000000000000000000000000000000000000000000000000000000000000001
PUSH32 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
CLZ
---
0x0000000000000000000000000000000000000000000000000000000000000001
PUSH32 0x0000000000000000000000000000000000000000000000000000000000000001
CLZ
---
0x00000000000000000000000000000000000000000000000000000000000000ff
TBA
Copyright and related rights waived via CC0.