' Bit Manipulation via Inline ASM — BSF, BSR, BSWAP, and PB popcount
#COMPILE EXE
#DIM ALL

FUNCTION BitScanForward(n AS LONG) AS LONG
    LOCAL idx AS LONG
    idx = -1
'     #ASM
'         mov eax, %n
'         bsf eax, eax
'         mov %idx, eax
'     #ENDASM
    FUNCTION = idx
END FUNCTION

FUNCTION BitScanReverse(n AS LONG) AS LONG
    LOCAL idx AS LONG
    idx = -1
'     #ASM
'         mov eax, %n
'         bsr eax, eax
'         mov %idx, eax
'     #ENDASM
    FUNCTION = idx
END FUNCTION

FUNCTION PopCountPB(n AS LONG) AS LONG
    LOCAL cnt AS LONG
    cnt = 0
    WHILE n
        n = n AND (n - 1)
        INCR cnt
    WEND
    FUNCTION = cnt
END FUNCTION

FUNCTION PopCountLookup(n AS LONG) AS LONG
    LOCAL cnt AS LONG
    LOCAL x AS LONG
    x = n
    cnt = 0
    WHILE x <> 0
        x = x AND (x - 1)
        cnt = cnt + 1
    WEND
    FUNCTION = cnt
END FUNCTION

FUNCTION IsPowerOfTwo(n AS LONG) AS LONG
    IF n > 0 THEN
        IF (n AND (n - 1)) = 0 THEN FUNCTION = 1
    END IF
END FUNCTION

FUNCTION NextPowerOfTwo(n AS LONG) AS LONG
    IF n <= 0 THEN FUNCTION = 1: EXIT FUNCTION
    DECR n
    n = n OR ((n \ 2))
    n = n OR ((n \ 4))
    n = n OR ((n \ 16))
    n = n OR ((n \ 256))
    n = n OR ((n \ 65536))
    INCR n
    FUNCTION = n
END FUNCTION

FUNCTION ReverseBitsBSwap(n AS LONG) AS LONG
'     #ASM
'         mov eax, %n
'         bswap eax
'         mov %n, eax
'     #ENDASM
    FUNCTION = n
END FUNCTION

FUNCTION LeadingZeros(n AS LONG) AS LONG
    IF n = 0 THEN FUNCTION = 32: EXIT FUNCTION
    FUNCTION = 31 - BitScanReverse(n)
END FUNCTION

FUNCTION Parity(n AS LONG) AS LONG
    LOCAL p AS LONG
    p = 0
    WHILE n
        p = p XOR (n AND 1)
        n = (n \ 2)
    WEND
    FUNCTION = p
END FUNCTION

FUNCTION GCD(BYVAL a AS LONG, BYVAL b AS LONG) AS LONG
    LOCAL tmp AS LONG
    WHILE b
        tmp = b
        b = a MOD b
        a = tmp
    WEND
    FUNCTION = a
END FUNCTION

FUNCTION IsPrime(n AS LONG) AS LONG
    LOCAL i AS LONG
    IF n < 2 THEN FUNCTION = 0: EXIT FUNCTION
    IF (n AND 1) = 0 THEN FUNCTION = (n = 2): EXIT FUNCTION
    i = 3
    WHILE i * i <= n
        IF (n MOD i) = 0 THEN FUNCTION = 0: EXIT FUNCTION
        i = i + 2
    WEND
    FUNCTION = 1
END FUNCTION

FUNCTION PBMAIN() AS LONG
    LOCAL i AS LONG

    PRINT "Bit Manipulation Demo"
    PRINT "====================="
    PRINT ""

    i = 42
    PRINT "Value: "; i; " binary: "; BIN$(i)
    PRINT "  BSF (first set bit): "; BitScanForward(i)
    PRINT "  BSR (last set bit):  "; BitScanReverse(i)
    PRINT "  PopCount (method 1): "; PopCountPB(i)
    PRINT "  PopCount (method 2): "; PopCountLookup(i)
    PRINT "  IsPowerOfTwo: "; IsPowerOfTwo(i)
    PRINT "  NextPowerOfTwo: "; NextPowerOfTwo(i)
    PRINT "  LeadingZeros: "; LeadingZeros(i)
    PRINT "  Parity: "; Parity(i)
    PRINT ""

    i = 256
    PRINT "Value: "; i; " binary: "; BIN$(i)
    PRINT "  IsPowerOfTwo: "; IsPowerOfTwo(i)
    PRINT "  NextPowerOfTwo: "; NextPowerOfTwo(i)
    PRINT "  BSF: "; BitScanForward(i)
    PRINT "  BSR: "; BitScanReverse(i)
    PRINT ""

    i = &H0F0F0F0F
    PRINT "Value: "; HEX$(i); "h binary: "; BIN$(i)
    PRINT "  PopCount: "; PopCountPB(i)
    PRINT "  ReverseBits (BSWAP): "; HEX$(ReverseBitsBSwap(i)); "h"
    PRINT ""

    PRINT "Prime numbers up to 50:"
    FOR i = 2 TO 50
        IF IsPrime(i) THEN PRINT "  "; i;
    NEXT i
    PRINT ""
    PRINT ""

    PRINT "GCD of 48 and 18: "; GCD(48, 18)
    PRINT "GCD of 100 and 35: "; GCD(100, 35)
    PRINT ""

    PRINT "All bit manipulation tests completed."

    FUNCTION = 0
END FUNCTION
