Advanced Search

BitVector in JS

/ Published in: JavaScript
Save to your folder(s)
Shows how to implement a primitive bit vector in js

Expand | Embed | Plain Text

Copy this code and paste it in your HTML 
  1. function BitVector(data) {
  2.     this.data = data == null ? [0] : data;
  3. }
  4.  
  5. BitVector.prototype.and = function (other) {
  6.     var data = new Array();
  7.     var newLen = Math.max(other.data.length, this.data.length);
  8.  
  9.     for (var i = 0; i < newLen; i++) {
  10.         data[i] = this.data[i] & other.data[i];
  11.     }
  12.  
  13.     return new BitVector(data);
  14. }
  15.  
  16. BitVector.prototype.or = function (other) {
  17.     var data = new Array();
  18.     var newLen = Math.max(other.data.length, this.data.length);
  19.  
  20.     for (var i = 0; i < newLen; i++) {
  21.         data[i] = this.data[i] | other.data[i];
  22.     }
  23.  
  24.     return new BitVector(data);
  25. }
  26.  
  27. BitVector.prototype.xor = function (other) {
  28.     var data = new Array();
  29.     var newLen = Math.max(other.data.length, this.data.length);
  30.  
  31.     for (var i = 0; i < newLen; i++) {
  32.         data[i] = this.data[i] ^ other.data[i];
  33.     }
  34.  
  35.     return new BitVector(data);
  36. }
  37.  
  38. BitVector.prototype.not = function () {
  39.     var data = new Array();
  40.  
  41.     for (var i = 0; i < this.data.length; i++) {
  42.         data[i] = ~this.data[i]
  43.     }
  44.  
  45.     return new BitVector(data);
  46. }
  47.  
  48. BitVector.prototype.empty = function () {
  49.     for (var i = 0; i < this.data.length; i++) {
  50.         if (this.data[i] != 0) return false;
  51.     }
  52.     return true;
  53. }
  54.  
  55. BitVector.prototype.count = function () {
  56.     var c = 0;
  57.     for (var i = 0; i < this.data.length; i++) {
  58.         var v = this.data[i];
  59.         if (v > 0) {
  60.             for (b = 0; b < 32; b++) {
  61.                 var bitMask = Math.pow(2, b);
  62.                 c += (bitMask & v) != 0;
  63.             }
  64.         }
  65.     }
  66.  
  67.     return c;
  68. }
  69.  
  70. BitVector.prototype.clone = function () {
  71.     var data = new Array();
  72.     for (var i = 0; i < this.data.length; i++) {
  73.         data[i] = this.data[i];
  74.     }
  75.     return new BitVector(data);
  76. }
  77.  
  78. BitVector.prototype.testBit = function (index) {
  79.     var bitPos = index % 32;
  80.     var val = this.data[(index - bitPos) / 32];
  81.     var bitMask = Math.pow(2, bitPos);
  82.     return (bitMask & val) != 0;
  83. }
  84.  
  85. BitVector.prototype.setBit = function (index, value) {
  86.     var bitPos = index % 32;
  87.     var bitMask = Math.pow(2, bitPos);
  88.     var arrPos = (index - bitPos) / 32;
  89.  
  90.     if (arrPos >= this.data.length) {
  91.         for (var i = this.data.length; i < arrPos + 1; i++) this.data[i] = 0;
  92.     }
  93.  
  94.     if (value) {
  95.         // Oder-Verknüpfung der Bitmask
  96.         this.data[arrPos] |= bitMask;
  97.     }
  98.     else {
  99.         // Und-Verknüpfung des Komplements der Bitmask
  100.         this.data[arrPos] &= ~bitMask;
  101.     }
  102. }
  103.  
  104. BitVector.prototype.toString = function () {
  105.     var s = "";
  106.  
  107.     for (var i = 0; i < this.data.length * 32; i++) {
  108.         s += this.testBit(i) ? '1' : '0';
  109.     }
  110.  
  111.     return s;
  112. }

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.