在 JavaScript 中使用整数作为位域

Question

作为项目的一部分，我有一串 0 到 3 之间的数字，例如： 2030000000000000000030000000000000000003333212111221121301

我想通过 URL 传递这个字符串，所以我想我可以尝试使用位字段，因为每个数字最多只使用 2 位。我在类中编写了以下函数，将这样的字符串与用作数据位字段的整数数组相互转换：

makeBuildBitfield: function(build) {
var b = build.split('');
var f = [3, 0]; // the "3" is there for future purposes
var i = 1;
var j = 0;

for (var t in b) {
    if (j < 14) {
        f[i] |= b[t];
        f[i] = f[i] << 2;
        ++j;
    } else {
        f[i] |= b[t];
        ++i;
        f[i] = 0;
        j = 0;
    }
}

return f.join('.');
},

getBuildFromBitfield: function(bitfield) {
b = bitfield.split('.');

var ba = [];
for (var x = 1; x < b.length; ++x) { //start from 1 to skip the "3"
    ba[x] = [];
    var n = b[x];
    for (var y = 14; y >= 0; --y) {
        ba[x][y] = n & 3;
        n = n >>> 2;
    }
}

build = '';
for (var a in ba) build += ba[a].join('');
return build;
},

它们似乎确实有效，但是......不完全是。当我在开始时从示例中传递字符串时：

2030000000000000000030000000000000000003333212111221121301

我得到以下输出：

3.587202560.786432.4089.156916164

但是，当我将其传递给应该将其转换回来的函数时，它会给我这个：

203000000000000000003000000000000000000333321021112211213010

请注意第二个字符串中的额外零。现在，我对位操作很陌生，这是我第一次尝试，但我已经四处搜索并阅读了我能找到的关于该主题的文章，并且我尝试在一张纸上写下随着循环的进行，尝试理解正在发生的事情，但我似乎无法弄清楚为什么会出错以及这些额外的零在那里做了什么。要么我的 string->bitfield 函数关闭，要么另一个函数关闭，或者很可能两者都关闭。但我真的无法弄清楚，所以有人对我如何解决出现的问题有任何建议吗？

提前致谢！

Answer 1

这是一个很好的简短方法，可将位域缩小为 36 进制字符串。它也适用于以 10 为基数的字符串，但它更加简洁。它也适用于位字段中的前导零。

function shrink (s) {
  for (var p=0, l=s.length, r=''; p<l; p+=25) { 
    r+=parseInt('1'+s.substring(p,p+25),4).toString(36); 
  }
  return r;
}

function expand (s) {
  for (var p=0, l=s.length, r=''; p<l; p+=10) { 
    r+=parseInt(s.substring(p,p+10), 36).toString(4).substring(1);
  }
  return r;
}

编辑 - 我假设您的目标是缩小位字段，通过 url （GET 请求）发送它，然后在另一侧扩展它。这将允许您做到这一点，尽管除了传输和扩展它之外，您将无法对缩小的数据执行任何有用的操作。

编辑 2 - 现在这是一个“无点”变体。这是一个测试：

var bits =  "0000000000000000000000000000000032222000" +
            "0000000000000000000000000000000031111300" +
            "0000000000000000000002111300000002111200" +
            "0000000000000000000003111120000003111130" +
            "0000000000000000000000021111200000111120" +
            "0000000000000320000000000211112000311110" +
            "0000000000002111123000000031111130011113" +
            "0000000000000321111111230000311112031111" +
            "0000000000000000032111111123002112200000" +
            "0000000032223300000000021111112000000000" +
            "0000000021111111112233000332130000000000" +
            "0330000000033322111111111111003330000000" +
            "2112000000000000000003222112001113000000" +
            "2112000111111111111112222220001113000000" +
            "2112000222222111111111111120001113000000" +
            "2112000000000000000033222230001113000000" +
            "2112003111111111111111111120001113000000" +
            "2112000000000000000000000000001113000000" +
            "2112333333333333333333333333331113000000" +
            "2111111111111111111111111111111113000000" ;

var shrunk = shrink(bits);
// b33j9ynrb4b34c70cb9cb33j9ynrclf2iv9lsx6ocpgnayh8n4b33j9ys...

var restored = expand(shrunk);

alert ( "Worked: " + (bits===restored) + ", orig size: " 
      + bits.length + ", shrunk size: " + shrunk.length);

// Worked: true, orig size: 800, shrunk size: 320

Answer 2

有几个问题：

1. 迭代数组时不要使用“for (var x in y)”类型的循环。始终使用索引。

2. 添加到位域字符串中的最后一个内容并不总是代表原始的 15 位数字。 “get”函数始终假定每个位域组件具有相同的位数。

3. 您在某些局部变量声明中遗漏了 var。

