Comparing int with Enum

Problem: this may not be an interview question but it is quite interesting. Let's first look at some examples.  If we have following code that compare int with enum, what will happen (be printed out)? We will test these examples using gcc.

*Updated the post inspired by Nemo's great comments.

enum MY_ENUM{
  MY_OK = 0,
  MY_NOT_OK
};

void foo()
{
   int i = -1;
   enum My_ENUM my_enum = MY_OK;

   if( i < my_enum) printf("I am OK!\n");
   else printf("I am NOT OK!\n");

}

For the above example,  we will see "I am NOT OK!". Why, the reason is in this example my_enum is regarded as unsigned int. Therefore, it will be converted into unsigned before the comparison. After the conversion, it will always be non-negative so the if will take the else branch. But what about this code snippet (just a little bit modification):

enum MY_ENUM{
  MY_OK = 0,
  MY_NOT_OK
};

void foo()
{
   int i = -1;
   enum My_ENUM my_enum = MY_OK;

   if( i < MY_OK) printf("I am OK!\n");
   else printf("I am NOT OK!\n");

}

It will print "I am OK!" instead. The reason is  in this example  MY_OK  is regarded as int.

Why we will see results like this? It is kind of confusing. To find out the things under-hood, we need to look at the C standard. There are several sections related to our problem.

• Section 6.4.4.3 says enumerators have type int. 
• Section 6.7.2.2/4 states that the enumeration type has a compatible type capable of representing the values of all enumerator members.
• Section 6.7.2.2/2 suggests that an enumerator initialized with a constant expressionthat falls outside the range of an int has unspecified or undefined behavior.

Section 6.7.2.2/4 can be used to explain the first example. The compatible type capable of representing the values of all enumerator members is unsigned it, since we only need to represent 0 and 1.Therefore   my_enum is unsigned int. Section 6.4.4.3 can explain the second example since MY_OK is an enumerator.

Then what if you want enumeration type to be int? Just follow Section 6.7.2.2/4 and have the enumeration defined as follow:

enum MY_ENUM{
  MY_NEG = -1
  MY_OK = 0,
  MY_NOT_OK
};

since we only need to represent -1,0 and 1 here, the enumeration type needs to be int.

We should be careful about Section 6.7.2.2/2. Since it suggests if we define something as follow, the behavior will be unspecified.

enum MY_ENUM{
  MY_NEG = -1
  MY_OK = 0,
  MY_BIG = 0x80000000
};

0x80000000 can't be represented in a 32bit int. Though in gcc, the enumeration type is still int here, we cannot expect a uniform behavior on other compilers.

Something about Template Specialization

When you have a generic template class,  some functionalities are not shared by all the data types and they are no needed for some specific data types. Template specialization just kicks in for this occasion. You can first declare a generic template for "all" the data types, then for a specific data type, you can provide a specific implementation. For example, if you want to implement a vector template, but you want to be space-efficient for bool type (e.g., use bit-vector to store them) other than some generic approach (e.g., use one integer to store one bool object). Then you can do as follow:

//generic template
template <typename T>
class vector
{
    // accessor functions and so forth
    private:
    T* vec_data;   // we'll store the data as block of dynamically allocated 
                   // memory
    int length;    // number of elements used 
    int vec_size;  // actual size of vec_data
};

//specialized
template <>
class vector <bool>
{
    // interface

    private:
    unsigned int *vector_data;
    int length;
    int size;
}; 

Besides, the interface for this specialized interface can be totally different from the generic template: they can have different methods. In some sense (or scenarios), template specialization can implement (substitute) the functionality of virtual inheritance. The major drawback of template specialization is increased code size and resulting complexity.

Similar to template specialization, we can also have partial specialization, which means you specialize certain features but still leave some feature for users to choose. The following shows one such example.

//generic template
template <typename T, unsigned length>
class fixedVector { ... };

//partial specialization
template <unsigned length>
class fixedVector <bool, length> { ... };

As we can see here, in the partial specialization,  the vector is determined to contain the bool type, but the length can still be specified.

Two's Complement

Two's Complement is a system used to effectively represent negative integers such that we can treat the negative number as ordinary number and reuse the addition.

The problem arouses from One's Complement. For example, 2 is denoted as "00000010" and "-1" is denoted as "11111110" in One's Complement. Then naive way of doing "2 + (-1)" will get "00000000". That is incorrect. We need to further add a carry bit "1" to the sum. Then we can get "00000001", which is the right answer. However, we need to do an extra addition here.

