Bitwise shifting instructions in EVM
EIP145 is a proposal for introducing native bitwise shifting instructions in the Ethereum Virtual Machine (EVM). The EVM currently lacks bitwise shifting operators, which are commonly used in programming languages for efficient manipulation of binary data. While shift operations can be implemented using arithmetic operators, this approach is more costly and requires more processing time from the host.
The proposal introduces three new instructions: SHL (shift left), SHR (logical shift right), and SAR (arithmetic shift right). The SHL instruction pops two values from the stack, the first being the number of bits to shift and the second being the value to shift. It then pushes the result of the shift operation onto the stack. The SHR instruction works similarly, but shifts the bits to the right with zero fill. The SAR instruction shifts the bits to the right with sign extension, meaning that the most significant bit is replicated to preserve the sign of the value.
The introduction of these instructions is motivated by the need for more efficient processing of bitwise operations in the EVM. Implementing shift operations using arithmetic operators currently costs 35 gas, while the proposed instructions only cost 3 gas. This makes them more costeffective for contracts that require frequent bitwise operations.
The proposal also includes test cases and implementation details for the new instructions. It is important to note that the instructions are designed to be backwards compatible with existing contracts, meaning that contracts written before the introduction of the instructions will still function properly.
Overall, the EIP145 proposal aims to improve the efficiency and costeffectiveness of bitwise operations in the EVM by introducing native bitwise shifting instructions.
Video
Original
Abstract
Native bitwise shifting instructions are introduced, which are more efficient processing wise on the host and are cheaper to use by a contract.
Motivation
EVM is lacking bitwise shifting operators, but supports other logical and arithmetic operators. Shift operations can be implemented via arithmetic operators, but that has a higher cost and requires more processing time from the host. Implementing SHL
and SHR
using arithmetic cost each 35 gas, while the proposed instructions take 3 gas.
Specification
The following instructions are introduced:
0x1b
: SHL
(shift left)
The SHL
instruction (shift left) pops 2 values from the stack, first arg1
and then arg2
, and pushes on the stack arg2
shifted to the left by arg1
number of bits. The result is equal to
(arg2 * 2^arg1) mod 2^256
Notes:
 The value (
arg2
) is interpreted as an unsigned number.  The shift amount (
arg1
) is interpreted as an unsigned number.  If the shift amount (
arg1
) is greater or equal 256 the result is 0.  This is equivalent to
PUSH1 2 EXP MUL
.
0x1c
: SHR
(logical shift right)
The SHR
instruction (logical shift right) pops 2 values from the stack, first arg1
and then arg2
, and pushes on the stack arg2
shifted to the right by arg1
number of bits with zero fill. The result is equal to
floor(arg2 / 2^arg1)
Notes:
 The value (
arg2
) is interpreted as an unsigned number.  The shift amount (
arg1
) is interpreted as an unsigned number.  If the shift amount (
arg1
) is greater or equal 256 the result is 0.  This is equivalent to
PUSH1 2 EXP DIV
.
0x1d
: SAR
(arithmetic shift right)
The SAR
instruction (arithmetic shift right) pops 2 values from the stack, first arg1
and then arg2
, and pushes on the stack arg2
shifted to the right by arg1
number of bits with sign extension. The result is equal to
floor(arg2 / 2^arg1)
Notes:
 The value (
arg2
) is interpreted as a signed number.  The shift amount (
arg1
) is interpreted as an unsigned number.  If the shift amount (
arg1
) is greater or equal 256 the result is 0 ifarg2
is nonnegative or 1 ifarg2
is negative.  This is not equivalent to
PUSH1 2 EXP SDIV
, since it rounds differently. SeeSDIV(1, 2) == 0
, whileSAR(1, 1) == 1
.
The cost of the shift instructions is set at verylow
tier (3 gas).
Rationale
Instruction operands were chosen to fit the more natural use case of shifting a value already on the stack. This means the operand order is swapped compared to most arithmetic instructions.
Backwards Compatibility
The newly introduced instructions have no effect on bytecode created in the past.
Test Cases
SHL
(shift left)

PUSH 0x0000000000000000000000000000000000000000000000000000000000000001 PUSH 0x00 SHL  0x0000000000000000000000000000000000000000000000000000000000000001

PUSH 0x0000000000000000000000000000000000000000000000000000000000000001 PUSH 0x01 SHL  0x0000000000000000000000000000000000000000000000000000000000000002

PUSH 0x0000000000000000000000000000000000000000000000000000000000000001 PUSH 0xff SHL  0x8000000000000000000000000000000000000000000000000000000000000000

PUSH 0x0000000000000000000000000000000000000000000000000000000000000001 PUSH 0x0100 SHL  0x0000000000000000000000000000000000000000000000000000000000000000

