Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Array concat as function
// [A0, A1, ..., AN-1]
// Code(X) = 2^N - 1 + Sum(0, N - 1, Xi * 2^i)
// [B0, B1, ..., BM-1]
// Concat(A, B) = 2 ^ [floor(lg (N + 1)) + floor(lg (M + 1))] - 1 +
// Code(A) - (2 ^ N - 1) + Code(B) - (2 ^ M - 1)
// graph: http://www.wolframalpha.com/input/?i=plot+2+%5E+%28floor%28lg2+%28x+%2B+1%29%29+%2B+floor%28lg2+%28y+%2B+1%29%29%29+-+1+%2B+%28x+-+%282+%5E+floor%28lg2+%28x+%2B+1%29%29+-+1%29%29+*+%282+%5E+floor%28lg2+%28y+%2B+1%29%29%29+%2B+%28y+-+%282+%5E+floor%28lg2+%28y+%2B+1%29%29+-+1%29%29%2C+x%3D0..3%2C+y%3D0..3
var _ = require("underscore");
function to_int(array)
{
return Math.pow(2, array.length) - 1 + parseInt(array.join(""), 2);
}
function to_array(coded)
{
var length = Math.floor(Math.log (coded + 1) / Math.log(2));
var value = coded - (Math.pow(2, length) - 1);
var array = new Array(length);
var index = length;
while (index--)
{
array[length - index - 1] = Math.floor(value / Math.pow(2, index));
value -= array[length - index - 1] * Math.pow(2, index);
}
return array;
}
function add(lhs, rhs)
{
var lhsLength = Math.floor(Math.log (lhs + 1) / Math.log(2));
var rhsLength = Math.floor(Math.log (rhs + 1) / Math.log(2));
var lhsValue = lhs - (Math.pow(2, lhsLength) - 1);
var rhsValue = rhs - (Math.pow(2, rhsLength) - 1);
return Math.pow(2, lhsLength + rhsLength) - 1 + lhsValue * Math.pow(2, rhsLength) + rhsValue;
}
console.log("-> " + to_int( [0,1,1,0] ))
var lhs = [1,1,0,0];
var rhs = [1,0,1];
var lhsCoded = to_int(lhs);
var rhsCoded = to_int(rhs);
var resultCoded = add(lhsCoded, rhsCoded);
console.log(lhsCoded + " ( [" + to_array(lhsCoded) + "] ) + " + rhsCoded + " ( [" + to_array(rhsCoded) + "] ) = " + resultCoded + " ( [" + to_array(resultCoded) + "] ) ");
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment