Miscellaneous Code Examples

Perfect Numbers

A perfect number is an integer that is equal to the sum of its positive proper divisors, that is, divisors excluding the number itself. For instance, 6 has proper divisors 1, 2, and 3, and 1 + 2 + 3 = 6, so 6 is a perfect number. The next perfect number is 28, because 1 + 2 + 4 + 7 + 14 = 28.

We can create a function to determine if a number is perfect or not. Add up all the factors of the number, and if the sum of all factors is equal to the number, then return true.

#import "Basic";

is_perfect :: (n: int) -> bool {
    if n <= 1 return false;

    sum := 1;
    for i: 2..n/2 + 1 {
        if n % i == 0 {
            sum += i;
        }
    }

    return sum == n;
}

main :: () {
    for i: 1..10000 {
        if is_perfect(i) {
            print("% is a perfect number.\n", i);
        }
    }
}

XOR Swap

The XOR swap is an algorithm that uses the XOR bitwise operation to swap the values of two variables without using the temporary variable which is normally required.

#import "Basic";

main :: () {
    a := 5;
    b := 9;

    print("Before swap: a = %, b = %\n", a, b);

    // XOR swap
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;

    print("After swap:  a = %, b = %\n", a, b);
}

Palindrome

A palindrome is a word, number, phrase, or other sequence of symbols that reads the same backwards as forwards. This is a function to compute whether a string is a palindrome.

#import "Basic";
#import "String";

is_palindrome :: (s: string) -> bool {
    left := 0;
    right := s.count - 1;

    while left < right {
        if s[left] != s[right] return false;
        left += 1;
        right -= 1;
    }

    return true;
}

main :: () {
    words := string.[ "racecar", "hello", "level", "banana", "madam" ];

    for word: words {
        if is_palindrome(word)
            print("\"%\" is a palindrome.\n", word);
        else
            print("\"%\" is not a palindrome.\n", word);
    }
}

Bit Scan Forward

A bit scan forward implementation using De Bruijn Multiplication based off of this implementation.

index64 :: int.[
     0,    1,   48,    2,   57,   49,   28,    3,
    61,   58,   50,   42,   38,   29,   17,    4,
    62,   55,   59,   36,   53,   51,   43,   22,
    45,   39,   33,   30,   24,   18,   12,    5,
    63,   47,   56,   27,   60,   41,   37,   16,
    54,   35,   52,   21,   44,   32,   23,   11,
    46,   26,   40,   15,   34,   20,   31,   10,
    25,   14,   19,    9,   13,    8,    7,    6,
];

bit_scan_forward :: (value: u64) -> int {
    DEBRUIJN64 : u64 : 0x03f79d71b4cb0a89;
    value = value & (cast,no_check(u64) -(cast(int)value));
    return index64[ (value * DEBRUIJN64) >> 58];
}