Talk a Bit about Bits!

Why Bits?

Given a high-level system, the smallest unit we can define is a Byte. A byte consists of 8 bits of information. Bit-wise hacks are needed if you want to operate on data units smaller than a byte. Though the inputs to these operations is a byte, they operate on each bit of the byte to yield the output. As an embedded engineer, I see many use-cases for these:).

If you want to have a bitmap for some book-keeping or have to run compression algorithms on data or packing the data for efficient transfer across the network – you would need bit manipulation!

So, let’s decode this today.


Bitwise operations

The bit-wise operations supported are :

  • AND: &
  • OR: |
  • XOR: ^
  • NOT: ~
  • Bitwise Left Shift : << and
  • Bitwise Right Shift : >>

Shown in the table below are the various operations performed on two bits a and b.

a b a&b (AND) a|b (OR) A^b (XOR)
0 0 0 0 0
0 1 0 1 1
1 0 0 1 1
1 1 1 1 0

Table 1. Bitwise operations summarized

Note that these are different from the Boolean operations “&&” and “||”. Boolean operations result in only Boolean output True of False (operate on inputs converted to Boolean expressions) while bit-wise operations have result in integral form short, int, char, unsigned, bool, long etc, after performing the operation at bit level on given inputs (need not only be Boolean).

Usage example :

AND operation can be used to check if a particular bit is set
OR operation can be used to SET a particular bit
XOR operation can be used to RESET/CLEAR a bit

Bit Shift operators

The left shift “<<” is an arithmetic operator that can operate on signed integers. The operation of shifting a number “a” to left by “n” bits yields the same result as multiplying “a” by (2 power n).

Similarly, the right shift operator “>>” on the unsigned integers yields same result as dividing “a” by (2 power n).

During the shift operations, the emptied bits are populated with zero for positive integers and “1” for negative integers. This is because post the shift, padding operation uses the MSB  (most significant bit) which is used to indicate the sign.  Shown below in Fig(1) are the example of bit shifts on unsigned 8-bit data (indicated by bits B0 to B7).

shifts.png
Fig 1. Bit shift operations

Result storage in C with bit-wise operations

When we use bitwise operations, the result of the operation is stored in a temporary variable. If we do not assign the operation to a variable it is LOST!! So, in the example below- if you expected it to print 12, it would still print value contained in a, that is 3.

For it to print 12, we would need to replace the line with the shift operation with the one shown in BLUE. We need to assign back the operation to the variable of interest – in this case, the result shall be stored in the variable “a”.

We can also combine the assignment operator into the expressions as shown in RED.

int main()
{
int a = 3;
int n = 2;
// operation : Left shift variable "a" by "n=2" bits
a<<n; // use a = a<<n; 
// or could  be written as : a<<=n; 
printf("Result  is %d", a);
}

Usage

We can use bit operations for book-keeping, packing data, extracting bit level info from some packed data, condition checks, reading a memory mapped I/O register, encryption, compression, checksum, endianness conversions when using sockets and so on. In this section, let’s go over some examples of usage.

Trick to efficient condition checks

Some time ago I was asked to write a CSS parser for this project on an embedded processor. And, obviously, I was constrained by CPU cycles I could use for this and also the memory consumption. So, I had to make sure I parsed the data exactly once, to extract information and also see if I can make the entire implementation processor cycle and memory friendly. I essentially had to extract URLs from CSS data and I was parsing the data and checking for characters “u”, “{” and “}”.

From ASCII table these have values :

‘u’ is 0x75

‘{‘  is 0x7B  and

‘}’ is 0x7D, only the right 4 bits differ and last bit is 1, picking all the fields that are set in all three yields 0x71, that shall be used as a MASK next.

example css data :  
#tag-id1{ ..text...url("http://www.geekgirldecodes.com") }
// Mask is 71 to match 'u' '{' '}' subset 
// Suppose pChar points to characters in the String being scanned.

// Without below MASK check, if we directly went to check against three 
// required characters u , { and } : we would end up performing these three 
// checks for all ASCII characters there are.

while((*pChar)&&(!(*pChar & MASK == MASK))){
 pChar++; // if it does not match subset , keep moving ahead on string
 }

// But, with ABOVE mask, we will only perform below match with 'u', '{' and '}' 
//only on 8 character subset, that may match the MASK "0x71" (between 70 to 7F)
 if(*pChar == 'u'){
 // do some operation
 }
 else if(*pChar == '{'){
 // do some operation
 }
 else if(*pChar == '}'){
 // do some operation
 }

Book Keeping bitmap

Suppose you want to keep track of occupancy of  8 seats in a room. If you put up some sensors that can detect when a person sits and notifies your system, the code designed for bookkeeping can use a bitmap internally.

Once the sensor on the seat detects a signal and your system needs to update the status, all this would need is an 8-bit bitmap, with each bit set aside per chair. This bit can be set to 1 if the seat is occupied else 0. To look up if seat 7 is occupied or not – we only need to check if this bit corresponding to seat number, is set in the bitmap as in below example code.

// Set aside 8 bits : 0000 0000 (8 bits for 8 seats)
// If a bit is set in the bitmap, it indicates seat occupied :
// example bitmap is 0100 0000 (7th seat occupied)

bool isSeatOccupied(int seatNumber){
return (bitmap & (1<< seatNumber)) ;
}

Obviously, you don’t need to do this if you are not a memory constrained system. I am giving this example to give you a feel of how you could use it if you needed to.

This would be useful in a memory constrained systems – like micro-controllers. While monitoring various I/O pins we could maintain a bitmap and use this type of implementation to check if a certain pin is set or not.

Packing data 

Say you want to transfer data over limited Bandwidth network. And, we have the following information to be transmitted :

id that can range from 0 -125  
Another field with range 0 - 257 
A flag with state information of 4 different states

How would you pack this data efficiently ?

Design a packet structure to do this , implement  pack() to  pack the data in the packet structure designed  and an unpack() function that reads the data packed.

Do mail me your answers @ decodergirlblog@gmail.com


Also, if you want some more bit manipulation tricks: Check here

But, I do hope that you don’t use for unnecessary use cases, just because you know how to and also want to show you can write tricky code ;). Make sure you write code that you will be able to easily understand and importantly be able to debug if any issue crops up at a later time!

In general when we use bit tricks, it’s a good thing to leave comments for those who may inherit your code.

So, until next time- keep decoding.

Also, if you have used any bit tricks in your code, do let me know in the comments below. 🙂

3 thoughts on “Talk a Bit about Bits!

  1. @Mortoray Boolean operations && and || operate with inputs viewed boolean expressions and are short circuiting operators
    where as bitwise logical operations operate on integral inputs , can include bool inputs as well but they are not short- circuiting type. Is leaf a new language you are designing ? 🙂

    Like

    1. Yes, perhaps it makes a difference for short-circuiting in current languages, though I think it could probabl be applied to the bitwise ones as well. hmm, I’ll have to think about that.

      Leaf is a new language I’m designing yes. I recently worked on improving boolean operator support. 🙂
      http://leaflang.org/ though mainly I talk about new things on my main site https://mortoray.com/

      Like

  2. Boolean operatiosn are really the same as bit-wise operations except limited to a variable of 1-bit in size. 🙂
    I’ve actually implemented the operators this way in Leaf, so all the logical operators also work on booleans.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s