Posted By

jscoder on 05/03/14


Tagged

utils


Versions (?)

BitVector in JS


 / Published in: JavaScript
 

Shows how to implement a primitive bit vector in js

  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  

You need to login to post a comment.