Introduction
The BIT we talk here is the smallest unit in binary: 0 and 1.
Using bit for attributes
If we want to assign a set of attributes to an item, a common practice is using mutually exclusive bit value to indicate each attribute and using “SUM” or “OR” operator to group assigned attributes as a single integer value. This solution is neat and fast to be implement in programming.
For example, a file in a file system may have attributes of
- READ
- WRITE
- EXECUTE
We may assign READ, READ and WRITE , READ and EXECUTE, or any combination of attributes to the file. We may use only a single 32 bits (or 64 bits) integer to indicate these attributes. This design allow us to expand the attribute set in future. This is a more practical approach compare to using one field for each attribute design.
In the above example, we may define
- 1 (0001) – READ
- 2 (0010) – WRITE
- 4 (0100) – EXECUTE
- 8 (1000) - HIDDEN
Note that each attribute should occupy a bit position and it shouldn’t overlap with other attributes else we will not able to identify their actual attributes in later stage.
Thus,
- 5 (0101) indicate READ + EXECUTE
- 2 (0010) indicate WRITE
- 7 (0111) indicate READ + WRITE + EXECUTE
- 6 (0110) indicate EXECUTE + WRITE
- 0 (0000) indicate No attributes defined
Using bits for states
In some situation we need a range of bits to indicate some kind of states. The one bit one attribute design doesn’t fit well here.
For example, a document may have one of the following states but never possess more than one state at a time:
- Draft
- Waiting for approval
- Approved
- Rejected
- Canceled
There are 5 states above, we may use 4 bits (3 bits is sufficient for above case) to present the state as
- 1 (0001) – Draft
- 2 (0010) – Waiting for approval
- 3 (0011) – Approved
- 4 (0100) – Rejected
- 5 (0101) - Canceled
Programming attributes in programming language
We may use only a single variable of type INTEGER to indicate an attribute sets. This design allow the attribute sets to expand in future without changing much in old codes.
Define attributes and states
Assume bit 0-3 (4 bits) is reserved for states and bit 4-7 (4 bits) is reserved for attributes.
const
at_READ = $10;
at_WRITE = $20;
at_EXECUTE = $40;
at_HIDDEN = $80;
st_Draft = 1;
st_Waiting = 2;
st_Approved = 3;
st_Rejected = 4;
st_Canceled = 5;
Set attributes
Use bit operator OR to set attribute:
- B := at_READ OR at_WRITE; // assign READ and WRITE
- B := B OR at_READ; // assign READ to B regardless of B READ attribute or not
Unset attribute
Use bit operator AND NOT to unset attribute:
- B := B AND (NOT at_READ) // unset READ of B
- B := B AND (NOT at_READ) AND (NOT at_WRITE) // unset READ and WRITE of B
Test an attribute is set
Use AND operator to check if READ attribute is set:
- (B and at_READ) = at_READ
Test state
Bits 0-3 is reserve for states, to test if the item is canceled:
- B and $0F = st_Canceled
Set State
Set state to st_Rejected (4):
- B := B and $F0 + st_Rejected
Programming attributes in SQL
It wasn’t easy to perform the above operations in SQL unless the SQL service support bit operator or function. The following solution is using normal mathematical operation to achieve the same bit operation as programming language without using special function.
Division operator in SQL
The division operator ( / ) in SQL has different behavior for integer and floating point division. For example:
- Integer division:
- 1 / 2 is 0
- 2 / 2 is 1
- Floating point division:
- 1 / 2.0 is 0.5
- 2 / 2.0 is 1.0
An integer value divided by 2 is similar as performing a right shift operation for binary value. For example,
- 10 / 2 = 5
- 9 / 2 = 4
Perform a right shift in binary for above numbers:
- 1010 shr 1 = 101 (5 in decimal)
- 1001 shr 1 = 100 (4 in decimal)
Likewise,
- perform 2 right shifts is dividing the value by 4
- perform 3 right shifts is dividing the value by 8
- perform n right shifts is dividing the value by 2^n
Multiplication operator in SQL
The multiplication operator ( * ) for integer works similarly as performing a left shift operation for binary value. For example,
- 5 * 2 = 10
- 7 * 2 = 14
Perform a left shift in binary for above numbers:
- 101 shl 1 = 1010 (10 in decimal)
- 111 shl 1 = 1110 (14 in decimal)
Likewise,
- perform 2 left shifts is multiplying the value by 4
- perform 3 left shifts is multiplying the value by 8
- perform n left shifts is multiplying the value by 2^n
Test the value of least significant bit
The least significant bit of a number is the right most bit in binary presentation of the number. For example, the least significant bit of 10 (1010 in binary) is 0 and 9 (1001 in binary) is 1.
We may use both integer or floating point division to check the least significant bit of a number:
i = (n / 2) – (n / 2.0)
i = 0 indicate least significant bit is off
i <> 0 indicate least significant bit is on
For example,
- 10 / 2 – 10 / 2.0 = 5 – 5.0 = 0 (least significant bit is 0)
- 9 / 2 – 9 / 2.0 = 4 – 4.5 = –0.5 (least significant bit is 1)
Test an attribute is set
To check if an at_EXECUTE ($40) attribute is set in SQL, we may use
WHERE ((Attribute / 64 / 2) - (Attribute / 64 / 2.0) <> 0
Set attribute
The following SQL set at_EXECUTE ($40) for rows that don’t have at_EXECUTE set:
UPDATE Table
SET Attribute = Attribute + 64
WHERE ((Attribute / 64 / 2) - (Attribute / 64 / 2.0) = 0
Unset attribute
The following SQL unset at_EXECUTE ($40) for rows that have at_EXECUTE set:
UPDATE Table
SET Attribute = Attribute – 64
WHERE ((Attribute / 64 / 2) - (Attribute / 64 / 2.0) <> 0
Test States
The following SQL retrieve all rows that has state of st_Canceled (5):
SELECT *
FROM Table
WHERE Attribute – (Attribute / 16) * 16 = 5
Set States
The following SQL set all rows to state of st_Canceled (5):
UPDATE Table
SET Attribute = (Attribute / 16) * 16 + 5
