Skip to content

Instantly share code, notes, and snippets.

@atarpara
Last active August 26, 2022 08:55
Show Gist options
  • Save atarpara/d6d3773d0ce8958b95804fd36981825f to your computer and use it in GitHub Desktop.
Save atarpara/d6d3773d0ce8958b95804fd36981825f to your computer and use it in GitHub Desktop.
LSB Bit Using Solmate Log2
pragma solidity ^0.8.4;
library LibBit {
function lsbsolmate(uint256 x) pure internal returns(uint256 r){
assembly {
// Set Only Right Most Bit all other 0
//x := xor(x,and(x,sub(x,1)))
x:= and(x,add(not(x),1))
// solmate log2 logic
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))))
r := or(r, shl(2, lt(0xf, shr(r, x))))
r := or(r, shl(1, lt(0x3, shr(r, x))))
r := or(r, lt(0x1, shr(r, x)))
}
}
}
@atarpara
Copy link
Author

@Vectorized Your trick is good but for the average case solmate log2 is optimize. (+ small bytecode)

image

@Vectorized
Copy link

@atarpara Hmm...

[PASS] testFuzzLSB() (gas: 285358) // Original (with the revert)
[PASS] testFuzzLSB() (gas: 252334) // Original (without the revert)
[PASS] testFuzzLSB() (gas: 217774) // Optimizoor (with the revert)
function testFuzzLSB() public {
    uint256 brutalizer = uint256(keccak256(abi.encode(address(this), block.timestamp)));
    for (uint256 i = 0; i < 256; i++) {
        assertEq(FixedPointMathLib.lsb(1 << i), i);
        assertEq(FixedPointMathLib.lsb(type(uint256).max << i), i);
        assertEq(FixedPointMathLib.lsb((brutalizer | 1) << i), i);
    }
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment