Wht is 2s compliment?

       Binary numbers do not have signs. So 2's complement is used to represent a negative nos. 2's complement is found in following way :

2's complement = (do 1's complement(it is to reverse the bits in a binary) +  1)
Step I)
If we have a binary no 00001100(decimal 12) then we have
to invert it by replacing all the 1s by 0 and 0s by 1.
So we get 00001100 ---> 11110011

Step II)
Now we have to add 1 to the no which we found in (I)
So we get ,
11110011 + 00000001 = 11110100


So the no 11110100 represents -12 .
As the MSB i.e. the first bit is 1 , it indicates that the no. represents a -ve no.
In binary subtraction instead of subtracting, 2's complement of a number is added.

why 2's complement is better than sign magnitude

   Because sign magnitude has 2 representations for 0 100000000000000000000 ( = -0) and 000000000000000000000 ( = +0) Clearly, -0 = +0. However, because of these two representations, different machines process sign magnitude differently at 0. Two's complement avoids this problem and is therefore used much more commonly.

Daemon creation example

* Rules:                                              *

* 1. Call 'fork' and have parent 'exit'                           *

* 2. Call 'setsid' to create a new session                        *

* 3. Change cwd to /   -> Else if a daemon is from a mounted            *

*    (or somewhere...)    filesystem, then that cannot be unmounted     *

* 4. Set file-mode-creation mask to 0, close unneeded file descriptors  * ************************************************************************/

 

#include <sys/types.h>

#include <sys/stat.h>

#include <fcntl.h>

#include <stdlib.h>

 

static int global;

 

int main(void)

{

      pid_t pid;

     

      if ( (pid = fork()) < 0 )

         return -1;

      else if ( pid != 0 )

            exit(0);

      setsid();   /* this makes it a session leader */

      chdir("/"); /* so that other file systems can be unmounted */

      umask(0);   /* The file mode creation mask could have been inherited

                     with restrictive permissions. E.g, if the daemon

                     expects files that it creates to have group-read

                     groud-write bits enabled, and a file mode creation

                     mask has turned them off, then it would be a

                     problem */

      close(0);

      close(1);

      close(2);

 

      while(1) {

            ++global;

 

        };  /* Just to show some processing.... */

      return 0;

}

algorithm for finding a string within a string?

The general problem is string searching; there are many algorithms and approaches depending on the nature of the application.

• Knuth-Morris-Pratt, searches for a string within another string
• Boyer-Moore, another string within string search
• Aho-Corasick; searches for words from a reference dictionary in a given arbitrary text

Some advanced index data structures are also used in other applications. Suffix trees are used a lot in bioinformatics; here you have one long reference text, and then you have many arbitrary strings that you want to find all occurrences for. Once the index (i.e. the tree) is built, finding patterns can be done quite efficiently.

For an interview answer, I think it's better to show breadth as well. Knowing about all these different algorithms and what specific purposes they serve best is probably better than knowing just one algorithm by heart.

is main() function required for C program?

No, the ISO C standard states that a main function is only required for a hosted environment (one with an underlying OS).

For a freestanding environment like an embedded system (or an operating system itself), it's implementation defined. From C99 5.1.2:

Two execution environments are defined: freestanding and hosted. In both cases, program startup occurs when a designated C function is called by the execution environment.

In a freestanding environment (in which C program execution may take place without any benefit of an operating system), the name and type of the function called at program startup are implementation-defined.

As to how Linux itself starts, the start point for the Linux kernel is start_kernel though, for a more complete picture of the entire boot process, you should start here.

and

The operating systems loader has to call a single entry point; in the GNU compiler, the entry point is defined in the crt0.o linked object file, the source for this is the assembler file crt0.s - that invokes main() after performing various run-time start-up tasks (such as establishing a stack, static initialisation). So when building an executable that links the default crt0.o, you must have a main(), otherwise you will get a linker error since in crt0.o main() is an unresolved symbol.

