How to Implement a Bitmask in PHP

How to implement a bitmask in php?

It's quite simple actually. First a bit of code to demonstrate how it can be implemented. If you don't understand anything about what this code is doing or how it works, feel free to ask additional questions in the comments:

const FLAG_1 = 0b0001; // 1
const FLAG_2 = 0b0010; // 2
const FLAG_3 = 0b0100; // 4
const FLAG_4 = 0b1000; // 8
// Can you see the pattern? ;-)

function show_flags ($flags) {
  if ($flags & FLAG_1) {
    echo "You passed flag 1!<br>\n";
  }
  if ($flags & FLAG_2) {
    echo "You passed flag 2!<br>\n";
  }
  if ($flags & FLAG_3) {
    echo "You passed flag 3!<br>\n";
  }
  if ($flags & FLAG_4) {
    echo "You passed flag 4!<br>\n";
  }
}

show_flags(FLAG_1 | FLAG_3);

Demo

Because the flags are integers, on a 32-bit platform you define up to 32 flags. On a 64-bit platform, it's 64. It is also possible to define the flags as strings, in which case the number of available flags is more or less infinite (within the bounds of system resources, of course). Here's how it works in binary (cut down to 8-bit integers for simplicity).

FLAG_1
Dec:    1
Binary: 00000001

FLAG_2
Dec:    2
Binary: 00000010

FLAG_3
Dec:    4
Binary: 00000100

// And so on...

When you combine the flags to pass them to the function, you OR them together. Let's take a look at what happens when we pass FLAG_1 | FLAG_3

  00000001
| 00000100
= 00000101

And when you want to see which flags were set, you AND the bitmask with the flag. So, lets take the result above and see if FLAG_3 was set:

  00000101
& 00000100
= 00000100

...we get the value of the flag back, a non-zero integer - but if we see if FLAG_2 was set:

  00000101
& 00000010
= 00000000

...we get zero. This means that you can simply evaluate the result of the AND operation as a boolean when checking if the value was passed.

Bitmask in PHP for settings?

Bit fields are a very handy and efficient tool for dealing with flags or any set of boolean values in general.

To understand them you first need to know how binary numbers work. After that you should check out the manual entries on bitwise operators and make sure you know how a bitwise AND, OR and left/right shift works.

A bit field is nothing more than an integer value. Let's assume our bit field's size is fixed and only one byte. Computers work with binary numbers, so if the value of our number is 29, you'll actually find 0001 1101 in the memory.

Using bitwise AND (&) and bitwise OR (|) you can read out and set each bit of the number individually. They both take two integers as input and perform an AND/OR on each bit individually.

To read out the very first bit of your number, you could do something like this:

  0001 1101 (=29, our number)
& 0000 0001 (=1, bit mask)
= 0000 0001 (=1, result)

As you can see you need a special number where only the bit we're interested in is set, that's the so called "bit mask". In our case it's 1. To read out the second bit we have to "push" the one in the bitmask one digit to the left. We can do that with the left shift operator ($number << 1) or by multiplying our by two.

  0001 1101
& 0000 0010
= 0000 0000 (=0, result)

You can do that for every bit in our number. The binary AND of our number and the bit mask leads either to zero, which means the bit wasn't "set", or to a non-zero integer, which means the bit was set.

If you want to set one of the bits, you can use bitwise OR:

  0001 1101
| 0010 0000 (=32, bit mask)
= 0011 1101 (=29+32)

However, you'll have to go a different way when you want to "clear" a bit.

A more general approach would be:

// To get bit n
$bit_n = ($number & (1 << $n)) != 0
// Alternative
$bit_n = ($number & (1 << $n)) >> $n

// Set bit n of number to new_bit
$number = ($number & ~(1 << $n)) | ($new_bit << $n)

At first it might look a bit cryptic, but actually it's quite easy.

By now you probably found out that bit fields are quite a low-level technique. That's why I recommend not to use them within PHP or databases.. If you want to have a bunch of flags it's probably ok, but for anything else you really don't need them.

The class you posted looks a bit special to me. For example, things like ... ? true : false are veery bad practice. If you want to use bit fields, you're probably better off defining some constants and use the method described above. It's not hard to come up with a simple class.

define('PERM_READ', 0);
define('PERM_WRITE', 1);

class BitField {
    private $value;

    public function __construct($value=0) {
        $this->value = $value;
    }

    public function getValue() {
        return $this->value;
    }

    public function get($n) {
        return ($this->value & (1 << $n)) != 0;
    }

    public function set($n, $new=true) {
        $this->value = ($this->value & ~(1 << $n)) | ($new << $n);
    }
    public function clear($n) {
        $this->set($n, false);
    }
}

$bf = new BitField($user->permissions);

if ($bf->get(PERM_READ)) {
    // can read
}

$bf->set(PERM_WRITE, true);
$user->permissions = $bf->getValue();
$user->save();

I didn't try any piece of code of this answer, but it should get you started even if it isn't working out of the box.

Note that you're limited to 32 values per bit field.

Why should I use bitwise/bitmask in PHP?

