simple-squiggle

A restricted subset of Squiggle
Log | Files | Refs | README

bitwise.js (9129B)

      1 /**
      2  * Bitwise and for Bignumbers
      3  *
      4  * Special Cases:
      5  *   N &  n =  N
      6  *   n &  0 =  0
      7  *   n & -1 =  n
      8  *   n &  n =  n
      9  *   I &  I =  I
     10  *  -I & -I = -I
     11  *   I & -I =  0
     12  *   I &  n =  n
     13  *   I & -n =  I
     14  *  -I &  n =  0
     15  *  -I & -n = -I
     16  *
     17  * @param {BigNumber} x
     18  * @param {BigNumber} y
     19  * @return {BigNumber} Result of `x` & `y`, is fully precise
     20  * @private
     21  */
     22 export function bitAndBigNumber(x, y) {
     23   if (x.isFinite() && !x.isInteger() || y.isFinite() && !y.isInteger()) {
     24     throw new Error('Integers expected in function bitAnd');
     25   }
     26 
     27   var BigNumber = x.constructor;
     28 
     29   if (x.isNaN() || y.isNaN()) {
     30     return new BigNumber(NaN);
     31   }
     32 
     33   if (x.isZero() || y.eq(-1) || x.eq(y)) {
     34     return x;
     35   }
     36 
     37   if (y.isZero() || x.eq(-1)) {
     38     return y;
     39   }
     40 
     41   if (!x.isFinite() || !y.isFinite()) {
     42     if (!x.isFinite() && !y.isFinite()) {
     43       if (x.isNegative() === y.isNegative()) {
     44         return x;
     45       }
     46 
     47       return new BigNumber(0);
     48     }
     49 
     50     if (!x.isFinite()) {
     51       if (y.isNegative()) {
     52         return x;
     53       }
     54 
     55       if (x.isNegative()) {
     56         return new BigNumber(0);
     57       }
     58 
     59       return y;
     60     }
     61 
     62     if (!y.isFinite()) {
     63       if (x.isNegative()) {
     64         return y;
     65       }
     66 
     67       if (y.isNegative()) {
     68         return new BigNumber(0);
     69       }
     70 
     71       return x;
     72     }
     73   }
     74 
     75   return bitwise(x, y, function (a, b) {
     76     return a & b;
     77   });
     78 }
     79 /**
     80  * Bitwise not
     81  * @param {BigNumber} x
     82  * @return {BigNumber} Result of ~`x`, fully precise
     83  *
     84  */
     85 
     86 export function bitNotBigNumber(x) {
     87   if (x.isFinite() && !x.isInteger()) {
     88     throw new Error('Integer expected in function bitNot');
     89   }
     90 
     91   var BigNumber = x.constructor;
     92   var prevPrec = BigNumber.precision;
     93   BigNumber.config({
     94     precision: 1E9
     95   });
     96   var result = x.plus(new BigNumber(1));
     97   result.s = -result.s || null;
     98   BigNumber.config({
     99     precision: prevPrec
    100   });
    101   return result;
    102 }
    103 /**
    104  * Bitwise OR for BigNumbers
    105  *
    106  * Special Cases:
    107  *   N |  n =  N
    108  *   n |  0 =  n
    109  *   n | -1 = -1
    110  *   n |  n =  n
    111  *   I |  I =  I
    112  *  -I | -I = -I
    113  *   I | -n = -1
    114  *   I | -I = -1
    115  *   I |  n =  I
    116  *  -I |  n = -I
    117  *  -I | -n = -n
    118  *
    119  * @param {BigNumber} x
    120  * @param {BigNumber} y
    121  * @return {BigNumber} Result of `x` | `y`, fully precise
    122  */
    123 
    124 export function bitOrBigNumber(x, y) {
    125   if (x.isFinite() && !x.isInteger() || y.isFinite() && !y.isInteger()) {
    126     throw new Error('Integers expected in function bitOr');
    127   }
    128 
    129   var BigNumber = x.constructor;
    130 
    131   if (x.isNaN() || y.isNaN()) {
    132     return new BigNumber(NaN);
    133   }
    134 
    135   var negOne = new BigNumber(-1);
    136 
    137   if (x.isZero() || y.eq(negOne) || x.eq(y)) {
    138     return y;
    139   }
    140 
    141   if (y.isZero() || x.eq(negOne)) {
    142     return x;
    143   }
    144 
    145   if (!x.isFinite() || !y.isFinite()) {
    146     if (!x.isFinite() && !x.isNegative() && y.isNegative() || x.isNegative() && !y.isNegative() && !y.isFinite()) {
    147       return negOne;
    148     }
    149 
    150     if (x.isNegative() && y.isNegative()) {
    151       return x.isFinite() ? x : y;
    152     }
    153 
    154     return x.isFinite() ? y : x;
    155   }
    156 
    157   return bitwise(x, y, function (a, b) {
    158     return a | b;
    159   });
    160 }
    161 /**
    162  * Applies bitwise function to numbers
    163  * @param {BigNumber} x
    164  * @param {BigNumber} y
    165  * @param {function (a, b)} func
    166  * @return {BigNumber}
    167  */
    168 
    169 export function bitwise(x, y, func) {
    170   var BigNumber = x.constructor;
    171   var xBits, yBits;
    172   var xSign = +(x.s < 0);
    173   var ySign = +(y.s < 0);
    174 
    175   if (xSign) {
    176     xBits = decCoefficientToBinaryString(bitNotBigNumber(x));
    177 
    178     for (var i = 0; i < xBits.length; ++i) {
    179       xBits[i] ^= 1;
    180     }
    181   } else {
    182     xBits = decCoefficientToBinaryString(x);
    183   }
    184 
    185   if (ySign) {
    186     yBits = decCoefficientToBinaryString(bitNotBigNumber(y));
    187 
    188     for (var _i = 0; _i < yBits.length; ++_i) {
    189       yBits[_i] ^= 1;
    190     }
    191   } else {
    192     yBits = decCoefficientToBinaryString(y);
    193   }
    194 
    195   var minBits, maxBits, minSign;
    196 
    197   if (xBits.length <= yBits.length) {
    198     minBits = xBits;
    199     maxBits = yBits;
    200     minSign = xSign;
    201   } else {
    202     minBits = yBits;
    203     maxBits = xBits;
    204     minSign = ySign;
    205   }
    206 
    207   var shortLen = minBits.length;
    208   var longLen = maxBits.length;
    209   var expFuncVal = func(xSign, ySign) ^ 1;
    210   var outVal = new BigNumber(expFuncVal ^ 1);
    211   var twoPower = new BigNumber(1);
    212   var two = new BigNumber(2);
    213   var prevPrec = BigNumber.precision;
    214   BigNumber.config({
    215     precision: 1E9
    216   });
    217 
    218   while (shortLen > 0) {
    219     if (func(minBits[--shortLen], maxBits[--longLen]) === expFuncVal) {
    220       outVal = outVal.plus(twoPower);
    221     }
    222 
    223     twoPower = twoPower.times(two);
    224   }
    225 
    226   while (longLen > 0) {
    227     if (func(minSign, maxBits[--longLen]) === expFuncVal) {
    228       outVal = outVal.plus(twoPower);
    229     }
    230 
    231     twoPower = twoPower.times(two);
    232   }
    233 
    234   BigNumber.config({
    235     precision: prevPrec
    236   });
    237 
    238   if (expFuncVal === 0) {
    239     outVal.s = -outVal.s;
    240   }
    241 
    242   return outVal;
    243 }
    244 /* Extracted from decimal.js, and edited to specialize. */
    245 
    246 function decCoefficientToBinaryString(x) {
    247   // Convert to string
    248   var a = x.d; // array with digits
    249 
    250   var r = a[0] + '';
    251 
    252   for (var i = 1; i < a.length; ++i) {
    253     var s = a[i] + '';
    254 
    255     for (var z = 7 - s.length; z--;) {
    256       s = '0' + s;
    257     }
    258 
    259     r += s;
    260   }
    261 
    262   var j = r.length;
    263 
    264   while (r.charAt(j) === '0') {
    265     j--;
    266   }
    267 
    268   var xe = x.e;
    269   var str = r.slice(0, j + 1 || 1);
    270   var strL = str.length;
    271 
    272   if (xe > 0) {
    273     if (++xe > strL) {
    274       // Append zeros.
    275       xe -= strL;
    276 
    277       while (xe--) {
    278         str += '0';
    279       }
    280     } else if (xe < strL) {
    281       str = str.slice(0, xe) + '.' + str.slice(xe);
    282     }
    283   } // Convert from base 10 (decimal) to base 2
    284 
    285 
    286   var arr = [0];
    287 
    288   for (var _i2 = 0; _i2 < str.length;) {
    289     var arrL = arr.length;
    290 
    291     while (arrL--) {
    292       arr[arrL] *= 10;
    293     }
    294 
    295     arr[0] += parseInt(str.charAt(_i2++)); // convert to int
    296 
    297     for (var _j = 0; _j < arr.length; ++_j) {
    298       if (arr[_j] > 1) {
    299         if (arr[_j + 1] === null || arr[_j + 1] === undefined) {
    300           arr[_j + 1] = 0;
    301         }
    302 
    303         arr[_j + 1] += arr[_j] >> 1;
    304         arr[_j] &= 1;
    305       }
    306     }
    307   }
    308 
    309   return arr.reverse();
    310 }
    311 /**
    312  * Bitwise XOR for BigNumbers
    313  *
    314  * Special Cases:
    315  *   N ^  n =  N
    316  *   n ^  0 =  n
    317  *   n ^  n =  0
    318  *   n ^ -1 = ~n
    319  *   I ^  n =  I
    320  *   I ^ -n = -I
    321  *   I ^ -I = -1
    322  *  -I ^  n = -I
    323  *  -I ^ -n =  I
    324  *
    325  * @param {BigNumber} x
    326  * @param {BigNumber} y
    327  * @return {BigNumber} Result of `x` ^ `y`, fully precise
    328  *
    329  */
    330 
    331 
    332 export function bitXor(x, y) {
    333   if (x.isFinite() && !x.isInteger() || y.isFinite() && !y.isInteger()) {
    334     throw new Error('Integers expected in function bitXor');
    335   }
    336 
    337   var BigNumber = x.constructor;
    338 
    339   if (x.isNaN() || y.isNaN()) {
    340     return new BigNumber(NaN);
    341   }
    342 
    343   if (x.isZero()) {
    344     return y;
    345   }
    346 
    347   if (y.isZero()) {
    348     return x;
    349   }
    350 
    351   if (x.eq(y)) {
    352     return new BigNumber(0);
    353   }
    354 
    355   var negOne = new BigNumber(-1);
    356 
    357   if (x.eq(negOne)) {
    358     return bitNotBigNumber(y);
    359   }
    360 
    361   if (y.eq(negOne)) {
    362     return bitNotBigNumber(x);
    363   }
    364 
    365   if (!x.isFinite() || !y.isFinite()) {
    366     if (!x.isFinite() && !y.isFinite()) {
    367       return negOne;
    368     }
    369 
    370     return new BigNumber(x.isNegative() === y.isNegative() ? Infinity : -Infinity);
    371   }
    372 
    373   return bitwise(x, y, function (a, b) {
    374     return a ^ b;
    375   });
    376 }
    377 /**
    378  * Bitwise left shift
    379  *
    380  * Special Cases:
    381  *  n << -n = N
    382  *  n <<  N = N
    383  *  N <<  n = N
    384  *  n <<  0 = n
    385  *  0 <<  n = 0
    386  *  I <<  I = N
    387  *  I <<  n = I
    388  *  n <<  I = I
    389  *
    390  * @param {BigNumber} x
    391  * @param {BigNumber} y
    392  * @return {BigNumber} Result of `x` << `y`
    393  *
    394  */
    395 
    396 export function leftShiftBigNumber(x, y) {
    397   if (x.isFinite() && !x.isInteger() || y.isFinite() && !y.isInteger()) {
    398     throw new Error('Integers expected in function leftShift');
    399   }
    400 
    401   var BigNumber = x.constructor;
    402 
    403   if (x.isNaN() || y.isNaN() || y.isNegative() && !y.isZero()) {
    404     return new BigNumber(NaN);
    405   }
    406 
    407   if (x.isZero() || y.isZero()) {
    408     return x;
    409   }
    410 
    411   if (!x.isFinite() && !y.isFinite()) {
    412     return new BigNumber(NaN);
    413   } // Math.pow(2, y) is fully precise for y < 55, and fast
    414 
    415 
    416   if (y.lt(55)) {
    417     return x.times(Math.pow(2, y.toNumber()) + '');
    418   }
    419 
    420   return x.times(new BigNumber(2).pow(y));
    421 }
    422 /*
    423  * Special Cases:
    424  *   n >> -n =  N
    425  *   n >>  N =  N
    426  *   N >>  n =  N
    427  *   I >>  I =  N
    428  *   n >>  0 =  n
    429  *   I >>  n =  I
    430  *  -I >>  n = -I
    431  *  -I >>  I = -I
    432  *   n >>  I =  I
    433  *  -n >>  I = -1
    434  *   0 >>  n =  0
    435  *
    436  * @param {BigNumber} value
    437  * @param {BigNumber} value
    438  * @return {BigNumber} Result of `x` >> `y`
    439  *
    440  */
    441 
    442 export function rightArithShiftBigNumber(x, y) {
    443   if (x.isFinite() && !x.isInteger() || y.isFinite() && !y.isInteger()) {
    444     throw new Error('Integers expected in function rightArithShift');
    445   }
    446 
    447   var BigNumber = x.constructor;
    448 
    449   if (x.isNaN() || y.isNaN() || y.isNegative() && !y.isZero()) {
    450     return new BigNumber(NaN);
    451   }
    452 
    453   if (x.isZero() || y.isZero()) {
    454     return x;
    455   }
    456 
    457   if (!y.isFinite()) {
    458     if (x.isNegative()) {
    459       return new BigNumber(-1);
    460     }
    461 
    462     if (!x.isFinite()) {
    463       return new BigNumber(NaN);
    464     }
    465 
    466     return new BigNumber(0);
    467   } // Math.pow(2, y) is fully precise for y < 55, and fast
    468 
    469 
    470   if (y.lt(55)) {
    471     return x.div(Math.pow(2, y.toNumber()) + '').floor();
    472   }
    473 
    474   return x.div(new BigNumber(2).pow(y)).floor();
    475 }