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 network – you would need bit manipulation !

So, let’s decode this today.

Bit wise operations

The bit-wise operations supported are :

  • AND : &
  • OR : |
  • XOR : ^
  • NOT : ~
  • Bitwise Left Shift : << and
  • Bitwise Right Shift : >>
Bit 1  Bit 2 AND OR 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 operation at bit level on given inputs (need not only be Boolean).

Usage example :

AND operation can be used to check if a particular position is set

OR operation can be used to reset a particular position

XOR operation can be used to set a particular position

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 same result as multiplying “a” by (2 power n).

Similarly, the right shift operator “>>” on 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 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) .

Fig 1. Bit shift operations

Result storage in C with bit-wise operations

When we use bit wise 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);


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

Sometime 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 book keeping 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 a 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 for giving 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 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 are 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. 🙂