In Two's Complement, the negative number is denoted by inverting all the bits in a positive number and adding 1. For example, "-1" is denoted as "11111111". Then we can just use the ordinary addition which save one extra addition. Besides, there is only one "0" in Two's Complement, but two in One's Complement (0 and -0).

About Smart Pointer, Copy-on-write

This link is very instructive.

Why we need virtirtual destructor?

When you release the resource of an class object, usually you leverage the object's destructor. Assume we have two class here: base Class A and derived Class B, for the following code:

class A{
  public:
    ~A(){}
};

class B: public A{
   public:
    ~B(){}
};

B *b = new B();
delete b;

First B's destructor will be called, followed by A's. On the other side, if we have the following code:

class A{
  public:
    ~A(){}
};

class B: public A{
   public:
    ~B(){}
};

A *a = new B();
delete a;

Only A's destructor will be called. In order to also call B's destructor in the second code example, the ~A() should be declared as virtual.

Something about Interrupt, Mutex and Semaphore

The details of interrupt and mutex are not that simple. Be aware of the following bullets:

1. Disable/Enable interrupt can be used to implement mutex. It is simple but flawed.
2. For multi-processors, disable interrupt may not be useful, unless you disable interrupt on all processors, which will be prohibitively expensive.
3. Atomic instruction, such as test-and-set, can be used to implement mutex. test-and-set is an atomic instruction which writes 1 to a memory location and fetch the old value of that location. For example, a spin-lock implementation is given as follow:

while (test_and_set(lock)==1);

4. Besides,  other atomic instructions such as exchange, compare&swap, load linked and conditional store can also be used.
5. For the example given in 3), we will busy wait. To minimize the waiting time, we can do the following (add a guard variable):

while (test_and_set(guard)==1);

if(lock_value == 1)
{
   put the thread in the waiting queue for the lock;
   go to sleep;
   guard = 0;
}
else
{ 
   lock_value = 1;
   guard = 0
}

6. Spin lock can sometimes delay releasing the lock. For example, thread A get switched out right after grabbing the lock. Thread B kicks in and try to grab the lock, but the lock has already been grabbed. Thread B has to be busy waiting, which will delay the switching back to thread A.
7. Semaphore represents the number of resources that are still available to simultaneous users (e.g. there are still 4 available slots)..   
8. Besides, we can also use implement some lock-free data structure in pursuit of better performance. These structures usually leverage some atomic instructions or atomic variables (the read/write to the variable is atomic, e.g. pointer type.). Some data structures are weak enough to be implemented without special atomic primitives, e.g., FIFO queue.

Things to Remember about memcpy()

If you want to implement memcpy(), you need to pay attention to the following things:

1. if you can use wider data type, use it (e.g., copy a 32 bit instead of 8 bit).
2. leverage the instruction set provided by the underlying architecture (processor). For example, some architecture has *p++, some only has *(++p).
3. memory alignment. Sometimes if you want to do 32bit copy, the instruction may require memory address to be aligned. Therefore some extra work needs to be done.
4. use pointer such as const char * for src.
5. if the src and dest memory address overlap with each other, some extra work needs to be done.

Some Tricks about Optimizing Branches

You should be cautious when using branches in your code. Sometimes the performance could be hurt.

while (++i > count)

The above code may generate complex machine code. It is much better to let the compiler to generate code that utilizes the processors compare instructions in an efficient way. This means creating loops that terminates when a compare value is zero, which is as follow:

while (count--)

The following code is also not good:

while (count-=2)

The Mystery about sizeof()

sizeof() is to get the size of a class or an class object. It might be simple conceptually, but there are some details you may not know.

• what does sizeof() return?

class A
{
  static char x;
  int y;
};

int main()
{
  int s1 = sizeof(A);
}

        s1 = 4. Why s1 = 4? The size of static members will not be counted into the size of the class. The reason is that those static members are stored centrally and shared by all the instances of the class.

• what does sizeof() return?

class A
{
  char x;
  int y;
};

int main()
{
  A a;
  int s1 = sizeof(A);
  int s2 = sizeof(a);
}

        s1 = 8 and s2 = 8. Why s1 = 8? The size it really needs is just 5 bytes. The reason is for alignment so padding is added. Why s2 = 8? sizeof(a) is equivalent to sizeof(A). Moreover, the padding scheme will sometimes make the order of data members matter. For example, if we have "char a; int x; char b;", the size will be 12. However, if we have "char a; char b; int x;", the size will be 8.

• what does sizeof() return?

class A
{
  char x;
  int y;
  virtual void bar();
};

int main()
{
  int s1 = sizeof(A);
}

        s1 = 12. Why s1 = 12? Since virtual function is defined, 4 extra bytes need to be allocated for the pointer to virtual function table.