PUSH 0x0000000000000000000000000000000000000000000000000000000000000001 PUSH 0x0101 SHL  0x0000000000000000000000000000000000000000000000000000000000000000

PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff PUSH 0x00 SHL  0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff PUSH 0x01 SHL  0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe

PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff PUSH 0xff SHL  0x8000000000000000000000000000000000000000000000000000000000000000

PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff PUSH 0x0100 SHL  0x0000000000000000000000000000000000000000000000000000000000000000

PUSH 0x0000000000000000000000000000000000000000000000000000000000000000 PUSH 0x01 SHL  0x0000000000000000000000000000000000000000000000000000000000000000

PUSH 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff PUSH 0x01 SHL  0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe
SHR
(logical shift right)

PUSH 0x0000000000000000000000000000000000000000000000000000000000000001 PUSH 0x00 SHR  0x0000000000000000000000000000000000000000000000000000000000000001

PUSH 0x0000000000000000000000000000000000000000000000000000000000000001 PUSH 0x01 SHR  0x0000000000000000000000000000000000000000000000000000000000000000

PUSH 0x8000000000000000000000000000000000000000000000000000000000000000 PUSH 0x01 SHR  0x4000000000000000000000000000000000000000000000000000000000000000

PUSH 0x8000000000000000000000000000000000000000000000000000000000000000 PUSH 0xff SHR  0x0000000000000000000000000000000000000000000000000000000000000001

PUSH 0x8000000000000000000000000000000000000000000000000000000000000000 PUSH 0x0100 SHR  0x0000000000000000000000000000000000000000000000000000000000000000

PUSH 0x8000000000000000000000000000000000000000000000000000000000000000 PUSH 0x0101 SHR  0x0000000000000000000000000000000000000000000000000000000000000000

PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff PUSH 0x00 SHR  0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff PUSH 0x01 SHR  0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff PUSH 0xff SHR  0x0000000000000000000000000000000000000000000000000000000000000001

PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff PUSH 0x0100 SHR  0x0000000000000000000000000000000000000000000000000000000000000000

PUSH 0x0000000000000000000000000000000000000000000000000000000000000000 PUSH 0x01 SHR  0x0000000000000000000000000000000000000000000000000000000000000000
SAR
(arithmetic shift right)

PUSH 0x0000000000000000000000000000000000000000000000000000000000000001 PUSH 0x00 SAR  0x0000000000000000000000000000000000000000000000000000000000000001

PUSH 0x0000000000000000000000000000000000000000000000000000000000000001 PUSH 0x01 SAR  0x0000000000000000000000000000000000000000000000000000000000000000

PUSH 0x8000000000000000000000000000000000000000000000000000000000000000 PUSH 0x01 SAR  0xc000000000000000000000000000000000000000000000000000000000000000

PUSH 0x8000000000000000000000000000000000000000000000000000000000000000 PUSH 0xff SAR  0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

PUSH 0x8000000000000000000000000000000000000000000000000000000000000000 PUSH 0x0100 SAR  0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

PUSH 0x8000000000000000000000000000000000000000000000000000000000000000 PUSH 0x0101 SAR  0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff PUSH 0x00 SAR  0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff PUSH 0x01 SAR  0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff PUSH 0xff SAR  0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff PUSH 0x0100 SAR  0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

PUSH 0x0000000000000000000000000000000000000000000000000000000000000000 PUSH 0x01 SAR  0x0000000000000000000000000000000000000000000000000000000000000000

PUSH 0x4000000000000000000000000000000000000000000000000000000000000000 PUSH 0xfe SAR  0x0000000000000000000000000000000000000000000000000000000000000001

PUSH 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff PUSH 0xf8 SAR  0x000000000000000000000000000000000000000000000000000000000000007f

PUSH 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff PUSH 0xfe SAR  0x0000000000000000000000000000000000000000000000000000000000000001

PUSH 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff PUSH 0xff SAR  0x0000000000000000000000000000000000000000000000000000000000000000

PUSH 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff PUSH 0x0100 SAR  0x0000000000000000000000000000000000000000000000000000000000000000
Implementation
Client support:
 cppethereum: https://github.com/ethereum/cppethereum/pull/4054
Compiler support:
 Solidity/LLL: https://github.com/ethereum/solidity/pull/2541
Tests
Sources:
Filled Tests:
 https://github.com/ethereum/tests/tree/develop/GeneralStateTests/stShift
 https://github.com/ethereum/tests/tree/develop/BlockchainTests/GeneralStateTests/stShift
Copyright
Copyright and related rights waived via CC0.
Adopted by projects
Not miss a beat of EIPs' update?
Subscribe EIPs Fun to receive the latest updates of EIPs Good for Buidlers to follow up.
View all