It would be possible (if somewhat perverse and unnecessary) to modify crt0.s to call a different entry point. Just make sure that you make such an object file specific to your project rather than modifying the default version, or you will break every build on that machine.

The OS itself has its own C runtime start-up (which will be called from the bootloader) so can call any entry point it wishes. I have not looked at the Linux source, but imagine that it has its own crt0.s that will call whatever the C code entry point is

Is recursion faster than loop or what is tail recursion?

In any realistic system, no, creating a stack frame will always be more expensive than an INC and a JMP. That's why really good compilers automatically transform tail recursion into a call to the same frame, i.e. without the overhead, so you get the more readable source version and the more efficient compiled version. A really, really good compiler should even be able to transform normal recursion into tail recursion where that is possible.

This depends on the language being used. You wrote 'language-agnostic', so I'll give some examples.

In Java, C, and Python, recursion is fairly expensive compared to iteration (in general) because it requires the allocation of a new stack frame. In some C compilers, one can use a compiler flag to eliminate this overhead, which transforms certain types of recursion (actually, certain types of tail calls) into jumps instead of function calls.

In functional programming language implementations, sometimes, iteration can be very expensive and recursion can be very cheap. In many, recursion is transformed into a simple jump, but changing the loop variable (which is mutable) sometimes requires some relatively heavy operations, especially on implementations which support multiple threads of execution. Mutation is expensive in some of these environments because of the interaction between the mutator and the garbage collector, if both might be running at the same time.

I know that in some Scheme implementations, recursion will generally be faster than looping.

In short, the answer depends on the code and the implementation. Use whatever style you prefer. If you're using a functional language, recursion might be faster. If you're using an imperative language, iteration is probably faster. In some environments, both methods will result in the same assembly being generated (put that in your pipe and smoke it).

Addendum: In some environments, the best alternative is neither recursion nor iteration but instead higher order functions. These include "map", "filter", and "reduce" (which is also called "fold"). Not only are these the preferred style, not only are they often cleaner, but in some environments these functions are the first (or only) to get a boost from automatic parallelization — so they can be significantly faster than either iteration or recursion. Data Parallel Haskell is an example of such an environment.

List comprehensions are another alternative, but these are usually just syntactic sugar for iteration, recursion, or higher order functions

where do constant variables stored in C

How they are stored is an implementation detail (depends on the compiler).

For example, in the GCC compiler, on most machines, read-only variables, constants, and jump tables are placed in the text section.

Consider the code:

const int i = 0;
 static const int k = 99;
 
int function(void)
{
     const int j = 37;
     totherfunc(&j);
    totherfunc(&i);
   //totherfunc(&k);
    return(j+3);
 }

Generally, i can be stored in the text segment (it's a read-only variable with a fixed value). If it is not in the text segment, it will be stored beside the global variables. Given that it is initialized to zero, it might be in the 'bss'(block starting symbols) section (where zeroed variables are usually allocated) or in the 'data' section (where initialized variables are usually allocated).

If the compiler is convinced the k is unused (which it could be since it is local to a single file), it might not appear in the object code at all. If the call to totherfunc() that references k was not commented out, then k would have to be allocated an address somewhere - it would likely be in the same segment as i.

The constant (if it is a constant, is it still a variable?) j will most probably appear on the stack of a conventional C implementation. (If you were asking in the comp.std.c news group, someone would mention that the standard doesn't say that automatic variables appear on the stack; fortunately, SO isn't comp.std.c!)

Note that I forced the variables to appear because I passed them by reference - presumably to a function expecting a pointer to a constant integer. If the addresses were never taken, then j and k could be optimized out of the code altogether. To remove i, the compiler would have to know all the source code for the entire program - it is accessible in other translation units (source files), and so cannot as readily be removed. Doubly not if the program indulges in dynamic loading of shared libraries - one of those libraries might rely on that global variable.

(Stylistically - the variables i and j should have longer, more meaningful names; this is only an example!)

Using extern in c and machine endianness

declaration and definition of a variable/function

Declaration of a variable/function simply declares that the variable/function exists somewhere in the program but the memory is not allocated for them. But the declaration of a variable/function serves an important role. And that is the type of the variable/function. Therefore, when a variable is declared, the program knows the data type of that variable. In case of function declaration, the program knows what are the arguments to that functions, their data types, the order of arguments and the return type of the function. So that's all about declaration. Coming to the definition, when we define a variable/function, apart from the role of declaration, it also allocates memory for that variable/function. Therefore, we can think of definition as a super set of declaration. (or declaration as a subset of definition). From this explanation, it should be obvious that a variable/function can be declared any number of times but it can be defined only once. (Remember the basic principle that you can't have two locations of the same variable/function). So that's all about declaration and definition.

