###二进制转十进制
32位机器上的自然数一共有4294967296个，
如果用一个bit来存放一个整数，1代表存在0代表不存在，那么把全部自然数存储在内存只要4294967296 / (8 * 1024 * 1024) = 512MB（8bit = 一个字节）
而这些自然数存放在文件中，一行一个数字，需要20G的容量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
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);
}
/* (1) $value & 31 相当于 $value % 32 ，
* 这个是取当前的值标示是否存在的位置
* 例如$value = 67 得到3 位置应该是在二进制从右往左数的下标3的位置也就是第四位
* (2) 1 << ($value & 31) 就是 把当前得到的值转化成二进制的位置
* 例如$value = 67 得到3 3的二进制 为11 向左偏移3位 得到2进制 1000
* (3) |= 是 按位或运算并赋值
* 所以当前$map[$index] 的二进制的值为 1000 十进制就是8
*/
echo "当前值的二进制：".(decbin($value))."\n";
echo "取模位置左移1：".(decbin(1 << ($value & 31))).'-'.(1 << ($value & 31))."\n";
echo "插入后map：".(decbin(self::$map[$index])).'-'.(self::$map[$index])."\n";
}
//查找某个值是否存在
public static function haxValue($value) {
$index = self::getIndex($value);
if (!isset(self::$map[$index])) {
return false;
}
/**
* 例如传入的值为87，bitmap中存的值为67
* (1) 1 << ($value & 31) 得到1<<23 ,1左偏移23位，
* 得到 二进制值为 100000000000000000000000 也就是十进制的8388608
* (2) 然后和 self::$map[$index] 进行按位与（二进制1000 和 二进制 100000000000000000000000）
* 得到二进制 000000000000000000000000也就是十进制的0 也就是不存在
* 如果存在则返回这个数在self::$map[$index] 中的位置转换成的十进制的值 （如67返回8二进制也就是1000）
*/
if ((self::$map[$index] & (1 << ($value & 31)))==0) {
return false;
}
return true;
}
public static function display()
{
$keys = array_keys(self::$map);
foreach ($keys as $key) {
print "map index: {$key}, bit:\n";
$temp = self::$map[$key];
$bit_str = '';
for ($i = 0; $i <= 31; $i++) {
$bit_str = (1 & $temp) . $bit_str;
echo ($bit_str)."\n";
$temp >>= 1;
}
echo "{$bit_str}\n";
}
}
//去出在数组的第几个key里面
private static function getIndex($value) {
return $value >> 5;
/**
* 相当于floor($value / 32);
* 这里是2进制运算当前值右移动5位
* 例如67 二进制为1000011 右移动5位二进制为10 十进制为2
*/
}
}
$list = [67];
foreach ($list as $value) {
BitMap::setValue($value);
}
BitMap::display();
var_dump(BitMap::haxValue(87));
|