Solidity – Understanding Bit Summation and Its Impact on Gas Costs

gassolidity

Is there an efficient way to perform bit summation in Solidity? Let's say I have 256 bools, and I want to count how many of them are true. Looping over all 256 would be extremely gas-expensive.

I can optimize by encoding all 256 into a single uint256, where each bool represents one bit. They use a lot less storage now, but counting up how many are true still seems to require looping through each bit of the uint256. Is there any alternative?

Best Answer

You can use the Brian Kernighan algorithm to count the number of set bits in a uint256

function countSetBits(uint256 x) public pure returns (uint8) {
    uint8 count;
    while (x != 0) {
        x &= x - 1;
        count++;
    }
    return count;
}
Related Topic