EIP-7939 Count Leading Zeros (CLZ) Opcode
Final · EVM & execution · EIP status Final · created 2025-04-28
Adds a new EVM opcode, CLZ (0x1e), that counts in one step how many consecutive 0 bits lead a 256-bit value. The cost is 5 gas.
Why it is needed
Counting leading zeros is a very basic operation that many CPUs, such as ARM, provide as a native instruction. It is widely used in math functions such as logarithms, powers and square roots, byte string comparison, data compression and decompression, finding the next set bit in a bitmap, and post-quantum signature verification. However, the Ethereum Virtual Machine (EVM) has no such instruction, so today it must be emulated in Solidity code. Even the fastest known implementation uses about 184 gas and contains several large constants, which increases contract code size. The dynamic bit shift operations this implementation uses are especially expensive in zero-knowledge (ZK) proving environments, so the burden is greater for systems that use ZK proofs. Adding one instruction lets the same computation run for 5 gas, with smaller code and cheaper proving cost.
What changes
Today
- Counting leading zeros requires complex Solidity code and costs about 184 gas
- This code contains several large constants and is often inlined, which enlarges the bytecode
- It uses dynamic bit shifts many times, so the ZK proving cost is high
After EIP-7939
- A single CLZ instruction finishes the same computation for 5 gas
- Contract bytecode gets smaller
- On SP1 rv32im, a 256-bit CLZ is cheaper to prove than ADD
Who is affected
- Smart contract developers: Code for math libraries, compression, bitmaps and byte comparison gets shorter and uses less gas.
- Client teams: The new opcode 0x1e must be implemented. It is a simple operation that does not touch state, so the implementation burden is small.
- ZK proving systems and L2s: They prove a native instruction instead of an expensive dynamic shift implementation, so the proving cost drops.
- Users: Computation gets cheaper for apps that use this operation heavily.
In depth
Instruction definition
A new opcode, CLZ, is added with number 0x1e. It pops a value x from the stack and pushes the number of 0 bits before the most significant 1 bit of x. If x is 0, it pushes 256. The source document shows the same behavior in three reference implementations: Solidity, Python and C++. The Solidity reference implementation is the fastest known one, using about 184 gas, and one of the C++ implementations represents a 256-bit number as eight uint32 values, a form optimized for SP1 rv32im proving. This EIP has Final status, so the specification is settled.
Gas cost 5, same as MUL
The instruction costs 5 gas, the same as MUL. It was originally 3, but it was raised to 5 to avoid the denial-of-service (DoS) risk that could arise from pricing it too cheaply. As justification, the source document presents the ADD implementation in the intx library and benchmark results. CLZ uses about the same compute cycles as ADD, and the variant optimized for SP1 rv32im uses fewer cycles than ADD in both the average and worst cases. On SP1 rv32im, a 256-bit CLZ is also cheaper to prove than ADD.
Special handling of a 0 input
CLZ(0) returns 256. 256 is the smallest number right after 255, so checking whether the result is outside the valid range of bit positions needs almost no extra bytecode. It is also useful when scanning data byte by byte. If an entire word is 0, computing 256 >> 3 immediately gives 32, the number of bytes to skip. The design returns a defined value instead of throwing an exception.
Why CLZ and not CTZ
CTZ (count trailing zeros), which counts the zeros at the low end (least significant), could also be a candidate, but this EIP adds only CLZ. The lowest set bit is easy to isolate with the x & -x operation, so CLZ alone is enough to implement what CTZ does. The reverse does not hold. CLZ cannot be implemented with CTZ. So it chose CLZ, the more expressive of the two.
ZK proving cost and bytecode size
The fastest current Solidity implementation uses a dynamic bitwise right shift (shr) many times. In ZK proving environments, shifts are expensive operations. On SP1 rv32im, a 32-bit right shift is 1.6 times more expensive than a 32-bit multiplication. A native CLZ instruction replaces the whole shift chain, so the proving cost drops. The existing Solidity implementation also contains several large constants and is often inlined for performance, which increases code size, and replacing it with a single opcode makes the bytecode smaller too.
Test cases
The source document presents six test cases. Input 0 returns 256 (0x100), 0x8000...00 with only the top bit set and 0xffff...ff with all bits set return 0, 0x4000...00 and 0x7fff...ff return 1, and input 1 returns 255 (0xff). The set is built to show that when the position of the most significant 1 bit is the same, the result is the same whatever the bits below it are.
Security and backward compatibility
CLZ is an instruction that neither reads nor writes state, and its memory use, compute cost and proving cost are all at a low constant level even in the worst case. The source document therefore explains that it cannot be abused for denial-of-service attacks. It is a new opcode that did not exist before, so it does not change the behavior of already deployed contracts and there is no backward compatibility issue.