Why not just do this...

define('PERMISSION_DENIED', 0);
define('PERMISSION_READ', 1);
define('PERMISSION_ADD',  2);
define('PERMISSION_UPDATE', 4);
define('PERMISSION_DELETE', 8);

//run function
// this value would be pulled from a user's setting mysql table
$_ARR_permission = 5;

if($_ARR_permission & PERMISSION_READ) {
    echo 'Access granted.';
}else {
    echo 'Access denied.';
}

You can also create lots of arbitrary combinations of permissions if you use bits...

$read_only = PERMISSION_READ;
$read_delete = PERMISSION_READ | PERMISSION_DELETE;
$full_rights = PERMISSION_DENIED | PERMISSION_READ | PERMISSION_ADD | PERMISSION_UPDATE | PERMISSION_DELETE;

//manipulating permissions is easy...
$myrights = PERMISSION_READ;
$myrights |= PERMISSION_UPDATE;    // add Update permission to my rights

php - Bitmask decode

I guess, this is the simplest and most "native" implementation:

$array = [2 => 'Text_1', 4 => 'Text_2', 8 => 'Text_3', 16 => 'Text_4', 32 => 'Text_5'];

$number = 48;

foreach ($array as $mask => $string)
{
    if ($number & $mask)
    {
        echo "$mask: $string" . PHP_EOL;
    }
}

Get array values based on bitmask in PHP

Here's some PHP code for you, but please note it is pretty inefficient. I have used this algorithm because:

It is explicit and uses words rather than mathematical tricks to get the job done, and
Works in situations where you can't assume an underlying implementation of 2s complement, but still want to 'think' that way. _{^{(try 'storing' bitmasks in PHP and thinking they will work in JavaScript)}}

Please read the comments and implement @Paebbels solution. The difference in performance is almost 7x, so really only use this if it will not be used very often.

It utilizes base_convert to convert the base 10 integer to base 2, splits the string into a character array, reverses the array and then iterates over it looking for 1s.

$mask = 49152; // 0xC000

// Find which positions in the mask contain a '1'
$bitArray = array_reverse(str_split(base_convert($mask, 10, 2)));

foreach($bitArray as $k => $v) {
    if($v) {
        echo $k . " is a one\n";
    }
}

Output:

14 is a one

15 is a one

As a function:

function extractElements($mask, array $input) 
{
    $output = array();
    $bitArray = array_reverse(str_split(base_convert($mask, 10, 2)));

    foreach($bitArray as $k => $v) {
        if($v && isset($input[$k])) {
            $output[] = $input[$k];
        }
    }

    return $output;
}

$mask = 76; // 0x4C
$input = [
    'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight'
];

print_r(extractElements($mask, $input));

Output:

Array
(
[0] => Three
1 => Four
[2] => Seven
)

Implement bitmask or relational ACL in PHP

Bitmasks

The original problem with bitmasks is that they go against the conventions of data modelling (expressed in another answer here, with further reading here and here). A 4-byte signed integer might only contain 31 different values (represented in integer as 2 147 483 648) and calculation is hard with them. There have been various questions on Stack Overflow before discussing this topic, which I used to get a sense of implementation of how bistmasks would work.

Testing also revealed that working with bitmasks is hard. It needs a sense to understand the bitwise operators, and migration becomes basically impossible. (By impossible I mean that, at first, implementing bitmasks seemed a good thing to do, but after all it turned out it requires too much expends compared to the benefit it could give in return.) Take a basic portal-like website... I mean no. Take Stack Overflow as an example, and how much unique privileges it has. I have actually tried to make a count but lost myself in complexity, but the amount we would need is way close, if not already over the said barrier of 31 unique values. There is a very likely chance that an update on the project which alters bitmask meanings result in a long need of recalculation, and it is a lot more error prone if confronted by database errors.

While I don't have the exact, pinpoint timing figures, using bitmasks felt slower than ACL. Comparing database sizes, memory and storage footprint is bigger and we have less chance to exploit the relational database and indexing capabilities. For user permissions on a website, bitmasks are a no-go, if we have other methods we might use.

There are various systems where bitmasks do works, namely MaNGOS (from which I originally came up with the idea), where item_template and various other template tables define flags which makes use of bitmasks. But the bottom line is that in these tables, the values are unlikely to ever change, the calculation is read-only, contrary to websites where users arbitrarily obtain and lose privileges.

Example code

define('U_NIL', 0);
define('U_EXEC', 1);
define('U_WRIT', 2);
define('U_READ', 4);

$our_perm = 7;
$req_perm = U_EXEC | U_WRIT | U_READ;
var_dump( ($our_perm & $req_perm) == $req_perm ); # Will be bool(true)

$our_perm = 3;
var_dump( ... The same thing ...); # Will be bool(false)

$our_perm = U_READ;
$req_perm = U_READ | U_WRIT;
var_dumo(...); # Will be bool(false)

$our_perm = U_READ | U_WRIT | U_EXEC;
$req_perm = U_READ;
var_dump(...); # Will be bool(true)