• what does sizeof() return?

class A
{
  char x;
  int y;
  void bar();
};

int main()
{
  int s1 = sizeof(A);
}

        s1 = 8. Why s1 = 8? Since there is no virtual function defined, we don't need the 4 extra bytes for the pointer to virtual function table. For non-virtual function, there is a central place to find those functions, therefore we don't need such pointer.

• what does sizeof() return?

class A
{
  char x;
  int y;
  void bar();
};

class B{
   int a;
   A aa;
   virtual void somefunction() ;
}

int main()
{
  int s1 = sizeof(B);
}

        s1 = 16. Why s1 = 16? The size of class A is 8. class B has one integer, one class A instance plus the pointer to the virtual function table. So the total size is 8+4+4 = 16 bytes.

• what does sizeof() return?

int foo(int n)
{
  char b[n+3];
  return sizeof(b);
}

int main()
{
  int s1 = foo(8);
  
}

        s1 = 11. Why s1 = 11? In this case, at compile time, the compiler can't know the size of array b. The size is known at the run time. That is to say, sizeof() can be evaluated at run time for some case. But for the general case, it is evaluated at compile time.

• what does sizeof() return?

class ABase{ 
        int iMem; 
}; 

class BBase : public virtual ABase { 
        int iMem; 
}; 

class CBase : public virtual ABase { 
        int iMem; 
}; 

class ABCDerived : public BBase, public CBase { 
        int iMem; 
}; 

int main()
{
   int s1 = sizeof(ABase);
   int s1 = sizeof(BBase);
   int s2 = sizeof(CBase);
   int s4 = sizeof(ABCDerived);
}

        s1 = 4, s2 = 12, s3 = 12 and s4 = 24. Why ? In this case, because BBase and CBase are derived from ABase virtually, they will also have an virtual base pointer (different from the pointer to virtual function table). So, 4 bytes will be added to the size of the class (BBase and CBase). That is sizeof ABase + size of int + sizeof Virtual Base pointer.Size of ABCDerived will be 24 (not 28 = sizeof (BBase + CBase + int member)) because it will maintain only one Virtual Base pointer.

• what does sizeof() return? (edited on Aug 12)

void foo(int a[])
{
  cout << sizeof(a) << endl;
}

int main()
{  
   int a[10];
   foo(a);
   cout << sizeof(a) << endl;
}

    .    The sizeof() in foo() will return 4 while the one in main() will return 40. The reason is that the a in foo() is actually interpreted as a integer pointer.

The Ugly Thing about char [], char *, const char *, char * const and char const *

These concepts seem simple, but mistake can be made if you haven't thoroughly understood them.

• is following code correct?

foo()
{
char a[]= "I HATE U!";
a[0] = 'U';
}

        Yes,  array a[] will be allocated on stack and a[0] just modifies the first character.

• is following code correct?

foo()
{
char *a = "I HATE U!";
a[0] = 'U';
}

        Compiler won't complain, but the program will crash. The reason is "I HATE U!" is a constant that will be allocated in the constant memory region.  If we try to modify its value thru pointer a, you will be hit by seg fault.
        However,  initializing the variable  takes a huge performance and space penalty for the array (using char a[] = "XXXX"). Only use the array method if you intend on changing the string, it takes up space in the stack and adds some serious overhead every time you enter the variable's scope. Use the pointer method otherwise.

• is following code correct?

foo()
{
cont char *a = "I HATE U!";
a[0] = 'U';
}

        No, compiler will complain.  a is a pointer points to char constant, you can modify what a points to (a's value), but you can't modify the content of the address that a points to (*a's value).

• is following code correct?

foo()
{
char * const a = "I HATE U!";
a++;
}

        No, compiler will complain.  a is a constant pointer, therefore you can'y modify what a points to (a's value). But you can modify the content of the address that a points to (*a's value) if that address is valid to access. In the above example, the address is not valid to access.

• is following code correct?

foo()
{
char const *a = "I HATE U!";
a[0] = 'U';
}

        No, compiler will complain. char const *a is the same as const char * a. 

"Mutable" Key Word

mutable allows a class data member to be modified in a const function.

Example:

Class A{
   private:
      mutable int x;

   public:
      void foo(int a) const
      {
         x = a;
      }   
}

Single Precision and Double Precision Floating Number

• Single precision floating number has 1 signed bit, exponent width 8 bits, fraction 23 bits, significand 24 bits. The value is  (from Wikipedia)
• Double precision floating number has 1 signed bit, exponent width 11 bits, fraction 52 bits, significand 53 bits.The value is (from Wikipedia)