Programming

Efficient storage and retrieval of boolean values using bitwise operations

Since each digit in a binary number is only composed of one of two possible values, 0 or 1, a binary number can be thought of as a series of switches.

Each of these switches can be thought of as a TRUE or FALSE value if it is 1 or 0. So a binary number can then be used to represent a list of boolean values. If we assigned a property to each bit in this binary number we would be able to store the value of a set of boolean properties (five properties in this case) within a single number.

For example, suppose you wanted to limit access to your computer for certain users, and you wanted to store what privileges each user had within a database. You could create a table for the users and create fields for CAN_READ, CAN_WRITE, CAN_EXECUTE. This would work fine, but using a binary number as the storage mechanism for the privileges can make this process much more elegant and efficient.

Take a three bit binary number, for instance, 111 (read that as one-one-one). Each bit could be assigned a boolean value. So the rightmost bit could represent the boolean value for CAN_READ, the middle bit could represent CAN_WRITE, and the leftmost bit could represent CAN_EXECUTE. Therefore switching any of these three values to 0 within the binary number would specify that that privilege was not granted for a particular user. For example, the binary number 011 (otherwise written as 3 in decimal) would specify that a user could read and write files on the computer but could not execute applications.

To create this kind of arrangement create a table to hold the privileges (a.k.a. permissions). Insert entries into this table for each bit in the whole binary number. Next create a users table that has a field for holding a number that represents what privileges a user has. In the permissions table each entry will only have one bit turned on, while the entries in the users table could have multiple bits turned on because a user could have more than one privilege on the computer.

So here is the SQL to create those two tables and fill them with data:

CREATE TABLE PERMISSION
(
	bit			BIGINT NOT NULL UNIQUE,
	name			VARCHAR( 32 ) NOT NULL UNIQUE,
	description		VARCHAR( 2048 ) NOT NULL,
	PRIMARY KEY ( bit )
);
 
CREATE TABLE USER
(
	id			SERIAL,
	name			VARCHAR( 32 ) NOT NULL UNIQUE,
	bitpattern		BIGINT NOT NULL,
	PRIMARY KEY ( id )
);
 
INSERT INTO PERMISSION ( bit, name, description )
	 VALUES ( 1, 'CAN_READ', 'User can read files');
INSERT INTO PERMISSION ( bit, name, description )
	 VALUES ( 2, 'CAN_WRITE', 'User can write files');
INSERT INTO PERMISSION ( bit, name, description )
	 VALUES ( 4, 'CAN_EXECUTE', 'User can execute applications');
 
INSERT INTO USER ( id, name, bitpattern )
	 VALUES ( 1, 'admin', 7);
INSERT INTO USER ( id, name, bitpattern )
	 VALUES ( 2, 'manager', 3);
INSERT INTO USER ( id, name, bitpattern )
	 VALUES ( 3, 'enduser', 1);

Here’s what they look like in a more visual way: 

…and filled with data:

Now to pull the permissions for a particular user out of the database we will use the bitwise AND operator (&). This operator compares two numbers binary bit by binary bit. If the bit at a particular position in both numbers is 1, then the bit at that position in the resulting number is 1, otherwise it is 0. So for example if we took the numbers 011 (3 in decimal) and 100 (4 in decimal) and performed a bitwise AND operation on them it would look like this:

011
100
—-
000

The result is 000, because none of the 1 bits overlapped. If the first number was the permissions a user had and the second number was the permission to execute applications, then performing a bit AND operation on these two numbers would determine that that particular user could not execute applications. If it had resulted in any other number besides 0 it means that they could execute applications. Therefore to query the database to find the permissions of a particular user we would perform the following:

SELECT * FROM USER, PERMISSION 
	  WHERE (bitpattern & bit != 0) 
	  AND (name = 'manager');

Which would search through the PERMISSION table and only return those entries where a bitwise AND operation between the ‘manager’ user’s permissions number and the bit of the privilege did not return 0. In this case it would return the entries for CAN_READ and CAN_WRITE.