/**
* Created by kudelin on 19.11.13.
*/
var BIG_BINARY = BIG_BINARY || {};
/**
* Класс n бинарного числа
* @param binaryString - строковое представление числа либо массив из 0 и 1
* @constructor
*/
BIG_BINARY.BinaryArrayNumber = function(binaryString) {
this.number = new Array(); // внутреннее представление числа
if (binaryString) {
this.setNumber = binaryString;
}
};
BIG_BINARY.BinaryArrayNumber.prototype = {
set setNumber(binaryValue) {
if (binaryValue) {
this.number.length = 0;
if (!Array.isArray(binaryValue)) {
for (var i = 0; i < binaryValue.length; i++) {
this.number.push(Number(binaryValue[i]));
}
} else {
this.number = binaryValue.concat();
}
}
},
get getBitArray() {
return new Array().concat(this.number);
},
toString: function() {
return this.number.join("");
}
};
/**
* Сумирует два n - бинарных числа
* @param binaryArrayNumber1
* @param binaryArrayNumber2
* @returns {BIG_BINARY.BinaryArrayNumber} - Сумма
*/
BIG_BINARY.BinaryArrayNumber.sum = function(binaryArrayNumber1, binaryArrayNumber2) {
/**
* Складывает два бита и запоминиает результат при переполнении, который учитывается при следующем вызове
* @param bit1
* @param bit2
* @returns {number} - результат сложения
*/
var getSumBitNumber = function(bit1, bit2) {
this.lastResult = this.lastResult || 0; // хранит возникающий при переполнении бит от предыдущего вызова
var intValue = bit1 + bit2 + this.lastResult;
this.lastResult = Math.floor(intValue / 2);
return intValue % 2;
};
/**
* Выравнивает массивы, дополняя нулями
* @param array1
* @param array2
*/
var alignmentArray = function(array1, array2) {
while (array1.length > array2.length) {
array2.push(0);
}
while (array2.length > array1.length) {
array1.push(0);
}
}
var binaryArray1 = binaryArrayNumber1.getBitArray.reverse(); // преворачиваем, чтобы работать с концом массива
var binaryArray2 = binaryArrayNumber2.getBitArray.reverse(); // чтобы не раздвигать его
alignmentArray(binaryArray1, binaryArray2);
var sumBinaryArray = new Array();
for (var i = 0, len = binaryArray1.length; i < len; i++) {
sumBinaryArray.push(getSumBitNumber(binaryArray1[i], binaryArray2[i]));
}
sumBinaryArray.push(getSumBitNumber(0,0)); // получить бит, возникающий при переполнении от последнего вызова
sumBinaryArray.reverse(); // вернуть исходный порядок
return new BIG_BINARY.BinaryArrayNumber(sumBinaryArray);
};
var num1 = new BIG_BINARY.BinaryArrayNumber("101101010010101010110101011010101011101010101001101");
var num2 = new BIG_BINARY.BinaryArrayNumber("100101011010001001010110101001010101111110101001011");
var sumNum = BIG_BINARY.BinaryArrayNumber.sum(num1, num2);
console.log(num1.toString());
console.log(num2.toString());
console.log(sumNum.toString());
// 101101010010101010110101011010101011101010101001101
// 100101011010001001010110101001010101111110101001011
// 1010010101100110100001100000100000001101001010011000
/*Просчет времени выполнения:
с1*n1/2 + c1*n2/2 + c2*|n1 - n2| + c3 + c4*n + c4 + c1*n/2 + c5
при n1 = n2
c1*3*n/2 + c3 + c4 + c5 + c4*n = C + n*(c1*3/2 + c4) -> O(n)
c1 - reverse
c2 - alignmentArray
c3 - new Array()
c4 - getSumBitNumber()
c5 - new BIG_BINARY.BinaryArrayNumber(sumBinaryArray) - конст, т.к. передается массив
*/
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.