Etcetera.

I will spare you the lines of code because various other questions describe the method aptly, in a way I will never be able to describe it. Bitmasks seem to be nice, bitmasks seem to be exotic, but there is no point letting them settle in production.

ACL

The other option which was described in the original question was to exploit the relational database and the SQL language to set up the permissions in the database. We will need to create two more tables into our database:

CREATE TABLE `perm_relation` (
    `row_id` int(10) NOT NULL AUTO_INCREMENT,
    `user_id` int(10) NOT NULL,
    `perm_id` int(10) NOT NULL,
    PRIMARY KEY (`row_id`),
    UNIQUE `permission` (`user_id`, `perm_id`)
) ENGINE=InnoDB;

CREATE TABLE `permission` (
    `id` int(10) NOT NULL AUTO_INCREMENT,
    `name` varchar(64) NOT NULL,
    PRIMARY KEY (`row_id`)
) ENGINE=InnoDB;

perm_relation.perm_id will be the foreign key pointing to permission.id, and perm_relation.user_id will be our relation to users.id. After this, it's only a matter of how we put together our programming logic.

SELECT row_id FROM perm_relation
WHERE perm_id = (SELECT id FROM permission WHERE name = "U_SUPERADMIN")
AND user_id = CURRENT_USER_ID;

Using this method we bind towards greater compatibility, quicker execution and easier migration. It takes only a neck of time to add new permissions, both as defining new ones and grating some to arbitrary users. Deletion is just as easy and it takes only a small SQL query to optimize our tables to remove orphan entires (for example: users having permissions given to them without related permission defined in the system).

Because we are implementing this system into a PHP environment, we can assume that there will be some sort of administrative page with many features relying on this permission list. An example of listing users filtered by the permission they have would be one example. In this context, ACL is a lot better than bitmasks, because we can take further exploits of JOIN statements... and even beyond.

The conclusion is that bitmasks and the relational pattern has different purposes. Bitmasks are too much and very bulk for a user permission system, while relational tables would be an overkill in the MaNGOS example mentioned above.

Bitwise operations in PHP?

You could use it for bitmasks to encode combinations of things. Basically, it works by giving each bit a meaning, so if you have 00000000, each bit represents something, in addition to being a single decimal number as well. Let's say I have some preferences for users I want to store, but my database is very limited in terms of storage. I could simply store the decimal number and derive from this, which preferences are selected, e.g. 9 is 2^3 + 2^0 is 00001001, so the user has preference 1 and preference 4.

 00000000 Meaning       Bin Dec    | Examples
 │││││││└ Preference 1  2^0   1    | Pref 1+2   is Dec   3 is 00000011
 ││││││└─ Preference 2  2^1   2    | Pref 1+8   is Dec 129 is 10000001
 │││││└── Preference 3  2^2   4    | Pref 3,4+6 is Dec  44 is 00101100
 ││││└─── Preference 4  2^3   8    | all Prefs  is Dec 255 is 11111111
 │││└──── Preference 5  2^4  16    |
 ││└───── Preference 6  2^5  32    | etc ...
 │└────── Preference 7  2^6  64    |
 └─────── Preference 8  2^7 128    |

Simple way to calculate values in a bitmask?

You need a bitwise-and:

if( $docs2view & 1 ) {...}
if( $docs2view & 2 ) {...}
if( $docs2view & 4 ) {...}
if( $docs2view & 8 ) {...}
if( $docs2view & 16 ) {...}

Here, I'm testing individual bits. If the bit is set, the condition will be non-zero (hence will evaluate to 'true').

You could possibly avoid a lot of code repetition by putting this in a loop and using the bit-shift operators (>> and <<).

You said:

Thank you, paddy! But I only need the lowest value that evaluates
true. How do I tell the loop to stop as soon as it finds that?

You can either convert those statements to elseif so that only the first becomes true, or you can do this (assuming you only check the first 8 bits):

$nextdoc = 0;

for( $i = 0; $i < 8; $i++ ) {
    if( $docs2view & (1<<$i) ) {
        $nextdoc = $i + 1;
        break;
    }
}

Combine setting of two bits in a bitmask

This gives the same result:

print decbin(1 << 2 | 1 << 9);

1 << 2 results in 4.
1 << 9 results in 512.
512 + 4 = 516
decbin(516) = 1000000100

Now this isn't a usual || statement you're doing the following:

101001 | 010110 = 111111
41     + 22     = 63

So in Laymen's terms, you're merging the values.

You could essentially put it in a function:

function bit_shiftlist(array $nums = [], bool $left = true){
  $ret = 0;
  foreach($nums as $value){
    $ret += $left ? 1 << $value : 1 >> $value;
  }

  return $ret;
}

$mask = bit_shiftlist([2, 9]);

var_dump($mask);       // 516
var_dump($mask ^ 512); // 4
var_dump($mask ^ 4);   // 512
var_dump($mask & 4);   // 4
var_dump($mask & 8);   // 0 - unexisting bit in both value 512 and 4.

How to Implement a Bitmask in PHP