Skip to content

Instantly share code, notes, and snippets.

@atarpara
Created August 24, 2022 05:34
Show Gist options
  • Save atarpara/79aacc2aeeab5fcec555a10d13177505 to your computer and use it in GitHub Desktop.
Save atarpara/79aacc2aeeab5fcec555a10d13177505 to your computer and use it in GitHub Desktop.
Most Significant Bit Index
pragma solidity ^0.8.4;
library LibBit {
function msbPosition(uint256 value) internal pure returns(uint8 position) {
assembly {
// value > 2*128 - 1
if gt(value,0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF) {
value := shr(128,value)
position := add(128,position)
}
// value > 2*64 - 1
if gt(value,0xFFFFFFFFFFFFFFFF) {
value := shr(64,value)
position := add(64,position)
}
// value > 2*32 - 1
if gt(value,0xFFFFFFFF) {
value := shr(32,value)
position := add(32,position)
}
// value > 2*16 - 1
if gt(value,0xFFFF) {
value := shr(16,value)
position := add(16,position)
}
// value > 2*8 - 1
if gt(value,0xFF) {
value := shr(8,value)
position := add(8,position)
}
// value > 2*4 - 1
if gt(value,0xF) {
value := shr(4,value)
position := add(4,position)
}
// value > 2*2 - 1
if gt(value,0x03) {
value := shr(2,value)
position := add(2,position)
}
// value > 2*1 - 1
if gt(value,0x01){
value := shr(1,value)
position := add(1,position)
}
}
}
}
@Vectorized
Copy link

            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))))

            x := shr(r, x)
            x := or(x, shr(1, x))
            x := or(x, shr(2, x))
            x := or(x, shr(4, x))
            x := or(x, shr(8, x))
            x := or(x, shr(16, x))

            r := or(r, byte(and(31, shr(27, mul(x, 0x07C4ACDD))), 
                0x0009010a0d15021d0b0e10121619031e080c141c0f111807131b17061a05041f))

@atarpara
Copy link
Author

@Vectorized awesome work. but still win solmate lib log2.

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