W9D3_examples.js

//2^5 == 32 == 100000
//2^5-1 == 31 == 11111
//Powers of two (2^n) are 1 followed by n zeroes.
//Mersenne numbers (2^n-1) are n ones.

//Negate an integer using Two's Complement
function negate(int) {
    return ~int + 1;
}

//Bit-wise AND on an integer
function is_even(int) {
    return (int & 1) == 0;
}
//This can potentially be much faster than division IF (and only if) the number
//is being stored as an integer, which is not normally the case in JavaScript.
//Some optimizing interpreters may be able to take advantage of this; others
//may not. Tested by @rosuav using Node v4.3.1 on Debian Linux; performance was
//statistically indistinguishable from the equivalent using modulo-two.
//Even if there is a difference, most optimizing interpreters will recognize
//that "n % 2" is identical to "n & 1", and do the bitwise operation, so you'll
//be unable to see a difference most of the time. But in theory, looking at the
//lowest bit of a number is faster than dividing and checking the remainder, in
//the same way that you (as a human) can easily see what the last digit of some
//number is, but would have more difficulty dividing by 7 and seeing what's
//left.

function and_and_or(n, m) {
    console.log(n, "and", m, "=", n & m);
    console.log(n, "or", m, "=", n | m);
}

function bitwise(n, m, op) {
    switch (op) {
        case 'and': case 'AND':
            console.log(n, "and", m, "=", n & m);
            break;
        case 'or': case 'OR':
            console.log(n, "or", m, "=", n | m);
            break;
        case 'xor': case 'XOR':
            console.log(n, "xor", m, "=", n ^ m);
            break;
    }
}

//Bitwise inversion (NOT) will look very similar to the negation above, for
//obvious reasons. If you use values greater than 2147483647 (2^31-1), they'll
//first be coalesced to 32-bit integer, possibly making them negative. This may
//produce extremely surprising values; basically, don't use JavaScript's Number
//type for any integer greater than 2147483647 (or less than -2147483648) if
//you're doing bitwise operations.

//With the bit manipulation functions below, it is assumed that bits are
//numbered from the right hand side (the lowest values), and that they are
//numbered from zero. Thus the least significant bit is the zeroth bit, the
//following bit is the first bit (the 2s place), and so on. You may choose
//another definition if you wish - eg numbering the LSB as the "first" - on
//condition you can justify it logically.

function set_third_bit(n) {
    return n | 8;
}

function toggle_third_bit(n) {
    return n ^ 8;
}

function clear_third_bit(n) {
    return n & (~8);
}

function is_third_bit_set(n) {
    return (n & 8) == 8;
}

function leftshift(n, m) {
    return n << m;
}
function leftshift_verify(n, m) {
    var shift = n << m;
    var mul = n;
    for (var i = 0; i < m; ++i) mul *= 2;
    console.log("Bit shift: " + shift);
    console.log("Multiply:  " + mul);
    console.log("Mul/cast:  " + (mul|0));
    mul %= 4294967296;
    console.log("Mul/trunc: " + mul);
    if (mul > 2147483647) mul -= 4294967296;
    console.log("MT signed: " + mul);
}
//Note that multiplying and truncating to 32 bits will always produce a
//positive result, whereas the bit shift yields a signed result. Anything
//greater than 2147483647 will appear negative after the bit shift. Thus
//the last step in the verification is to force the result to be a signed
//integer, all of which results in the same as multiplying and casting to
//integer (via the "|0" trick).

function rightshift(n, m) {
    return n >> m;
}
function rightshift_verify(n, m) {
    var shift = n >> m;
    var zshift = n >>> m;
    var div = n;
    for (var i = 0; i < m; ++i) div /= 2;
    div = Math.floor(div);
    console.log("Bit shift: " + shift);
    console.log("ZF shift:  " + zshift);
    console.log("Divide:    " + div);
}
//Minor details of the specs are left as exercises for the reader.

//All of the below functions assume that the numbers concerned can be
//represented as 32-bit integers.

function double_by_shifting(n) {
    return n<<1;
}

function quadruple_by_shifting(n) {
    return n<<2;
}

function halve_by_shifting(n) {
    return n>>1;
}

function two_to_the_nth(n) {
    return 1<<n;
}

var morton = function(a, b) {
    var out = 0;
    for (var i=0; i<8; i++) {
        out |= (a & (1 << i)) << i;
        out |= (b & (1 << i)) << (i + 1);
    }
    return out;
};