Wallogit.com
2017 © Pedro Peláez
A simple Bit Set implementation
, (*1)
A simple bit set implementation for compact storage of sets of values. The library itself is stateless providing only pure mapping functions., (*2)
PHP 7.1+, (*3)
$ composer require pwm/bitset
In this example we are going to use a bit set to put users in groups., (*4)
Let's create a Group class. It has a list of groups, named G1 to G5 for this example, and a map between groups and binary values of powers of 2 provided by BitSet. Finally it has 2 functions that map between group names and bit values., (*5)
class Group
{
const G1 = 'Group 1';
const G2 = 'Group 2';
const G3 = 'Group 3';
const G4 = 'Group 4';
const G5 = 'Group 5';
private const MAP = [
self::G1 => BitSet::B1,
self::G2 => BitSet::B2,
self::G3 => BitSet::B3,
self::G4 => BitSet::B4,
self::G5 => BitSet::B5,
];
public static function fromGroups(array $groups): array
{
return array_values(array_intersect_key(self::MAP, array_flip($groups)));
}
public static function toGroups(array $bitValues): array
{
return array_values(array_intersect_key(array_flip(self::MAP), array_flip($bitValues)));
}
}
Let's also create a User class. A user can belong to groups. The $groups property starts from 0 that represents the empty set. It has 5 methods to manipulate its groups, corresponding to BitSet's 5 functions: get(), set(), add(), remove() and has()., (*6)
class User
{
private $groups = BitSet::EMPTY;
public function getGroups(): array
{
return Group::toGroups(BitSet::get($this->groups));
}
public function setGroups(array $groups): void
{
$this->groups = BitSet::set(Group::fromGroups($groups));
}
public function addGroups(array $groups): void
{
$this->groups = BitSet::add($this->groups, Group::fromGroups($groups));
}
public function removeGroups(array $groups): void
{
$this->groups = BitSet::remove($this->groups, Group::fromGroups($groups));
}
public function hasGroup(string $group): bool
{
$a = Group::fromGroups([$group]);
return isset($a[0])
? BitSet::has($this->groups, $a[0])
: false;
}
}
Now we can use the above the following way:, (*7)
$user = new User(); $user->setGroups([Group::G1, Group::G2]); assert($user->getGroups() === [Group::G1, Group::G2]); assert($user->hasGroup(Group::G1) === true); $user->addGroups([Group::G4, Group::G5]); $user->removeGroups([Group::G1, Group::G4]); assert($user->getGroups() === [Group::G2, Group::G5]); assert($user->hasGroup(Group::G1) === false);
As an example let's take the numbers 1, 4 and 8. Their sum is 13. Pretty uninteresting so far. But let's look at their binary representations: 0b1, 0b100 and 0b1000 respectively. Their sum 13 is 0b1101. See how the base-2 representations of 1, 4 and 8 "fill unique slots" in 13's, leaving only one slot unset? This is because 1, 4 and 8 are all powers of 2 so their binary representations starts with a 1 followed by zero or more 0s. 0b1 = 2^0 = 1, 0b100 = 2^2 = 4, 0b1000 = 2^3 = 8. Their sum: 2^0 + 2^2 + 2^3 = 0b1 + 0b100 + 0b1000 = 0b1101 = 13. Now, say in a game, we could call 1 "north", 2 "south", 4 "east" and 8 "west" and then 13 could mean that our character can move all directions from its current position except south as 2 (0b10) is not in 13 (0b1101)., (*8)
The idea behind a bit set is using a base-2 representation of a number to singal the presence or absence of values by having its bits set to 1 or 0. The values themselves are also numbers with the restriction that they must be powers of 2 starting from 2^0 and in general, depending on the underlying system, going up to 2^32 or 2^64. For example on a 64 bit system one can store up to 64 unique values in a bit set., (*9)
The BitSet library itself is a collection of 5 pure functions that map between values and their bit set:, (*10)
set(array $values): int, (*11)
Maps a list of unique positive integers to a single integer, the bit set, that is their sum. All integers in the input list must be powers of 2., (*12)
get(int $bitSet): array, (*13)
Maps an integer, the bit set, to a list of unique positive integers. All integers in the output list must be powers of 2., (*14)
add(int $bitSet, array $values): int, (*15)
Adds a list of unique positive integers to a bit set. All integers in the list must be powers of 2., (*16)
remove(int $bitSet, array $values): int, (*17)
Subtracts a list of unique positive integers from a bit set. All integers in the list must be powers of 2., (*18)
has(int $bitSet, int $value): bool, (*19)
Predicate that tells whether an element is in a bit set or not., (*20)
$ vendor/bin/phpunit $ composer phpcs $ composer phpstan
Click here, (*21)
MIT, (*22)
A simple Bit Set implementation
MIT
bitset bitmap bitarray
A simple Bit Set implementation
MIT
bitset bitmap bitarray
A simple Bit Set implementation
MIT