My Blog

This post explores bit manipulation techniques in Solidity, focusing on optimizing operations using assembly code for gas efficiency.

The BitWise Contract

The BitWise contract demonstrates different ways to count set bits in a byte. Let's examine the implementation and optimize it using assembly.

At its core, the BitWise contract is designed to count the number of bits set to 1 in an 8-bit unsigned integer (uint8). This seemingly simple operation is fundamental to many low-level optimizations in blockchain development. The contract implements two approaches to solving this problem:

countBitSet:
The naive implementation uses a loop to check each bit position (0-7) by right-shifting the input value and using a bitwise AND operation with 1 to isolate each bit. This approach processes all 8 bits regardless of how many are actually set to 1, making it less efficient for sparse bit patterns.
countBitSetAsm:
The optimized implementation uses inline assembly with Brian Kernighan's algorithm, which leverages a clever bitwise trick. Instead of checking each bit position sequentially, it uses the expression n & (n-1) to clear the rightmost set bit in each iteration. This means the algorithm only performs as many iterations as there are set bits, making it significantly more efficient for most inputs.

The assembly implementation also demonstrates several important aspects of Solidity's low-level programming capabilities:

Variable initialization (result := 0)
Using local variables for computation (let value := data)
Conditional looping (for gt(value, 0) )
Arithmetic operations (add(result, 1))
Bitwise operations (and(value, sub(value, 1)))

The gas efficiency of the assembly implementation comes not only from fewer iterations but also from direct access to EVM operations without the safety checks and overhead of Solidity's high-level constructs. This example illustrates how strategic use of assembly can yield significant performance benefits in gas-sensitive smart contract operations.

// SPDX-License-Identifier: MIT

pragma solidity ^0.8.4;

contract BitWise {
    // count the number of bit set in data.  i.e. data = 7, result = 3
    function countBitSet(uint8 data) public pure returns (uint8 result) {
        for( uint i = 0; i < 8; i += 1) {
            if( ((data >> i) & 1) == 1) {
                result += 1;
            }
        }
    }

    function countBitSetAsm(uint8 data) public pure returns (uint8 result) {
        assembly {
            // Initialize result to 0
            result := 0
            
            // Brian Kernighan's Algorithm
            // Keep turning off the rightmost bit until data becomes 0
            // This is more efficient than checking each bit
            let value := data
            for {} gt(value, 0) {} {
                // Increment the result counter
                result := add(result, 1)
                
                // Turn off the rightmost bit that is set to 1
                // n & (n-1) removes the rightmost set bit
                value := and(value, sub(value, 1))
            }
        }
    }
}

Bit Counting Algorithms

Naïve Approach

The original countBitSet function uses a straightforward approach, checking each bit individually by shifting and masking. While simple to understand, this requires 8 iterations for an 8-bit number.

Brian Kernighan's Algorithm

Our optimized countBitSetAsm function implements Brian Kernighan's algorithm using assembly. This algorithm works by repeatedly clearing the rightmost set bit until no bits remain, counting how many operations this takes.

The key optimization is:

n & (n-1)

This expression always turns off the rightmost '1' bit in the binary representation.

Gas Comparison

The assembly implementation is more gas-efficient because:

It performs fewer iterations (only as many as there are set bits)
It avoids expensive repeated shifting operations
It uses direct EVM operations without the overhead of Solidity safety checks

String Character Access Function

The String contract demonstrates how to efficiently access characters in a string using assembly:

contract String {
    function charAt(string memory input, uint index) public pure returns(bytes2) {
        assembly {
            // Get the length of the string
            let len := mload(input)
            
            // Check if the index is within bounds
            if lt(index, len) {
                // Calculate the position of the character in memory
                // Add 32 to skip the length field of the string
                // Add index to get to the specific character
                let pos := add(add(input, 32), index)
                
                // Load the character at the calculated position
                // return first two bytes (char + trailing zero)
                return(pos, 2)
            }
            
            // If index is out of bounds, return 0x0000
            return(0, 2)
        }
    }
}

Test Cases

charAt("abcdef", 2) should return 0x6300 (the ASCII code for 'c' followed by a zero byte)
charAt("", 0) should return 0x0000 (out of bounds)
charAt("george", 10) should return 0x0000 (out of bounds)

Practical Applications

Bit manipulation techniques are valuable in Solidity for:

Storage optimization using bitmaps
Permission and flag systems
Cryptographic operations
Low-level data processing

By using these techniques, you can significantly reduce gas costs and improve the efficiency of your smart contracts.

Bit Manipulation Optimization in Solidity