Bitwise Operation Explained

• Download source - 2.76 KB

Background

After reading the wonderful article, “An introduction to bitwise operators” by PJ Arends, I thought of extending the scenario further and thought of putting few common uses of bitwise operations that I have faced in real life. The above mentioned article is indeed a pre-requisite to this one.

Bitwise operations are really a joy to use. If used with care, they give a tremendous good look to the code and performance too.

Using the Code

So, let’s start with a vintage problem introduced by Denis Ritchie, “You have a variable (say int) at your disposal, you need to find out how many bits are set (i.e. 1) in the bit pattern beneath”.

Say, you have declared an int var = 13, then the bitwise structure of var will be:

Shaded cells indicate the power of each bucket, in the higher order, all buckets actually exist, but we ignored them for this example. Now let’s write a method that will return the number of bit sets in this variable:

int __numOf_SET_Bits(int var){
 if (var==0) return 0;
 else return (var&01)?1+__numOf_SET_Bits(var>>1):__numOf_SET_Bits(var>>1);
}

A simple recursive function that counts the total number of set bits in the bit pattern for a variable. In the heart of the function, there exist two bitwise operations:

1. One which checks whether the current right most bit has a numeric value of 1 or not (checks by a bitwise AND with a 1), if so increment the total count by one.
2. While calling the function recursively, make a right shift by 1 over the variable, thus truncating the right most bit of the variable (and left most bit will be padded by a zero).

There also exists an iterative version of this algorithm, please refer “C Programming Language” book by Denis Ritchie.

Ok, now let’s analyze another similar kind of problem, “Find out whether a number is even or odd”. The naïve algorithm is:

#define isEven(a) \
  ((((a)%2)==0)?1:0)

But if you closely look at the bit pattern for any variable, you can see all the buckets in the bit pattern have a power of even number except the right most one (which has a power of 1). Now since (Even Number + Even Number) = Even Number and (Even Number + Odd Number) = Odd Number, we can conclude for a even number the right most bit must have a value ZERO, and for an odd number the right most bit must be set to ONE. So let’s try to write a function/macro considering this property:

#include <stdio.h>
#define isEven(a) \
  ((((a)&01)==0)?1:0)
int main()
{
 int var=1;
 if(isEven(var)){
    printf("%d is a even number \n",var);
 }
 else
    printf("%d is a odd number \n",var);
 return 0;
}

Wow, this one looks cool.

Now let's analyze another problem, “Find out whether a number has a form of power of 2 or not”, i.e., all the numbers 1,2,4,8,16,32,64.128……. have a form of power of 2. How to find this out? I am going to give two solutions.

If you look closely at the bit pattern, all the numbers have a form of power of 2, for all of them exactly one bit is set, rest all are zero in the bit pattern. Now if we bitwise-AND-ed that number with a number having a value less than 1, the operational outcomes will be zero. Consider the example of 128:

Voila, we can use this property indeed. Let's write our first version of the code:

#include <stdio.h>
#define __isPower_of_TWO(a) \
 (((a)&(a-1))==0)?1:0
int main(){
 int arr[] = {1,2,3,4,5,8,9,16};
 int i=0;
 for(;i<sizeof(arr)/sizeof(arr[0]);i++){
        if (__isPower_of_TWO(*(arr+i)))
           printf("%d has a form of Power of Two \n",*(arr+i));
        else
           printf("%d is not in the form \n", *(arr+i));
 }
 return 0;
}

Now consider another way to do this:

#include <stdio.h>
#define __isPower_of_TWO(a) \
 (((a)&(-a))==a)?1:0
int main(){
 int arr[] = {1,2,3,4,5,8,9,16};
 int i=0;
 for(;i<sizeof(arr)/sizeof(arr[0]);i++){
        if (__isPower_of_TWO(*(arr+i)))
           printf("%d has a form of Power of Two \n",*(arr+i));
        else
           printf("%d is not in the form \n", *(arr+i));
 }
 return 0;
}

Really it’s another nice way to do the same job.

Now consider another famous problem of swapping the value of two variables without using the third one. The naïve algorithm uses the arithmetic operator to do so. The smarter way to do it is to use Bitwise-XOR operation, the XOR operation has a unique property: returns 0 when the bits have the same value (both zero, or both one) and returns 1 when their values are different (one is zero and the other is one). Let’s first write the logic, and then we will see it with an example.

#include <stdio.h>
void __SWAP(int *a,int *b){
 *a = *a ^ *b;
 *b = *a ^ *b;
 *a = *a ^ *b;
}
int main()
{
 int a=5, b=6;
 printf("Before swap: a=%d <=====> b=%d \n",a,b);
 __SWAP(&a,&b);
 printf("After  swap: a=%d <=====> b=%d \n",a,b);
 return 0;
}

In the core of the logic, there are three sequential bitwise-XOR operations, which swap the value in-turn. Awesome, let's see an example.

Initially bit-pattern of a and b is:

Now after first bitwise-XOR operation, value of “a” and “b” become: (check only the bit-pattern of “a” will change, “b” will remain the same for this step. (* indicates which bit has changed the state).

After the second operation: (here only “b” will be changed, and check bit pattern of “b” now contains original bit-pattern of a, so the value of “a” has been shifted over b).

After the third operation: (here only value of “a” will be changed, and voila! Look the value of “b” has been shifted over “a”, swap operation got passed).

Now, let’s analyze a data structure building technique, named “XOR linked list”. A doubly linked list is a list for which each node contains a data member and two pointers pointing to the previous and next item in the list. For the last node in the list the value of the “next” is NULL, for the first node (head) the value of “prev” is NULL. If a head itself contains a NULL, then the list is empty. Since each node contains two address parts (one for predecessor and another for successor) the storage requirement gets higher. A bitwise-XOR operation can compress the same information into one address field.

Consider the following code:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct XOR_based_Node {
 int data;
 unsigned long compressedAddress;
}node;
node* head = NULL;
void add_element_to_list(node** headRef, int data)
{
  node *newNode = (node*)malloc(sizeof(node));
 assert(newNode);
 newNode->compressedAddress = (unsigned long)(*headRef);
 newNode->data = data;
 if(*headRef != NULL)
  (*headRef)->compressedAddress ^= (unsigned long)newNode;
 *headRef=newNode;
}
void printList(node* head)
{
  unsigned long prev = 0;
 while(head) {
  unsigned long next = prev ^ head->compressedAddress;
  printf("%d ", head->data);
  prev = (unsigned long)head;
  head = (node *)next;
 }
 printf("\n");
}
int main(void) {
 int i=0;
 for(;i<10;i++)
   add_element_to_list(&head,i);
 printList(head);
 return 0;
}

In this code, all the address calculations have been done in a single address field (that we have per node). This field has been calculated while we try to push a node in the list using bitwise-XOR operation and the proper memory location has been fetched using bitwise-XOR operation too.

Given below is the output:

bash-3.2$ gcc -g -o hello XoR_List.c 
bash-3.2$ ./hello
9 8 7 6 5 4 3 2 1 0 
bash-3.2$

Conclusion

There are tons and tons of real life examples of using bitwise operations. In the second part of the article, I'll focus on the data structure only (heap, priority queue, red-black tree, splay tree) and will try to explain how a bitwise operation can help us greatly to implement those.

References

1. "C Programming Language" by Denis Ritchie

History

• 19^th August, 2008: Initial post