Eccelerators.BitTwiddling

src/counting/BitScanning.lvt

namespace Eccelerators.BitTwiddling.Counting

/**
 * Locates significant bits and zero runs in unsigned 32-bit values.
 *
 * Bit positions use the least-significant-bit convention: bit 0 is the low
 * bit and bit 31 is the high bit. Functions that cannot identify a set bit in
 * zero return the documented sentinel rather than an ambiguous valid index.
 */
class BitScanning
{
    /**
     * Counts consecutive zero bits from bit 31 toward bit 0.
     *
     * The result ranges from 0 through 32. A zero input returns 32.
     */
    public static fn CountLeadingZeros[](value: uint) int
    {
        if (value == (0 as uint))
        {
            return 32
        }

        var workingValue: uint = value
        var count: int = 0

        if (workingValue <= (0x0000FFFF as uint))
        {
            workingValue = workingValue << 16
            count = count + 16
        }
        if (workingValue <= (0x00FFFFFF as uint))
        {
            workingValue = workingValue << 8
            count = count + 8
        }
        if (workingValue <= (0x0FFFFFFF as uint))
        {
            workingValue = workingValue << 4
            count = count + 4
        }
        if (workingValue <= (0x3FFFFFFF as uint))
        {
            workingValue = workingValue << 2
            count = count + 2
        }
        if (workingValue <= (0x7FFFFFFF as uint))
        {
            count = count + 1
        }

        return count
    }

    /**
     * Returns the index of value's most-significant set bit.
     *
     * Valid indices range from 0 through 31. A zero input returns -1.
     */
    public static fn HighestSetBit[](value: uint) int
    {
        if (value == (0 as uint))
        {
            return -1
        }

        var workingValue: uint = value
        var result: int = 0
        while (workingValue > (1 as uint))
        {
            workingValue = workingValue >> 1
            result = result + 1
        }
        return result
    }

    /**
     * Returns the index of value's least-significant set bit.
     *
     * Valid indices range from 0 through 31. A zero input returns -1.
     */
    public static fn LowestSetBit[](value: uint) int
    {
        if (value == (0 as uint))
        {
            return -1
        }

        var workingValue: uint = value
        var result: int = 0
        while ((workingValue & (1 as uint)) == (0 as uint))
        {
            workingValue = workingValue >> 1
            result = result + 1
        }
        return result
    }

    /**
     * Returns floor(log2(value)), which is also the highest set-bit index.
     *
     * Positive inputs return a result from 0 through 31. Zero returns -1.
     * This implementation uses a fixed five-stage binary search.
     */
    public static fn Log2Floor[](value: uint) int
    {
        if (value == (0 as uint))
        {
            return -1
        }

        var workingValue: uint = value
        var result: int = 0

        if (workingValue >= (0x00010000 as uint))
        {
            workingValue = workingValue >> 16
            result = result + 16
        }
        if (workingValue >= (0x00000100 as uint))
        {
            workingValue = workingValue >> 8
            result = result + 8
        }
        if (workingValue >= (0x00000010 as uint))
        {
            workingValue = workingValue >> 4
            result = result + 4
        }
        if (workingValue >= (0x00000004 as uint))
        {
            workingValue = workingValue >> 2
            result = result + 2
        }
        if (workingValue >= (0x00000002 as uint))
        {
            result = result + 1
        }

        return result
    }

    /**
     * Counts consecutive zero bits from bit 0 toward bit 31.
     *
     * The result ranges from 0 through 32. A zero input returns 32.
     */
    public static fn CountTrailingZeros[](value: uint) int
    {
        if (value == (0 as uint))
        {
            return 32
        }

        var workingValue: uint = value
        var count: int = 0

        if ((workingValue & (0x0000FFFF as uint)) == (0 as uint))
        {
            workingValue = workingValue >> 16
            count = count + 16
        }
        if ((workingValue & (0x000000FF as uint)) == (0 as uint))
        {
            workingValue = workingValue >> 8
            count = count + 8
        }
        if ((workingValue & (0x0000000F as uint)) == (0 as uint))
        {
            workingValue = workingValue >> 4
            count = count + 4
        }
        if ((workingValue & (0x00000003 as uint)) == (0 as uint))
        {
            workingValue = workingValue >> 2
            count = count + 2
        }
        if ((workingValue & (1 as uint)) == (0 as uint))
        {
            count = count + 1
        }

        return count
    }
}