Bitwise Operation Explained

• Download bitwise_operation - 2.76 KB

Background

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

Bitwise operation are really joy to use, if used with care it gives a tremendous good look over 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) in 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

512	256	128	64	32	16	8	4	2	1
0	0	0	0	0	0	1	1	0	1

Shaded cell indicates power of each bucket, higher order all bucket are actually exists, but we ignored 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 call 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 bucket in the bit pattern has 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, so we can conclude for a Even Number the right most bit must have a value ZERO, and for a 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 lets analyze another problem, “Find out whether a number has a form of power of 2 or not” i.e. all the number 1,2,4,8,16,32,64.128……. has a form of power of 2. How to find this out? I am going to give two solutions,

If you closely look at the bit pattern of all the number has 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:

Number	128	64	32	16	8	4	2	1
128	1	0	0	0	0	0	0	0
128-1=127	0	1	1	1	1	1	1	1
128 bitwise-AND 127	0	0	0	0	0	0	0	0

Voila, we can use this property indeed. Lets 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 variable without using the third one. The naïve algorithm uses the arithmetic operator to do so. The smarter way to do is to use Bitwise-XOR operation, the XOR operation has a unique property: returns 0 when the bits has the same value (both zero, or both one) and returns 1 when their values are different (one is zero 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 is three sequential bitwise-XOR operations, which swaps the value in-turn. Awesome, lets see an example.

Initially bit-pattern of a and b is:

a	0	0	0	0	0	1	0	1
b	0	0	0	0	0	1	1	0

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

a	0	0	0	0	0	0 (*)	1 (*)	1
b	0	0	0	0	0	1	1	0

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

a	0	0	0	0	0	0	1	1
b	0	0	0	0	0	1	0 (*)	1 (*)

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

a	0	0	0	0	0	1 (*)	1	0 (*)
b	0	0	0	0	0	1	0	1

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 pointer 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 part (one for predecessor and another for successor) the storage requirement getting higher. A bitwise-XOR operation can compresses 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 calculation has 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 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 example of using bitwise Operation. In my 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