这是我的版本，它至少适用于您的示例输入：

  makeBuildBitfield: function(build) {
    var b = build.split('');
    var f = [3, 0]; // the "3" is there for future purposes
    var i = 1, j = 0;;

    for (var t = 0; t < b.length; ++t, ++j) {
        if (j === 15) {
          f[++i] = 0;
          j = 0;
        }
        f[i] = (f[i] << 2) + (b[t] & 3);
    }

    f[0] = j === 0 ? 15 : j;
    return f.join('.');
  },

  getBuildFromBitfield: function(bitfield) {
    var b = bitfield.split('.');

    var ba = [];
    for (var x = 1; x < b.length; ++x) { //start from 1 to skip the "3"
        ba[x] = [];
        var n = b[x];
        for (var y = (x === b.length - 1 ? parseInt(b[0], 10) : 15); --y >= 0; ) {
            ba[x][y] = n & 3;
            n = n >>> 2;
        }
    }

    var build = '';
    for (var a = 1; a < ba.length; ++a) {
      build += ba[a].join('');
    }
    return build;
  }

我窃取了您的“f[0]”作为最后一个条目的大小，但您可以将该值放在任何地方。

Answer 3

好吧，因为我已经编写了一些位图代码，所以这里有一个使用它的解决方案。

Bitmap.js

function Bitmap (vals) {
  this.arr = [];
  this.length = 0;
  if (vals) {
    for (var i = vals.length - 1; i >= 0; --i) {
      if (vals [i]) {
        this.set (i);
      }
      else {
        this.clear (i);
      }
    }
  }
}

Bitmap.prototype = {
    constructor: Bitmap

  , toString: function () {
      vals = [];
      for (var i = this.length - 1; i >= 0; --i) {
        vals [i] = this.get (i) ? "1" : "0";
      }
      return vals.join ("");
    }

  , clear: function (i) {
      if (i >= this.length) {
        this.length = i + 1;
      }
      var pos = i / 32 | 0;
      this.arr [pos] = this.arr [pos] & ~(1 << i % 32);
    }

  , get: function (i) {
      return (this.arr [Math.floor (i / 32 | 0)] & 1 << i % 32) > 0;
    }

  , serialize: function () {
      var str = "";
      for (var i = 0; i < this.arr.length; ++i) {
        var num = this.arr [i];
        str += num < 0
          ? (-num).toString (36) + Bitmap.NEGATIVE_DELIM
          : num.toString (36) + Bitmap.POSITIVE_DELIM
          ;
      }
      var trailingLength = this.length % 32;
      if (trailingLength == 0) {
        trailingLength = 32;
      }
      if (this.length == 0) {
        trailingLength = 0;
      }
      return str + trailingLength.toString (36);
    }

  , set: function (i) {
      if (i >= this.length) {
        this.length = i + 1;
      }
      var pos = i / 32 | 0;
      this.arr [pos] = this.arr [pos] | 1 << i % 32;
    }

  , size: function () {
      return this.length;
    }

};

Bitmap.POSITIVE_DELIM = ".";
Bitmap.NEGATIVE_DELIM = "!"

Bitmap.deserialize = (function () {
  var MATCH_REGEX = new RegExp (
      "[A-Za-z0-9]+(?:"
      + Bitmap.POSITIVE_DELIM
      + "|"
      + Bitmap.NEGATIVE_DELIM
      + ")?"
    , "g");
  return function (str) {
    var bm = new Bitmap ();
    var arr = str.match (MATCH_REGEX);
    var trailingLength = parseInt (arr.pop (), 36);
    for (var i = 0; i < arr.length; ++i) {
      var str = arr [i];
      var sign = str.charAt (str.length - 1) == Bitmap.POSITIVE_DELIM ? 1 : -1;
      bm.arr [i] = parseInt (str, 36) * sign;
    }
    bm.length = Math.max ((arr.length - 1) * 32 + trailingLength, 0);
    return bm;
  };
}) ();

测试.js

function toBits (numStr, numBitsToExtract) {
  var numChars = numStr.split ("");
  var bits = [];
  for (var i = 0; i < numChars.length; ++i) {
    var num = numChars [i] - 0;
    for (var j = numBitsToExtract - 1; j >= 0; --j) {
      bits.push (num & 1 << j ? 1 : 0);
    }
  }
  return bits;
}

function fromBits (bitStr, numBitsToExtract) {
  var bitChars = bitStr.split ("");
  var nums = [];
  for (var i = 0; i < bitChars.length; ) {
    var num = 0;
    for (var j = numBitsToExtract - 1; j >= 0; ++i, --j) {
      num |= bitChars [i] - 0 << j;
    }
    nums.push (num);
  }
  return nums.join ("");
}

var numStr = "2030000000000000000030000000000000000003333212111221121301";
var bits = toBits (numStr, 2);
var serialized = new Bitmap (bits).serialize (); // "1d.lc.ou00e8!ci3a.k"
var recoveredNumStr = fromBits (Bitmap.deserialize (serialized).toString (), 2);