Understanding "extern" keyword in C

it's mandatory to understand declaration/defination to understand the "extern" keyword. Let us first take the easy case. Use of extern with C functions. By default, the declaration and definition of a C function have "extern" prepended with them. It means even though we don't use extern with the declaration/definition of C functions, it is present there. For example, when we write.

int foo(int arg1, char arg2);

There's an extern present in the beginning which is hidden and the compiler treats it as below.

extern int foo(int arg1, char arg2);

Same is the case with the definition of a C function (Definition of a C function means writing the body of the function). Therefore whenever we define a C function, an extern is present there in the beginning of the function definition. Since the declaration can be done any number of times and definition can be done only once, we can notice that declaration of a function can be added in several C/H files or in a single C/H file several times. But we notice the actual definition of the function only once (i.e. in one file only). And as the extern extends the visibility to the whole program, the functions can be used (called) anywhere in any of the files of the whole program provided the declaration of the function is known. (By knowing the declaration of the function, C compiler knows that the definition of the function exists and it goes ahead to compile the program). So that's all about extern with C functions.

Now let us the take the second and final case i.e. use of extern with C variables. I feel that it more interesting and information than the previous case where extern is present by default with C functions. So let me ask the question, how would you declare a C variable without defining it? Many of you would see it trivial but it's important question to understand extern with C variables. The answer goes as follows.

extern int var;

Here, an integer type variable called var has been declared (remember no definition i.e. no memory allocation for var so far). And we can do this declaration as many times as needed. (remember that declaration can be done any number of times) So far so good.

Now how would you define a variable. Now I agree that it is the most trivial question in programming and the answer is as follows.

int var;

Here, an integer type variable called var has been declared as well as defined. (remember that definition is the super set of declaration). Here the memory for var is also allocated. Now here comes the surprise, when we declared/defined a C function, we saw that an extern was present by default. While defining a function, we can prepend it with extern without any issues. But it is not the case with C variables. If we put the presence of extern in variable as default then the memory for them will not be allocated ever, they will be declared only. Therefore, we put extern explicitly for C variables when we want to declare them without defining them. Also, as the extern extends the visibility to the whole program, by externing a variable we can use the variables anywhere in the program provided we know the declaration of them and the variable is defined somewhere.

Now let us try to understand extern with examples.

Example 1:
int var;
int main(void)
{
var = 10;
return 0;
}

Analysis: This program is compiled successfully. Here var is defined (and declared implicitly) globally.

Example 2:
extern int var;
int main(void)
{
return 0;
}

Analysis: This program is compiled successfully. Here var is declared only. Notice var is never used so no problems.

Example 3:
extern int var;
int main(void)
{
var = 10;
return 0;
}

Analysis: This program throws error in compilation. Because var is declared but not defined anywhere. Essentially, the var isn't allocated any memory. And the program is trying to change the value to 10 of a variable that doesn't exist at all.

Example 4:
#include "somefile.h"
extern int var;
int main(void)
{
var = 10;
return 0;
}

Analysis: Supposing that somefile.h has the definition of var. This program will be compiled successfully.

Example 5:
extern int var = 0;
int main(void)
{
var = 10;
return 0;
}

Analysis: Guess this program will work? Well, here comes another surprise from C standards. They say that..if a variable is only declared and an initializer is also provided with that declaration, then the memory for that variable will be allocated i.e. that variable will be considered as defined. Therefore, as per the C standard, this program will compile successfully and work.

So that was a preliminary look at "extern" keyword in C.

I'm sure that you want to have some take away from the reading of this post. And I would not disappoint you.
In short, we can say

1. Declaration can be done any number of times but definition only once.
2. "extern" keyword is used to extend the visibility of variables/functions().
3. Since functions are visible through out the program by default. The use of extern is not needed in function declaration/definition. Its use is redundant.
4. When extern is used with a variable, it's only declared not defined.
5. As an exception, when an extern variable is declared with initialization, it is taken as definition of the variable as well.

Mystery of Bigendian and Littleendian

What are these?

Little and big endian are two ways of storing multibyte data-types ( int, float, etc). In little endian machines, last byte of binary representation of the multibyte data-type is stored first. On the other hand, in big endian machines, first byte of binary representation of the multibyte data-type is stored last.

Suppose integer is stored as 4 bytes (For those who are using DOS based compilers such as C++ 3.0 , integer is 2 bytes) then a variable x with value 0×01234567 will be stored as following.

How to see memory representation of multibyte data types on your machine?

Here is a sample C code that shows the byte representation of int, float and pointer.
#include

/* function to show bytes in memory, from location start to start+n*/
void show_mem_rep(char *start, int n)
{
int i;
for (i = 0; i < n; i++)
printf(" %.2x", start[i]);
printf("\n");
}

/*Main function to call above function for 0×01234567*/
int main()
{
int i = 0×01234567;
show_mem_rep((char *)&i, sizeof(i));
getchar();
return 0;
}

When above program is run on little endian machine, gives "67 45 23 01″ as output , while if it is run on endian machine, gives "01 23 45 67″ as output.

Is there a quick way to determine endianness of your machine?

There are n no. of ways for determining endianness of your machine. Here is one quick way of doing the same.
#include
int main()
{
unsigned int i = 1;
char *c = (char*)&i;
if (*c)
printf("Little endian");
else
printf("Big endian");
getchar();
return 0;
}

In the above program, a character pointer c is pointing to an integer i. Since size of character is 1 byte when the character pointer is de-referenced it will contain only first byte of integer. If machine is little endian then *c will be 1 (because last byte is stored first) and if machine is big endian then *c will be 0.

Does endianness matter for programmers?

Most of the times compiler takes care of endianness, however, endianness becomes an issue in following cases.

It matters in network programming: Suppose you write integers to file on a little endian machine and you transfer this file to a big endian machine. Unless there is little andian to big endian transformation, big endian machine will read the file in reverse order. You can find such a practical example here.

Standard byte order for networks is big endian, also known as network byte order. Before transferring data on network, data is first converted to network byte order (big endian).

Sometimes it matters when you are using type casting, below program is an example.
#include
int main()
{
unsigned char arr[2] = {0×01, 0×00};
unsigned short int x = *(unsigned short int *) arr;
printf("%d", x);
getchar();
return 0;
}

In the above program, a char array is typecasted to an unsigned short integer type. When I run above program on little endian machine, I get 1 as output, while if I run it on a big endian machine I get 512. To make programs endianness independent, above programming style should be avoided.

What are bi-endians?

Bi-endian processors can run in both modes little and big endian.

What are the examples of little, big endian and bi-endian machines ?
Intel based processors are little endians. ARM processors were little endians. Current generation ARM processors are bi-endian.

Motorola 68K processors are big endians. PowerPC (by Motorola) and SPARK (by Sun) processors were big endian. Current version of these processors are bi-endians.

Does endianness effects file formats?

File formats which have 1 byte as a basic unit are independent of endianness e..g., ASCII files . Other file formats use some fixed endianness forrmat e.g, JPEG files are stored in big endian format.

Which one is better — little endian or big endian

The term little and big endian came from Gulliver's Travels by Jonathan Swift. Two groups could not agree by which end a egg should be opened -a-the little or the big. Just like the egg issue, there is no technological reason to choose one byte ordering convention over the other, hence the arguments degenerate into bickering about sociopolitical issues. As long as one of the conventions is selected and adhered to consistently, the choice is arbitrary.

Some of the puzzling things about c language

Can you guess why there is no distinct format specifier for 'double' in the printf/scanf format string, although it is one of the four basic data types? (Remember we use %lf for printing the double value in printf/scanf; %d is for integers).

Ans: In older versions of C, there was no 'double'—it was just 'long float' type—and that is the reason why it has the format specifier '%lf' ('%d' was already in use to indicate signed decimal values). Later, double type was added to indicate that the floating point type might be of 'double precision' (IEEE format, 64-bit value). So a format specifier for long float and double was kept the same.

Why is the output file of the C compiler called a.out?

Ans: The a.out stands for 'assembler.output' file [2]. The original UNIX was written using an assembler for the PDP-7 machine. The output of the assembler was a fixed file name, which was a.out to indicate that it was the output file from the assembler. No assembly needs to be done in modern compilers; instead, linking and loading of object files is done. However, this tradition continues and the output of cc is by default a.out!

what is the use of volatile keyword in c?

The meaning of volatile is a popular interview question, particularly for freshers and I've read articles describing the properties of this keyword as if it had super powers.

The volatile keyword does a very simple job. When a variable is marked as volatile, the programmer is instructing the compiler not to cache this variable in a register but instead to read the value of the variable from memory each and every time the variable is used. That's it – simple isn't it?

To illustrate the use of the keyword, consider the following example:

volatile int* vp = SOME_REGISTER_ADDRESS;
for(int i=0; i<100; i++)
foo(*vp);
In this simple example, the pointer vp points to a volatile int. The value of this int is read from memory for each loop iteration. If volatile was not specified then it is likely that the compiler would generate optimized code which would read the value of the int once, temporarily store this in a register and then use the register copy during each iteration.

hope after reading this you reply confidently, when the same question is asked to you in the interview

Integer overflow and why it occurs?

What is integer overflow and why it occurs?

An integer overflow, or integer wrapping, is a potential problem in a program based upon the fact that the value that can be held in a numeric data type is limited by the data type's size in bytes. ANSI C uses the following minimum sizes:

data type size (bytes)
char 1
short 2
int 2
long 4

In practice, many compilers use a 4-byte int. It also should be noted that the actual ranges for the data types depend on whether or not they are signed. for instance, a signed 2-byte short may be between -32767 and 32767, while an unsigned short may be between 0 and 65535. See your [include]/limits.h file for specific numbers for your compiler.

Why should you care?

If you try to put a value into a data type that is too small to hold it, the high-order bits are dropped, and only the low-order bits are stored. Another way of saying that is that modulo-arithmetic is performed on the value before storing it to make sure it fits within the data type. Taking our unsigned short example:

Limit: 65535 or 1111 1111 1111 1111
Too big: 65536 or 1 0000 0000 0000 0000
What's stored: 0 or 0000 0000 0000 0000

As the above makes evident, that result is because the high-order (or left-most) bit of the value that's too big is dropped. Or you could say that what's stored is the result of
Stored = value % (limit + 1) or 65536 % (65535 + 1) = 0
In signed data types, the result is a little different and results in some seemingly weird behavior:

Positive limit: 32767 or 0111 1111 1111 1111
Too big: 32768 or 1000 0000 0000 0000
What's stored: -32768

Why's that?

It's because of "2′s compliment," which is how negative numbers are represented in binary. To make a long story short, the first half of the range (0 thru 0111 1111 1111 1111) is used for positive numbers in order of least to greatest. The second half of the range is then used for negative numbers in order of least to greatest. So, the negative range for a signed 2-byte short is -32768 thru -1, in that order.

When it occurs?

Integer overflow happens because computers use fixed width to represent integers. So which are the operations that result in overflow? Bitwise and logical operations cannot overflow, while cast and arithmetic operations can. For example, ++ and += operators can overflow, whereas && or & operators (or even <> operators) cannot.

Regarding arithmetic operators, it is obvious that operations like addition, subtraction and multiplication can overflow. How about operations like (unary) negation, division and mod (remainder)? For unary negation, -MIN_INT is equal to MIN_INT (and not MAX_INT), so it overflows. Following the same logic, division overflows for the expression (MIN_INT / -1). How about a mod operation? It does not overflow. The only possible overflow case (MIN_INT % -1) is equal to 0 (verify this yourself—the formula for % operator is a % b = a – ((a / b) * b)).

What happens when it occur?

Suppose memory is being allocated based on an unsigned integer data type's value. If that value has wrapped around, it may be that far too little memory will be made available. Or if a comparison is being made between a signed integer value and some other number, assuming that the former should be less than the latter, if that value has over flown into the negative, the comparison would pass. But are things going to behave the way the programmer intended? Probably not.

Sorting and searching techniques are most important for the programmer and we will use it in most of the programs we write. Among them the most widely used are binary search and quick sort for efficiency. In these algorithms we use mean of two elements. If the elements are integers then the mean is prone to be integer overflow condition. This results in undesirable results or bugs. So, let's look at some techniques to detect an overflow before it occurs.

For the statement int k = (i + j);
• If i and j are of different signs, it cannot overflow.
• If i and j are of same signs (- or +), it can overflow.
• If i and j are positive integers, then their sign bit is zero. If k is negative, it means its sign bit is 1—it indicates the value of (i + j) is too large to represent in k, so it overflows.
• If i and j are negative integers, then their sign bit is one. If k is positive, it means its sign bit is 0—it indicates that the value of (i + j) is too small to represent in k, so it overflows.

How to check for the overflow?

To check for overflow, we have to provide checks for conditions 3 and 4. Here is the straightforward conversion of these two statements into code. The function isSafeToAdd(), returns true or false, after checking for overflow.

/* Is it safe to add i and j without overflow? Return value 1 indicates there is no overflow; else it is overflow and not safe to add i and j */
int isSafeToAdd(int i, int j)
{
if( (i < 0 && j =0) || (i > 0 && j > 0) && k INT_MAX) or if ((i + j) INT_MAX) || ((i + j) INT_MAX), we can check the condition (i > INT_MAX – j) by moving j to the RHS of the expression. So, the condition in isSafeToAdd can be rewritten as:

if( (i > INT_MAX – j) || (i < INT_MIN – j) )
return 0;

That works! But can we simplify it further? From condition 2, we know that for an overflow to occur, the signs of i and j should be the same. If you notice the conditions in 3 and 4, the sign bit of the result (k) is different from (i and j). Does this strike you as the check that the ^ operator can be used? How about this check:

int k = (i + j);
if( ((i ^ k) & (j ^ k)) < 0)
return 0;

Let us check it. Assume that i and j are positive values and when it overflows, the result k will be negative. Now the condition (i ^ k) will be a negative value—the sign bit of i is 0 and the sign bit of k is 1; so ^ of the sign bit will be 1 and hence the value of the expression (i ^ k) is negative. So is the case for (j ^ k) and when the & of two values is negative; hence, the condition check with < 0 becomes true when there is overflow. When i and j are negative and k is positive, the condition again is < 0 (following the same logic described above).

So, yes, this also works! Though the if condition is not very easy to understand, it is correct and is also an efficient solution!