Click here to Skip to main content
Click here to Skip to main content

Bitwise Operation Explained

, 19 Aug 2008 CPOL
Rate this:
Please Sign up or sign in to vote.
Few well known bitwise operation problem collection

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 gives 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:

512

256

128

64

32

16

8

4

2

1

0

0

0

0

0

0

1

1

0

1

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:

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. 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:

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” 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).

a

0

0

0

0

0

0 (*)

1 (*)

1

b

0

0

0

0

0

1

1

0

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).

a

0

0

0

0

0

0

1

1

b

0

0

0

0

0

1

0 (*)

1 (*)

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).

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 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

  • 19th August, 2008: Initial post

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

programmersmind
Software Developer (Senior) Rebaca Technologies
India India
int main(){
while(!isSleeping())
{
write_code();
}
return 0;
}

Comments and Discussions

 
GeneralMy vote of 5 Pinmembermanoj kumar choubey28-Feb-12 18:55 
GeneralIsEven.. fora double PinmemberCanopenR30-Mar-09 11:16 
Generalswap [modified] PinmemberJ0ker12-Sep-08 18:39 
GeneralRe: swap Pinmemberprogrammersmind15-Sep-08 6:57 
GeneralRe: swap PinmemberBartosz Wojcik23-Sep-08 9:19 
RantRe: swap - undefined behavior PinmemberJ0ker24-Sep-08 6:07 
GeneralBeware of signed numbers Pinmemberbillyvas25-Aug-08 20:38 
GeneralRe: Beware of signed numbers Pinmemberprogrammersmind3-Sep-08 12:28 
GeneralOther Operations PinmemberHawk77725-Aug-08 15:47 
GeneralRe: Other Operations Pinmemberprogrammersmind25-Aug-08 16:10 
GeneralRe: Other Operations Pinmemberwtwhite25-Aug-08 16:57 
GeneralRe: Other Operations PinmemberHawk77725-Aug-08 21:15 
General"Find out whether a number has a form of power of 2 or not" Pinmemberphinecos21-Aug-08 17:03 
GeneralRe: "Find out whether a number has a form of power of 2 or not" Pinmemberpeterchen25-Oct-08 12:25 
GeneralComment Pinmemberpwasser19-Aug-08 15:11 
GeneralRe: Comment Pinmemberprogrammersmind19-Aug-08 15:15 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.141223.1 | Last Updated 19 Aug 2008
Article Copyright 2008 by programmersmind
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid