BITs operation in SQL

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