C++ Tricks: Part II

Another set of tricks.

I am going to outline a couple of more tricks that are used for interviews and overall cool things to know:

How to identify the endianness of a machine:
The easiest way to do this is using a pointer to a short, and figuring out if the low order is a certain value that you expect from a big endian or little endian byte order.

bool isBigEndian()
{
     short s = 1;

     // big Endian if MSB == 0
     return (*((char*)&s) == 0);
}

Another trick is to use an unsigned integer as a set data structure. However, it's limited to holding only 32 values. Usually this is enough, but sometimes it's not. In any event, here's the process that goes into it.

You can look at an unsigned integer as a 32-bit integer, where the ith bit (0-indexed) is set to one (1) if and only if it is within the set, and zero (0) otherwise. Therefore, to add something to a set, there is a trick to use:

          x |= (1<<(i));

This will get the ith bit for you and bitwise-OR it and store it in the variable x. Usually it can be used like this for computing set-type problems, like the TSP-related problems, permutation, backtracking problems, and the like. Of course, to remove the set, there is a similar trick:

         x &= ~(1<<(i));

This will flip all the bits to a one (1) except for the i-th bit and bitwise-AND it with x. Therefore, the only bits that are changed within x was the i-th bit, everything else stays the same. This technique is quite useful.

Tricky way to check if a string is a palindrome. It takes n/2 checks such that n is the length of the string in consideration. The algorithm to do so is to check the mirror image of the indices since they should be identical in a palindrome. (Front<->End) The code follows:

     int len = str.size();
     for (int i = 0; i < len/2; ++i) {
          if (str[i] != str[len-1-i]) {
               return false;
          }
     }
     return true;

Obtaining the offset of a data member from a structure. This is quite useful. The key to this idea is that it is based on the rule that if you ever take the address-of (&) operator on an element that is dereferenced, it does not evaluate what's being dereferenced. The code follows:

      typedef struct B {
           int x;
           char y;
      } B_t;
      typedef struct A {
           char a;
           int b;
           short c;
           B_t d;
           long long e;
      } A_t;
      To find the offset of member 'e' within
      type A_t, you need to know the padding infrastructure.
      This could get complicated, so this is a better way:

      unsigned int offset = (unsigned int)(&((A_t*)NULL)->e);

Because it does not evaluate the NULL dereferencing e, this just calculates where the variable e is within the A_t structure. This is quite useful in things such as the list-head problem, which will be shown in an upcoming article. And since NULL is actually ((void*)0), the starting address of the structure in this case would be zero (0), which is the reason why it would give us the actual offset of where 'e' is stored at.