3e:null 3f:["$","title",null,{"children":"bitset | Luvoy | Observable"}] 45:T78a,{/** * Parses the parameters and set variable P * * @param {Object} P * @param {string|BitSet|Array|Uint8Array|number=} val */ function parse(P, val) { if (val == null) { P['data'] = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; P['_'] = 0; return; } if (val instanceof BitSet) { P['data'] = val['data']; P['_'] = val['_']; return; } switch (typeof val) { case 'number': P['data'] = [val | 0]; P['_'] = 0; break; case 'string': var base = 2; var len = WORD_LENGTH; if (val.indexOf('0b') === 0) { val = val.substr(2); } else if (val.indexOf('0x') === 0) { val = val.substr(2); base = 16; len = 8; } P['data'] = []; P['_'] = 0; var a = val.length - len; var b = val.length; do { var num = parseInt(val.slice(a > 0 ? a : 0, b), base); if (isNaN(num)) { throw SyntaxError('Invalid param'); } P['data'].push(num | 0); if (a <= 0) break; a -= len; b -= len; } while (1); break; default: P['data'] = [0]; var data = P['data']; if (val instanceof Array) { for (var i = val.length - 1; i >= 0; i--) { var ndx = val[i]; if (ndx === Infinity) { P['_'] = -1; } else { scale(P, ndx); data[ndx >>> WORD_LOG] |= 1 << ndx; } } break; } if (Uint8Array && val instanceof Uint8Array) { var bits = 8; scale(P, val.length * bits); for (var i = 0; i < val.length; i++) { var n = val[i]; for (var j = 0; j < bits; j++) { var k = i * bits + j; data[k >>> WORD_LOG] |= (n >> j & 1) << k; } } break; } throw SyntaxError('Invalid param'); } } return parse }46:T3ad3,BitSet.prototype = ({ 'data': [], '_': 0, /** * Set a single bit flag * * Ex: * bs1 = new BitSet(10); * * bs1.set(3, 1); * * @param {number} ndx The index of the bit to be set * @param {number=} value Optional value that should be set on the index (0 or 1) * @returns {BitSet} this */ 'set': function(ndx, value) { ndx |= 0; scale(this, ndx); if (value === undefined || value) { this['data'][ndx >>> WORD_LOG] |= (1 << ndx); } else { this['data'][ndx >>> WORD_LOG] &= ~(1 << ndx); } return this; }, /** * Get a single bit flag of a certain bit position * * Ex: * bs1 = new BitSet(); * var isValid = bs1.get(12); * * @param {number} ndx the index to be fetched * @returns {number} The binary flag */ 'get': function(ndx) { ndx |= 0; var d = this['data']; var n = ndx >>> WORD_LOG; if (n >= d.length) { return this['_'] & 1; } return (d[n] >>> ndx) & 1; }, /** * Creates the bitwise NOT of a set. * * Ex: * bs1 = new BitSet(10); * * res = bs1.not(); * * @returns {BitSet} A new BitSet object, containing the bitwise NOT of this */ 'not': function() { // invert() var t = this['clone'](); var d = t['data']; for (var i = 0; i < d.length; i++) { d[i] = ~d[i]; } t['_'] = ~t['_']; return t; }, /** * Creates the bitwise AND of two sets. * * Ex: * bs1 = new BitSet(10); * bs2 = new BitSet(10); * * res = bs1.and(bs2); * * @param {BitSet} value A bitset object * @returns {BitSet} A new BitSet object, containing the bitwise AND of this and value */ 'and': function(value) {// intersection parse(P, value); var T = this['clone'](); var t = T['data']; var p = P['data']; var pl = p.length; var p_ = P['_']; var t_ = T['_']; // If this is infinite, we need all bits from P if (t_ !== 0) { scale(T, pl * WORD_LENGTH - 1); } var tl = t.length; var l = Math.min(pl, tl); var i = 0; for (; i < l; i++) { t[i] &= p[i]; } for (; i < tl; i++) { t[i] &= p_; } T['_'] &= p_; return T; }, /** * Creates the bitwise OR of two sets. * * Ex: * bs1 = new BitSet(10); * bs2 = new BitSet(10); * * res = bs1.or(bs2); * * @param {BitSet} val A bitset object * @returns {BitSet} A new BitSet object, containing the bitwise OR of this and val */ 'or': function(val) { // union parse(P, val); var t = this['clone'](); var d = t['data']; var p = P['data']; var pl = p.length - 1; var tl = d.length - 1; var minLength = Math.min(tl, pl); // Append backwards, extend array only once for (var i = pl; i > minLength; i--) { d[i] = p[i]; } for (; i >= 0; i--) { d[i] |= p[i]; } t['_'] |= P['_']; return t; }, /** * Creates the bitwise XOR of two sets. * * Ex: * bs1 = new BitSet(10); * bs2 = new BitSet(10); * * res = bs1.xor(bs2); * * @param {BitSet} val A bitset object * @returns {BitSet} A new BitSet object, containing the bitwise XOR of this and val */ 'xor': function(val) { // symmetric difference parse(P, val); var t = this['clone'](); var d = t['data']; var p = P['data']; var t_ = t['_']; var p_ = P['_']; var i = 0; var tl = d.length - 1; var pl = p.length - 1; // Cut if tl > pl for (i = tl; i > pl; i--) { d[i] ^= p_; } // Cut if pl > tl for (i = pl; i > tl; i--) { d[i] = t_ ^ p[i]; } // XOR the rest for (; i >= 0; i--) { d[i] ^= p[i]; } // XOR infinity t['_'] ^= p_; return t; }, /** * Creates the bitwise AND NOT (not confuse with NAND!) of two sets. * * Ex: * bs1 = new BitSet(10); * bs2 = new BitSet(10); * * res = bs1.notAnd(bs2); * * @param {BitSet} val A bitset object * @returns {BitSet} A new BitSet object, containing the bitwise AND NOT of this and other */ 'andNot': function(val) { // difference return this['and'](new BitSet(val)['flip']()); }, /** * Flip/Invert a range of bits by setting * * Ex: * bs1 = new BitSet(); * bs1.flip(); // Flip entire set * bs1.flip(5); // Flip single bit * bs1.flip(3,10); // Flip a bit range * * @param {number=} from The start index of the range to be flipped * @param {number=} to The end index of the range to be flipped * @returns {BitSet} this */ 'flip': function(from, to) { if (from === undefined) { var d = this['data']; for (var i = 0; i < d.length; i++) { d[i] = ~d[i]; } this['_'] = ~this['_']; } else if (to === undefined) { scale(this, from); this['data'][from >>> WORD_LOG] ^= (1 << from); } else if (0 <= from && from <= to) { scale(this, to); for (var i = from; i <= to; i++) { this['data'][i >>> WORD_LOG] ^= (1 << i); } } return this; }, /** * Clear a range of bits by setting it to 0 * * Ex: * bs1 = new BitSet(); * bs1.clear(); // Clear entire set * bs1.clear(5); // Clear single bit * bs1.clear(3,10); // Clear a bit range * * @param {number=} from The start index of the range to be cleared * @param {number=} to The end index of the range to be cleared * @returns {BitSet} this */ 'clear': function(from, to) { var data = this['data']; if (from === undefined) { for (var i = data.length - 1; i >= 0; i--) { data[i] = 0; } this['_'] = 0; } else if (to === undefined) { from |= 0; scale(this, from); data[from >>> WORD_LOG] &= ~(1 << from); } else if (from <= to) { scale(this, to); for (var i = from; i <= to; i++) { data[i >>> WORD_LOG] &= ~(1 << i); } } return this; }, /** * Gets an entire range as a new bitset object * * Ex: * bs1 = new BitSet(); * bs1.slice(4, 8); * * @param {number=} from The start index of the range to be get * @param {number=} to The end index of the range to be get * @returns {BitSet} A new smaller bitset object, containing the extracted range */ 'slice': function(from, to) { if (from === undefined) { return this['clone'](); } else if (to === undefined) { to = this['data'].length * WORD_LENGTH; var im = Object.create(BitSet.prototype); im['_'] = this['_']; im['data'] = [0]; for (var i = from; i <= to; i++) { im['set'](i - from, this['get'](i)); } return im; } else if (from <= to && 0 <= from) { var im = Object.create(BitSet.prototype); im['data'] = [0]; for (var i = from; i <= to; i++) { im['set'](i - from, this['get'](i)); } return im; } return null; }, /** * Set a range of bits * * Ex: * bs1 = new BitSet(); * * bs1.setRange(10, 15, 1); * * @param {number} from The start index of the range to be set * @param {number} to The end index of the range to be set * @param {number} value Optional value that should be set on the index (0 or 1) * @returns {BitSet} this */ 'setRange': function(from, to, value) { for (var i = from; i <= to; i++) { this['set'](i, value); } return this; }, /** * Clones the actual object * * Ex: * bs1 = new BitSet(10); * bs2 = bs1.clone(); * * @returns {BitSet|Object} A new BitSet object, containing a copy of the actual object */ 'clone': function() { var im = Object.create(BitSet.prototype); im['data'] = this['data'].slice(); im['_'] = this['_']; return im; }, /** * Gets a list of set bits * * @returns {Array} */ 'toArray': Math['clz32'] ? function() { var ret = []; var data = this['data']; for (var i = data.length - 1; i >= 0; i--) { var num = data[i]; while (num !== 0) { var t = 31 - Math['clz32'](num); num ^= 1 << t; ret.unshift((i * WORD_LENGTH) + t); } } if (this['_'] !== 0) ret.push(Infinity); return ret; } : function() { var ret = []; var data = this['data']; for (var i = 0; i < data.length; i++) { var num = data[i]; while (num !== 0) { var t = num & -num; num ^= t; ret.push((i * WORD_LENGTH) + popCount(t - 1)); } } if (this['_'] !== 0) ret.push(Infinity); return ret; }, /** * Overrides the toString method to get a binary representation of the BitSet * * @param {number=} base * @returns string A binary string */ 'toString': function(base) { var data = this['data']; if (!base) base = 2; // If base is power of two if ((base & (base - 1)) === 0 && base < 36) { var ret = ''; var len = 2 + Math.log(4294967295/*Math.pow(2, WORD_LENGTH)-1*/) / Math.log(base) | 0; for (var i = data.length - 1; i >= 0; i--) { var cur = data[i]; // Make the number unsigned if (cur < 0) cur += 4294967296 /*Math.pow(2, WORD_LENGTH)*/; var tmp = cur.toString(base); if (ret !== '') { // Fill small positive numbers with leading zeros. The +1 for array creation is added outside already ret += '0'.repeat(len - tmp.length - 1); } ret += tmp; } if (this['_'] === 0) { ret = ret.replace(/^0+/, ''); if (ret === '') ret = '0'; return ret; } else { // Pad the string with ones ret = '1111' + ret; return ret.replace(/^1+/, '...1111'); } } else { if ((2 > base || base > 36)) throw SyntaxError('Invalid base'); var ret = []; var arr = []; // Copy every single bit to a new array for (var i = data.length; i--; ) { for (var j = WORD_LENGTH; j--; ) { arr.push(data[i] >>> j & 1); } } do { ret.unshift(divide(arr, base).toString(base)); } while (!arr.every(function(x) { return x === 0; })); return ret.join(''); } }, /** * Check if the BitSet is empty, means all bits are unset * * Ex: * bs1 = new BitSet(10); * * bs1.isEmpty() ? 'yes' : 'no' * * @returns {boolean} Whether the bitset is empty */ 'isEmpty': function() { if (this['_'] !== 0) return false; var d = this['data']; for (var i = d.length - 1; i >= 0; i--) { if (d[i] !== 0) return false; } return true; }, /** * Calculates the number of bits set * * Ex: * bs1 = new BitSet(10); * * var num = bs1.cardinality(); * * @returns {number} The number of bits set */ 'cardinality': function() { if (this['_'] !== 0) { return Infinity; } var s = 0; var d = this['data']; for (var i = 0; i < d.length; i++) { var n = d[i]; if (n !== 0) s += popCount(n); } return s; }, /** * Calculates the Most Significant Bit / log base two * * Ex: * bs1 = new BitSet(10); * * var logbase2 = bs1.msb(); * * var truncatedTwo = Math.pow(2, logbase2); // May overflow! * * @returns {number} The index of the highest bit set */ 'msb': Math['clz32'] ? function() { if (this['_'] !== 0) { return Infinity; } var data = this['data']; for (var i = data.length; i-- > 0;) { var c = Math['clz32'](data[i]); if (c !== WORD_LENGTH) { return (i * WORD_LENGTH) + WORD_LENGTH - 1 - c; } } return Infinity; } : function() { if (this['_'] !== 0) { return Infinity; } var data = this['data']; for (var i = data.length; i-- > 0;) { var v = data[i]; var c = 0; if (v) { for (; (v >>>= 1) > 0; c++) { } return (i * WORD_LENGTH) + c; } } return Infinity; }, /** * Calculates the number of trailing zeros * * Ex: * bs1 = new BitSet(10); * * var ntz = bs1.ntz(); * * @returns {number} The index of the lowest bit set */ 'ntz': function() { var data = this['data']; for (var j = 0; j < data.length; j++) { var v = data[j]; if (v !== 0) { v = (v ^ (v - 1)) >>> 1; // Set v's trailing 0s to 1s and zero rest return (j * WORD_LENGTH) + popCount(v); } } return Infinity; }, /** * Calculates the Least Significant Bit * * Ex: * bs1 = new BitSet(10); * * var lsb = bs1.lsb(); * * @returns {number} The index of the lowest bit set */ 'lsb': function() { var data = this['data']; for (var i = 0; i < data.length; i++) { var v = data[i]; var c = 0; if (v) { var bit = (v & -v); for (; (bit >>>= 1); c++) { } return WORD_LENGTH * i + c; } } return this['_'] & 1; }, /** * Compares two BitSet objects * * Ex: * bs1 = new BitSet(10); * bs2 = new BitSet(10); * * bs1.equals(bs2) ? 'yes' : 'no' * * @param {BitSet} val A bitset object * @returns {boolean} Whether the two BitSets have the same bits set (valid for indefinite sets as well) */ 'equals': function(val) { parse(P, val); var t = this['data']; var p = P['data']; var t_ = this['_']; var p_ = P['_']; var tl = t.length - 1; var pl = p.length - 1; if (p_ !== t_) { return false; } var minLength = tl < pl ? tl : pl; var i = 0; for (; i <= minLength; i++) { if (t[i] !== p[i]) return false; } for (i = tl; i > pl; i--) { if (t[i] !== p_) return false; } for (i = pl; i > tl; i--) { if (p[i] !== t_) return false; } return true; }, [Symbol.iterator]: function () { var d = this['data']; var ndx = 0; if (this['_'] === 0) { // Find highest index with something meaningful var highest = 0; for (var i = d.length - 1; i >= 0; i--) { if (d[i] !== 0) { highest = i; break; } } return { 'next': function () { var n = ndx >>> WORD_LOG; return { 'done': n > highest || n === highest && (d[n] >>> ndx) === 0, 'value': n > highest ? 0 : (d[n] >>> ndx++) & 1 }; } }; } else { // Endless iterator! return { 'next': function () { var n = ndx >>> WORD_LOG; return { 'done': false, 'value': n < d.length ? (d[n] >>> ndx++) & 1 : 1, }; } }; } } }）; BitSet['fromHexString'] = function(str) { return new BitSet('0x' + str); }; BitSet['Random'] = function(n) { if (n === undefined || n < 0) { n = WORD_LENGTH; } var m = n % WORD_LENGTH; // Create an array, large enough to hold the random bits var t = []; var len = Math.ceil(n / WORD_LENGTH); // Create an bitset instance var s = Object.create(BitSet.prototype); // Fill the vector with random data, uniformly distributed for (var i = 0; i < len; i++) { t.push(Math.random() * 4294967296 | 0); } // Mask out unwanted bits if (m > 0) { t[len - 1] &= (1 << m) - 1; } s['data'] = t; s['_'] = 0; return s; }47:[] 43:{"id":"1f1aa793057e81ba","slug":null,"title":"bitset","thumbnail":"e83ef5aa13a6d43da350c7feef08c3d4d161fea5b41dda32cfa2052733a5589c","access_level":"public","create_time":"$D2023-03-21T02:40:41.796Z","update_time":"$D2023-03-21T05:24:14.386Z","view_time":null,"first_public_time":"$D2023-03-21T02:40:41.796Z","has_unpublished_edits":null,"fork":{"id":"d4320304e77dae18","slug":"bitset","title":"bitset","owner":{"id":"412485c08e0f3413","login":"zipengliu","name":"Zipeng Liu"}},"stars":0,"starred":false,"owner":{"type":"team","id":"7571c48497ac6e2f","login":"luvoy","name":"Luvoy","avatar_url":"https://avatars-next.observableusercontent.com/60944aee68bca793fee3137f720bb9737eeb2817cf7feb1e66cf91c9dc015987","tier":"starter_2024","bio":"","following":false},"version":101,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"c23375506cfabab8","login":"luvoy","name":"Luvoy","avatar_url":"https://avatars-next.observableusercontent.com/60944aee68bca793fee3137f720bb9737eeb2817cf7feb1e66cf91c9dc015987","tier":null,"bio":"","following":false}],"members":[{"type":"individual","id":"c23375506cfabab8","login":"luvoy","name":"Luvoy","avatar_url":"https://avatars-next.observableusercontent.com/60944aee68bca793fee3137f720bb9737eeb2817cf7feb1e66cf91c9dc015987","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"bitset","cells":[{"id":0,"value":"# bitset","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":22,"value":"/**\n * @license BitSet.js v5.1.1 2/1/2020\n * http://www.xarg.org/2014/03/javascript-bit-array/\n *\n * Copyright (c) 2020, Robert Eisele (robert@xarg.org)\n * Dual licensed under the MIT or GPL Version 2 licenses.\n **/\n// Changed to class format","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":14,"value":" /**\n * The number of bits of a word\n * @const\n * @type number\n */\nWORD_LENGTH = 32;","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":" /**\n * The log base 2 of WORD_LENGTH\n * @const\n * @type number\n */\nWORD_LOG = 5;","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":29,"value":"/**\n * Calculates the number of set bits\n *\n * @param {number} v\n * @returns {number}\n */\nfunction popCount(v) {\n\n // Warren, H. (2009). Hacker`s Delight. New York, NY: Addison-Wesley\n\n v -= ((v >>> 1) & 0x55555555);\n v = (v & 0x33333333) + ((v >>> 2) & 0x33333333);\n return (((v + (v >>> 4) & 0xF0F0F0F) * 0x1010101) >>> 24);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":31,"value":"/**\n* Divide a number in base two by B\n*\n* @param {Array} arr\n* @param {number} B\n* @returns {number}\n*/\nfunction divide(arr, B) {\n\n var r = 0;\n\n for (var i = 0; i < arr.length; i++) {\n r *= 2;\n var d = (arr[i] + r) / B | 0;\n r = (arr[i] + r) % B;\n arr[i] = d;\n }\n return r;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":34,"value":"$45","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":39,"value":"function scale(dst, ndx) {\n\n var l = ndx >>> WORD_LOG;\n var d = dst['data'];\n var v = dst['_'];\n\n for (var i = d.length; l >= i; l--) {\n d.push(v);\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":63,"value":"BitSet = function(param) {\n /**\n * Module entry point\n *\n * @constructor\n * @param {string|BitSet|number=} param\n * @returns {BitSet}\n */\n if (!(this instanceof BitSet)) {\n return new BitSet(param);\n }\n parse(this, param);\n this['data'] = this['data'].slice();\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":73,"value":"P = ({\n data: [], // Holds the actual bits in form of a 32bit integer array.\n _: 0 // Holds the MSB flag information to make indefinitely large bitsets inversion-proof\n});","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"$46","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":97,"value":"BitSet.prototype.fromBinaryString = function(str) {\n\n return new BitSet('0b' + str);\n};","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W47","stdlib":"1"}} 44:"$43:body"