概述
bitmap这个东西一直都是知道概念，没有实际coding过，网上照抄了一个代码，特喵的有点小问题，上一个自己debug过的版本。
作用
大量数据进行排序，查找和去重上可以使用这个策略来降低内存的使用
代码
class BitMap
{
public static $map = [];
public static function setValue($value) {
$index = self::getIndex($value);
if (isset(self::$map[$index])) {
self::$map[$index] |= 1 << ($value & 31);
} else {
self::$map[$index] = 1 << ($value & 31);
}
}
public static function haxValue($value) {
$index = self::getIndex($value);
return isset(self::$map[$index]) ? (self::$map[$index] & (1 << ($value & 31))) == (1 << ($value & 31)) : false;
}
public static function display()
{
$keys = array_keys(self::$map);
foreach ($keys as $key) {
print "map index: {$key}, bit:";
$temp = self::$map[$key];
$bit_str = '';
for ($i = 0; $i <= 31; $i++) {
$bit_str = (1 & $temp) . $bit_str;
$temp >>= 1;
}
echo "{$bit_str}\n";
}
}
private static function getIndex($value) {
return $value >> 5;
}
}
$list = [1, 3, 3, 7, 25, 88, 0];
foreach ($list as $value) {
BitMap::setValue($value);
}
BitMap::display();
var_dump(BitMap::haxValue(87));
var_dump(BitMap::haxValue(88));
var_dump(BitMap::haxValue(89));
策略
1个4字节的整型变量有32比特，所以我们用一个int来表示32个数字是否存在(哪个数字存在那么那一位上就是1)； 实际上：
$map[0] 表示 [0, 31]
$map[1] 表示 [32, 63]
$map[2] 表示 [64, 95]
整个类包含两个主要的方法: setValue和hasValue。 先描述getIndex()的作用，实际上是将输入值对32取模，可以按位右移5位(2^5=32)的方式或者floor($value / 32)等各种方式，按位操作会快嘛，用这个舒服。
再说setValue()方法，核心代码就1行：
self::$map[$index] |= 1 << ($value & 31);
首先$value & 31实际上就是将输入值对32取模。31转换成二进制实际上就是5个1，拿着输入值的后5位，来跟这5个1按位与，得到一个偏移量。记录偏移量实际就是记录了输入值存在。 然后这里有一个按位或的操作，起到了将多个偏移量聚合，且去重的作用。
其次我们来看hasValue()方法，核心代码也就1行，暂时没想到更好的写法：
(self::$map[$index] & (1 << ($value & 31))) == (1 << ($value & 31))
在我们完成setValue()的行为后，map中值的二进制展示大概是这样：
bit:00000010000000000000000010001011
上述值我取的是$map[0],如果3是存在，那么从右往左数4位，那一位一定是1，否则是0。所以判断的方式是我们构造出来一个二进制的1000,拿着这个数去和$map[0]按位与。这里有且仅有2种可能性：
3存在：那么返回二进制的10003不存在: 那么返回0
所以这里也可以写成：
(self::$map[$index] & (1 << ($value & 31))) != 0
因为我们构造的操作数有且仅有1位是1。
其他代码没什么好说的，执行一下就完事儿了。
