Most Significant Bit

Most Significant Bit

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.19;

contract MostSignificantBit {
    /// 이분 탐색을 사용해 x의 최상위 비트를 찾는다
    function findMostSignificantBitBinarySearch(uint256 x) public pure returns(uint8 r) {
        if (x >= 2 ** 128) {
            x >>= 128;
            r += 128;
        }

        if (x >= 2 ** 64) {
            x >>= 64;
            r += 64;
        }

        if (x >= 2 ** 32) {
            x >>= 32;
            r += 32;
        }

        if (x >= 2 ** 16) {
            x >>= 16;
            r += 16;
        }

        if (x >= 2 ** 8) {
            x >>= 8;
            r += 8;
        }

        if (x >= 2 ** 4) {
            x >>= 4;
            r += 4;
        }

        if (x >= 2 ** 2) {
            x >>= 2;
            r += 2;
        }

        if (x >= 2) {
            r += 1;
        }
    }

    /// x를 2로 나누는 과정을 반복하여 x의 최상위 비트를 찾는다
    function findMostSignificantBitDivideByTwo(uint256 x) public pure returns(uint8 r) {
        for (; x > 1;) {
         r += 1;
         x /= 2;   
        }
    }

    /// 비트 연산자를 사용해 최상위 비트부터 비교하며 x의 최상위 비트를 찾는다
    function findMostSignificantBitFromLeftMost(uint256 x) public pure returns(uint8 r) {
        for (uint8 i = 255; i >= 0; i--) {
            if ((x >> i) & 1 == 1) {
                r = i;
                break;
            }
        }
    }
}

/* findMostSignificantBitBinarySearch */

[test case 1]
input: 115792089237316195423570985008687907853269984665640564039457584007913129639935
output: 255
execution cost: 2589 gas

[test case 2]
input: 1
output: 0
execution cost: 806 gas

[test case 3]
input: 340282366920938463463374607431768211456 
output: 128
execution cost: 1031 gas

/* findMostSignificantBitDivideByTwo */

[test case 1]
input: 115792089237316195423570985008687907853269984665640564039457584007913129639935
output: 255
excution cost: 111275 gas

[test case 2]
input: 1
output: 0
execution cost: 605 gas

[test case 3]
input: 340282366920938463463374607431768211456
output: 128
execution cost: 56157 gas

/* findMostSignificantBitFromLeftMost */

[test case 1]
input: 115792089237316195423570985008687907853269984665640564039457584007913129639935
output: 255
excution cost: 683 gas

[test case 2]
input: 1
output: 0
execution cost: 59078 gas

[test case 3]
input: 340282366920938463463374607431768211456
output: 128
execution cost: 29766 gas

Least Significant Bit

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.19;

contract LeastSignificantBit {
    function leastSignificantBit(uint256 x) public pure returns(uint8 r) {
        require(x > 0);

        r = 255;

        if (x & type(uint128).max > 0) {
            r -= 128;
        } else {
            x >>= 128;
        }

        if (x & type(uint64).max > 0) {
            r -= 64;
        } else {
            x >>= 64;
        }

        if (x & type(uint32).max > 0) {
            r -= 32;
        } else {
            x >>= 32;
        }

        if (x & type(uint16).max > 0) {
            r -= 16;
        } else {
            x >>= 16;
        }

        if (x & type(uint8).max > 0) {
            r -= 8;
        } else {
            x >>= 8;
        }

        if (x & 15 > 0) {
            r -= 4;
        } else {
            x >>= 4;
        }

        if (x & 3 > 0) {
            r -= 2;
        } else {
            x >>= 2;
        }

        if (x & 1 > 0) r -= 1;
    }
}

Reference

https://github.com/Uniswap/v3-core/blob/main/contracts/libraries/BitMath.sol
https://youtu.be/M6awK0lskR4