Swap Values, no third variable

A classic problem asked in many interviews and such. And almost every genius will tell you that its simple.

swap(int *x,int *y)
  *x += *y;
  *y = *x - *y;
  *x = *x - *y;

Simple right? Wrong!
what happens if one value is 2147483647 and the other is 2147483640 ?
You will definitely overflow x and make a mess of it!

So whats the foolproof way?  Observe!

swap(int *x, int *y)
 *x ^= *y;
 *y ^= *x;
 *x ^= *y;

So how is it done? Bit-wise Xor operation. Faster, better and guaranteed to get you laid. For more info on bit wise xor Google it or click here

Technorati Tags: , ,


Efficient way to print int in binary format

void printBinary(int *intVal){
  register unsigned int mask;
  mask = 1<<((8*sizeof(int))-1);
    print("%d",((*intVal & mask)/mask));
  while((mask >>= 1) & -1);

Ok, Sorry I did not put any comments in the code, simply because I want it to look short and sweet. Now let me elaborate a bit on how this works.

void printBinary(int *intVal){

We are taking a pointer here, so make sure your calling function sends an address and not the value.

  register unsigned int mask;

Register for speed, we need to have an unsigned int.

mask = 1<<((8*sizeof(int))-1);

Ok, let me explain this one step at a time
Step 1: Get Size of integer.
Step 2: Multiply it with 8 ( we need the Size in Bits, not in bytes).
Step 3: Subtract this value by 1
Step 4 : Left Shift 1 by the value obtained by Step 3 calculation.

How does this work?
Assume that the platform where you are gonna run this code represents binary as 4bytes. So
Step 1: 4 Bytes
Step 2 : 4×2 = 32 Bits
Step 3 : 32 -1 = 31
Step 4 : Left shift 1 (binary : 00000000000000000000000000000001) by 31 times = binary : 10000000000000000000000000000000

    print("%d",((*intVal & mask)/mask));
  while((mask >>= 1) & -1);

Now comes the bit tricky part, so how do we do this? Quite simple once you get a hang of it.

First we do a bitwise and on the value we got from the calling function and the mask. We then divide it by mask.

Initially, the mask will be at the leftmost position (which is usually the sign bit, hence will be 1 if the value is negative). Now if the number you passed on was signed and negative, then ‘and’ing with mask will ensure that only signed bit will remain and makes the rest of the bits as ‘0’. Now you divide this value by mask itself. Hence you will get value with 1.

Now if the bit was zero then the result of  ‘and’ing would have been all zeros. Thus dividing the value with mask would have yielded 0.

Ok, now the next step, we right shift the mask by 1. So we will end up with 01000000000000000000000000000000 , first time around. We then do a bitwise and with -1 which is represented as binary all 1’s. Thus this while loop will remain true till we keep right shifting 1 in the mask all the way to the right, and finally dropped. By that time we would have printed the value of  referenced by intVal pointer in binary form.

Simple? 🙂

Tip: If you know the size of integer in your platform then you can get some more performance and simplicity by pre calculating what number will be 1 followed by all zeros. For 4 bytes this value will be 2147483648.

Cscope + Notepad++ Coding nirvana!

Loved Cscope on cygwin, but hated the fact that you anything you select will open up in Vi, and then do some keyboard voodoo to get back to the cscope window?

Or are you one of those fan of notepad++ awesomeness but love the way cscope hunts for stuff for ya?

Fear not, there is a way both your sweethearts can now play with you, all at the same time for an awesome threesome 😉

Just export these lines before you fire up Cscope

export CSCOPE_EDITOR="/cygdrive/c/Program Files/Notepad++/notepad++.exe"
export CSCOPE_LINEFLAG="-n%s"

Please note : Change the CSCOPE_EDITOR path to where your notepad++ is currently residing. For your convenience, I have included the path that is default for Normal install of notepad++.

Better still, put it in a script file (or perhaps bashrc).

Got a better suggestion? Post a comment 🙂