Coding Away

The classic way of swapping to variables uses a temporary variable. In C++ it looks something like:

void swap1(int &a, int &b)
{
     int c=a;
     a = b;
     b = c;
}

Some developers can’t stand that they need a temporary variable to make the swap, and prefer to write:

void swap2(int &a, int &b)
{
     a ^= b;
     b ^= a;
     a ^= b
}

Assuming that a and b are pointing to different memory locations, this actually works.
It is based on the fact that [ (a^b)^a = b ] and [ (b^a)^b = a ]

While this seems like a cool trick, is it really worth writing it? Or should you stick with the classics?
I say it is not worth it! Stick with the classics!!!

In fact:

It is slower

swap1 requires 3 assignments.
swap2 requires 3 XORs and 3 assignments.

If you are not convinced, here is the assembly generated by VS for swap1 (you get similar results with gcc and other compilers):

6:    void swap1(int &a, int &b)
7:    {
00401030   push        ebp
00401031   mov         ebp,esp
00401033   sub         esp,44h
00401036   push        ebx
00401037   push        esi
00401038   push        edi
00401039   lea         edi,[ebp-44h]
0040103C   mov         ecx,11h
00401041   mov         eax,0CCCCCCCCh
00401046   rep stos    dword ptr [edi]
8:        int c;
9:        c = a;
00401048   mov         eax,dword ptr [ebp+8]
0040104B   mov         ecx,dword ptr [eax]
0040104D   mov         dword ptr [ebp-4],ecx
10:       a = b;
00401050   mov         edx,dword ptr [ebp+8]
00401053   mov         eax,dword ptr [ebp+0Ch]
00401056   mov         ecx,dword ptr [eax]
00401058   mov         dword ptr [edx],ecx
11:       b = c;
0040105A   mov         edx,dword ptr [ebp+0Ch]
0040105D   mov         eax,dword ptr [ebp-4]
00401060   mov         dword ptr [edx],eax
12:   }

While for swap2 the assembly generated by VS is:

14:   void swap2(int &a, int &b)
15:   {
00401080   push        ebp
00401081   mov         ebp,esp
00401083   sub         esp,40h
00401086   push        ebx
00401087   push        esi
00401088   push        edi
00401089   lea         edi,[ebp-40h]
0040108C   mov         ecx,10h
00401091   mov         eax,0CCCCCCCCh
00401096   rep stos    dword ptr [edi]
16:        a ^= b;
00401098   mov         eax,dword ptr [ebp+8]
0040109B   mov         ecx,dword ptr [ebp+0Ch]
0040109E   mov         edx,dword ptr [eax]
004010A0   xor         edx,dword ptr [ecx]
004010A2   mov         eax,dword ptr [ebp+8]
004010A5   mov         dword ptr [eax],edx
17:        b ^= a;
004010A7   mov         ecx,dword ptr [ebp+0Ch]
004010AA   mov         edx,dword ptr [ebp+8]
004010AD   mov         eax,dword ptr [ecx]
004010AF   xor         eax,dword ptr [edx]
004010B1   mov         ecx,dword ptr [ebp+0Ch]
004010B4   mov         dword ptr [ecx],eax
18:        a ^= b;
004010B6   mov         edx,dword ptr [ebp+8]
004010B9   mov         eax,dword ptr [ebp+0Ch]
004010BC   mov         ecx,dword ptr [edx]
004010BE   xor         ecx,dword ptr [eax]
004010C0   mov         edx,dword ptr [ebp+8]
004010C3   mov         dword ptr [edx],ecx
19:   }

This should make it clear how swap2 is less efficient than swap1.

Provides no real advantage

The only real advantage is the rush you get from having written a piece of unreadable code using cool tricks.

The fact that you save sizeof(int) bytes on the stack in 99.99% of the cases is not a real good reason to write swap2 instead of swap1. Perhaps it is advantageous in some recursive situation, where every byte in the stack counts and where you don’t want to make an extra function call to a swap function. I’d have to see such code to believe it.

It is not readable

I know. If you wrote it, you know what it does. But what about the rest of the world?
The problem is that for many others swap2 is not going to be readable and it is going to generate only confusion, not amazement.

In the long term it is far better to write readable code than some cool unreadable and inefficient piece of work.

Keep it simple!!

Sometimes it is useful to find out if a particular integer represents a power of two. You can find that out with a simple trick.

A power of two in binary is represented by a all zeros, except for a single one. For example 00010000 is a power of two (2^4).
In fact you can calculate the n-th power of 2 with:

int power2(int n)
{
     return (1<

If you subtract one from a power of two, you obtain a number which binary representation is a sequence of ones. Example in binary:

00010000 - 1 = 00001111

If you take this number and perform a logical AND with the original power of two you obtain a flat zero!
Example:

00010000 &
00001111
———
00000000

If you have any other number that is not a power of two, this doesn’t work anymore and you’d never obtain a zero.
For example let’s take 18, which is not a power of two.

18 in binary is 00010010
00010010 - 1 = 00010001

00010010 &
00010001 =
———
00010000

Another example. Let’s take 14 which is another number that is not a power of two:

14 in binary is 00001110
00001110 - 1 = 00001101

00001101 &
00001110 =
———
00001100

In general you’ll find that the result of (X-1)&X always contains at least a one… unless X is a power of two! Cool!

For this simple reason you can find out if an integer is a power of two with something like:

boolean isPowerOf2(int x)
{
    return ((x-1) & x)==0;
}

Enjoy!

I keep seeing code to calculate leap years implemented with functions like:

bool isLeap_wrong1(unsigned int year)
{
    return !(year%4);
}

bool isLeap_wrong2(unsigned int year)
{
    return !(year%4) && (year%100) ;
}

These are inaccurate because they don’t take in consideration all the rules of the Gregorian calendar adopted by most countries in the world.

In the Gregorian calendar before the year 1600 AD a leap year was defined as follows:

A year is a defined as “leap year” if it is divisible by 4 but not by 100.

After the year 1600 AD the Gregorian calendar was revised and the leap year defined as follows:

A year is a defined as “leap year” if it is divisible by 4 but not by 100 unless it is also divisible by 400.

This definition is destined to be revised in the future (before 2800 AD) since it is still not perfect; however, in your lifetime you should be fine with it and it is currently the official rule.

Based on this definition, the correct “modern” (past 1600AD) way to find out if a year is a leap year is the following:

bool isLeap(unsigned int year)
{
    return !(year%4) && ( (year%100) || !(year%400) )
}

I can’t help it. I just love the nuisances of C++, and some of the weird things you can write with it.

From time to time I will share some of my favorite examples under “Useless Programming Interview Questions” (UPIQ) category.

Why did I pick this name? Well, the aspects of C++ that I am referring to allow you to write code so strange and unreadable that you’d never do it in real life! Right? The only time you might seriously consider these aspects of the language is if you are a twisted individual asking an useless interview question to a job candidate.

Why do I call these questions “useless”? Because the fact that the candidate knows the answer or not tells you very little about his or her skills. You’d better don’t waste precious interview time in such things. I know it’s fun, but I bet there are much better questions you can ask.

Useless Interview Questions:

Mr.Candidate, please look at this code:

int main()
{
	int a[3]={1};
	int b=1;
	int c[3]={0,2,1};

	a[b[c]]=2;

	printf("a[0]=%dn",a[0]);
	printf("a[1]=%dn",a[1]);
	printf("a[2]=%dn",a[2]);
	return 0;
}

1) Is this valid C++? Can you compile it?
2) If so, what is it going to print to stdout?

Answers:

(more…)