使用大整数与位数组

2016年9月15日，作者：David Farrell

几周前，我写了使用位数组节省空间的文章，并在最大掩码长度上做了一些挥手的处理。具体来说，我说：

使用像bigint这样的模块可能因为地址内存限制而无法工作

现在我并不确定“地址内存限制”这句话在哪里，但这是我从别处读到的，并且认为这是真的，但没有时间去研究。越想越觉得这句话没有意义。一个系统能够访问的内存量受许多因素的控制，但我相信你永远不会想要为了仅存储掩码而创建使用所有可寻址内存的位数组。我决定测试大整数的位数组，看看它们在bigint下是否表现正确。

测试大掩码

对于这些测试，我想检查位数组通常会使用的典型操作：设置/清除掩码以及将位数组转换为二进制字符串。我想出了以下测试脚本：

#!/usr/bin/env perl
use strict;
use warnings;
use bigint;
use Test::More tests => 60;

for my $shift_size (8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096) {
  my $bitmask  = 1 << ($shift_size - 1);
  my $bit_array = 0;

  ok !($bit_array & $bitmask),  'bitmask is not set';
  ok $bit_array |= $bitmask,    'set bitmask';
  ok $bit_array  & $bitmask,    'bitmask is set';
  ok !($bit_array &= ~$bitmask),'bitmask is unset';
  ok !($bit_array & $bitmask),  'bitmask is not set';

  cmp_ok length(sprintf "%b", $bitmask), '==', $shift_size,
    'bitmask string is correct length';
}

此脚本遍历不断增大的数字，使用它们创建掩码，然后测试位数组与掩码。位操作在我之前的文章中已有解释。最后，脚本使用sprintf将掩码转换为二进制字符串，并检查其长度是否正确。运行此脚本时，我遇到了一些有趣的失败。以下是输出片段：

...
not ok 24 - bitmask string is correct length
#   Failed test 'bitmask string is correct length'
#   at ./bigint-test line 18.
#          got: 64
#     expected: 128
ok 25 - bitmask is not set
ok 26 - set bitmask
ok 27 - bitmask is set
ok 28 - bitmask is unset
ok 29 - bitmask is not set
not ok 30 - bitmask string is correct length
#   Failed test 'bitmask string is correct length'
#   at ./bigint-test line 18.
#          got: 64
#     expected: 256
...

虽然所有的位操作都通过了，但当掩码大小超过64位时（我的机器是64位，我预计在32位编译的Perl中会在32位后失败），字符串长度测试就失败了。那么怎么办呢？是不是sprintf不能打印大于64位的整数？在尝试了各种不同的函数后，我尝试了最简单的：向sprintf中包含一个长度参数。所以这条线：

cmp_ok length(sprintf "%b", $bitmask), '==', $shift_size,

变成了

cmp_ok length(sprintf "%0${shift_size}b", $bitmask), '==', $shift_size,

我很高兴地报告，这次更改是有效的，所有的测试都通过了（在Perl 5.10及以上版本）。以下是最终的脚本：

#!/usr/bin/env perl
use strict;
use warnings;
use bigint;
use Test::More tests => 60;

for my $shift_size (8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096) {
  my $bitmask  = 1 << ($shift_size - 1);
  my $bit_array = 0;

  ok !($bit_array & $bitmask),  'bitmask is not set';
  ok $bit_array |= $bitmask,    'set bitmask';
  ok $bit_array  & $bitmask,    'bitmask is set';
  ok !($bit_array &= ~$bitmask),'bitmask is unset';
  ok !($bit_array & $bitmask),  'bitmask is not set';

  cmp_ok length(sprintf "%0${shift_size}b", $bitmask), '==', $shift_size,
    'bitmask string is correct length';
}