File Explorer

1/**2 * Mnemonist Bitwise Helpers3 * ==========================4 *5 * Miscellaneous helpers helping with bitwise operations.6 */7 8/**9 * Takes a 32 bits integer and returns its MSB using SWAR strategy.10 *11 * @param  {number} x - Target number.12 * @return {number}13 */14function msb32(x) {15  x |= (x >> 1);16  x |= (x >> 2);17  x |= (x >> 4);18  x |= (x >> 8);19  x |= (x >> 16);20 21  return (x & ~(x >> 1));22}23exports.msb32 = msb32;24 25/**26 * Takes a byte and returns its MSB using SWAR strategy.27 *28 * @param  {number} x - Target number.29 * @return {number}30 */31function msb8(x) {32  x |= (x >> 1);33  x |= (x >> 2);34  x |= (x >> 4);35 36  return (x & ~(x >> 1));37}38exports.msb8 = msb8;39 40/**41 * Takes a number and return bit at position.42 *43 * @param  {number} x   - Target number.44 * @param  {number} pos - Position.45 * @return {number}46 */47exports.test = function(x, pos) {48  return (x >> pos) & 1;49};50 51/**52 * Compare two bytes and return their critical bit.53 *54 * @param  {number} a - First byte.55 * @param  {number} b - Second byte.56 * @return {number}57 */58exports.criticalBit8 = function(a, b) {59  return msb8(a ^ b);60};61 62exports.criticalBit8Mask = function(a, b) {63  return (~msb8(a ^ b) >>> 0) & 0xff;64};65 66exports.testCriticalBit8 = function(x, mask) {67  return (1 + (x | mask)) >> 8;68};69 70exports.criticalBit32Mask = function(a, b) {71  return (~msb32(a ^ b) >>> 0) & 0xffffffff;72};73 74/**75 * Takes a 32 bits integer and returns its population count (number of 1 of76 * the binary representation).77 *78 * @param  {number} x - Target number.79 * @return {number}80 */81exports.popcount = function(x) {82  x -= x >> 1 & 0x55555555;83  x = (x & 0x33333333) + (x >> 2 & 0x33333333);84  x = x + (x >> 4) & 0x0f0f0f0f;85  x += x >> 8;86  x += x >> 16;87  return x & 0x7f;88};89 90/**91 * Slightly faster popcount function based on a precomputed table of 8bits92 * words.93 *94 * @param  {number} x - Target number.95 * @return {number}96 */97var TABLE8 = new Uint8Array(Math.pow(2, 8));98 99for (var i = 0, l = TABLE8.length; i < l; i++)100  TABLE8[i] = exports.popcount(i);101 102exports.table8Popcount = function(x) {103  return (104    TABLE8[x & 0xff] +105    TABLE8[(x >> 8) & 0xff] +106    TABLE8[(x >> 16) & 0xff] +107    TABLE8[(x >> 24) & 0xff]108  );109};110