Test if a given number is power of two in one line in C

In binary representation, a number is power of two if it has only one on bit and others bits as off.
For ex: binary representation of 8 is 1000 (contains only one on bit) whereas, that of 5 is 0101(contains two on bits).

If a number is power of two, for example 8, bitwise and of 8 and 7 is 0

Code:

#include <stdio.h>

int main(){
     int n = 8;
     if((!(n & (n-1)))){  // & is bitwise and whereas ! is logical not
          printf("The number is power of two\n");
     }else{
           printf("Not a power of two\n");
     }
     return 0;
}

However, this does not give correct result for n = 0. For n = 0, the above expression would be 1, thus printing, "the number is power of two". To accommodate, the case for n = 0, use the following code.

 #include <stdio.h>

int main(){
     int n = 8;
     if((n && !(n & (n-1)))){     // && is logical and, ! is logical not and & is bitwise and
          printf("The number is power of two\n");
     }else{
           printf("Not a power of two\n");
     }
     return 0;
}

lvalue required as left operand of assignment error when using C

Consider the following array:

int arr[5] = {1,2,3,4,5};

We know that name of the array points to address of first element of array i.e. address of 1 here.

So, the following code:

printf("%u",arr);

will give address of 1 in this case. This address of 1 is constant and cannot be changed. So, in a C program, it is not possible to change the value of arr.

The following code will give an error: lvalue required as left operand

#include

int main(){
     int arr[5] = {1,2,3,4,5};  
     arr++;
     return 0;
}

Even if you give a lvalue by modifying the code as below, it will still throw a compilation error.
error: incompatible types when assigning to type 'int[5]' from type 'int *'  

int main(){
     int arr[5] = {1,2,3,4,5};  
     arr = arr +1;
     return 0;
}

Thus, important thing to understand here is, we are missing out on a key concept.
Here, arr is a constant just like a const variable which cannot be changed and any attempt to change that value will result in a compilation error.

It will be more comprehensible if the error "lvalue required as left operand" would have read "arr is a constant and cannot be changed".

Having said that, the following operation is valid.

int main(){
     int arr[5] = {1,2,3,4,5};  
     printf("%d\n", *(arr + 1));
     return 0;
}

This is because, we are fetching the value at index 1 of array arr and not increasing the value of arr.

This is similar to int y = x +5;
We are not increasing the value of x here. We are just adding 5 to value of 5 and assigning it to y.

Fetching elements in multi-dimensional array in C using pointers

As opposed to traditional method of using integer indexes, elements in a multi-dimensional array in C can be fetched using pointers.

Consider the following code using multi-dimensional array.

#include <stdio.h>

int main()
{
 
    int matrix[10][20] = {{1,2,3,4},{5,6,7,8},{9,10,11,12}};
    int i,j;
    for(i = 0; i < 3;i++){
        for(j = 0 ; j< 4 ;j++){
            printf("%d\n",(*(*(matrix +i)) + j));  
        }
    }
 
return 0;
}

Different methods are available to print individual elements from the above array. Three different approaches are described below.

1.  *(a[i] + j) :
    a[i] refers to first element in i th array of matrix. Adding j gives the address of j th element in i th array.
    De-referencing this address gives value at ith row and j th column of matrix array

2. (*(matrix + i))[j]
      *(matrix + i) gives address of first element of i th row of matrix. [j] gives j th column of row i.

3. *(*(matrix + i) + j)
     As above, *(matrix + i) gives address of first element of i th row of matrix. Adding j gives address of j th column of matrix. De-referencing this element gives the value of  i th row and j th column.

Understanding Recursion

Recursion is a method where the solution to the problem depends on solution to smaller instances of the same problem.

The most common example for recursion is factorial. Let us see this with an example.

#include <stdio.h>

int factorial(int n){
    int F;
    printf("I am calculating the factorial of %d: ",n);
    if(n==0)
        return 1;
   
    F = n*factorial(n-1);
    printf("The calculation of factorial is done for %d\n",F);
    return F;
}

int main(){
  int n,result;

  printf("Enter the number to calculate the factorial \n");
  scanf("%d",&n);

  result = factorial(n);
  printf("The factorial is %d \n",result);
}

Can you guess what will be the output of this program, how the print statements are printed ?

Let's assume the number for which the factorial is to be calculated is 5.

factorial function is called with value 5--> the first printf statement is printed-->.The recursive function is then called with the value 5.

The calculation of 5*factorial(4) is paused as it needs to calculate the factorial first ie factorial(4).

So, it goes to beginning of function and the second printf statement is then printed -->factorial is called again with value 4,

The calculation 4*factorial(3) is paused as factorial(3) needs to be calculated first.

So, it goes to beginning of function and the third printf statement is then printed -->factorial is called again with value 3,

The calculation 3*factorial(2) is paused as factorial(2) needs to be calculated first.

So, it goes to beginning of function and the fourth printf statement is then printed -->factorial is called again with value 2,

The calculation 2*factorial(1) is paused as factorial(1) needs to be calculated first.

So, it goes to beginning of function and the fifth printf statement is then printed -->factorial is called again with value 1,

The calculation 1*factorial(0) is paused as factorial(0) needs to be calculated first.

So, it goes to beginning of function and the sixth printf statement is then printed. At this point n=0 and the value 1 is returned to factorial(0).

Now the paused calculations take place as follows:

Since factorial(0) =1,
The fifth calculation:factorial(1) = 1*factorial(0) =1 and the print statement is printed with n=1
The fourth calculation:factorial(2) = 2* factorial(1)=2 and the print statement is printed with n=2
The third calculation:factorial(3) = 3*factorial(2) =6 and the print statement is printed with n=3
The second calculation:factorial(4) = 4*factorial(3) = 24 and the print statement is printed with n=4
The first calculation:factorial(5) = 5*factorial(4) =120 and the print statement is printed with n=5

Finally F =120 and the value is printed.

The final output looks like this:

Enter the number to calculate the factorial: 5
I am calculating the factorial of 5
I am calculating the factorial of 4
I am calculating the factorial of 3
I am calculating the factorial of 2
I am calculating the factorial of 1
I am calculating the factorial of 0
The calculation of factorial is done for 1
The calculation of factorial is done for 2
The calculation of factorial is done for 3
The calculation of factorial is done for 4
The calculation of factorial is done for 5
The factorial is 120

C System Calls and FILE I/O library function

System calls are special types of functions available in some programming languages. They are used by programs to communicate directly with the operating system. The OS talks back to the program through the return value of the function. When a system call is made, the control is relinquished to the operating system to perform the system call and the program is blocked until the call has finished. We should always check the return value as this is the only method the operating system communicates with the program. All these functions are included under header file unistd.h, sys/stat.h and sys/types.h. The return value is an integer. Operation takes place on file descriptor.

There are more than 100 system calls implemented as a part of C library. A few of C system calls are:

1. close : This closes the file descriptor.
    Function Definition : int close(int fildes);
2. dup : It provides and alias for the provided file descriptor.
    Function Definition : int dup(int fildes);
3. dup2:  It provides and alias for the provided file descriptor and then deletes the old file descriptor.
    Function Definition : int dup2(int fildes);
4. fstat : It is used to determine information about a file based on its file descriptor.
    Function Definition : int dup(int fildes, struct stat *buf); The second parameter stores the data             about the file.
5. lseek : change the location of the read/write pointer of a file descriptor. The location can be set           either in absolute or relative terms.
    Function Definition: off_t lseek(int fildes, off_t offset, int whence);
    whence :The method in which the offset is to be interpreted (relative, absolute, etc.).
 

Value	Meaning
SEEK_SET	Offset is to be measured in absolute terms.
SEEK_CUR	Offset is to be measured relative to the current location of the pointer.
SEEK_END	Offset is to be measured relative to the end of the file.

6. lstat :  determine information about a file based on its filename.
    Function Definition: int lstat(const char *path, struct stat *buf);
7. open : open a new file and obtain its file descriptor.
    Function Definition:
                        int open(const char *path, int oflags);
                        int open(const char *path, int oflags, mode_t mode);
8. read : read data into a buffer.
    Function Definition : size_t read(int fildes, void *buf, size_t nbytes);
9. stat :  used to determine information about a file based on its file path.
    Function Definition:  int stat(const char *path, struct stat *buf);
10. write : used to write data out of a buffer.
    Function Definition : size_t write(int fildes, const void *buf, size_t nbytes);


In contrast to these library function for system calls, there are other similar library function which are used for file I/O in C.  The operation takes place on pointers of type FILE(i.e. streams) and an integer is returned They are:

1. fopen: opens the filename pointed to, by filename using the given mode.
    Function Definition :  FILE *fopen(const char *filename, const char *mode);
2. fprintf: sends formatted output to a stream.
    Function Definition : int fprintf(FILE *stream, const char *format, ...)
3. fscanf:  reads formatted input from a stream.
    Function Definition: int fscanf(FILE *stream, const char *format, ...)
4. fputc: writes a character (an unsigned char) specified by the argument char to the specified stream     and advances the position indicator for the stream.
    Function Definition : int fputc(int char, FILE *stream)
5. fgetc: gets the next character (an unsigned char) from the specified stream and advances the               position indicator for the stream.
    Function Definition: int fgetc(FILE *stream)

Two other functions are used for I/O operations on binary files i.e. streams :

1. fread : reads data from the given stream into the array pointed to, by ptr.
    Function Definition : size_t fread(void *ptr, size_t size, size_t nmemb, FILE *stream)
2. fwrite :  writes data from the array pointed to, by ptr to the given stream.
    size_t fwrite(const void *ptr, size_t size, size_t nmemb, FILE *stream)

Dynamic Memory Allocation in C

Many programmers think that dynamic memory allocation is difficult to learn. I was one of them. However, after going through some tutorials I found it to be quite easy.

Why dynamic memory allocation ?

Allocating large data objects are compile time is not always practical if data objects are used infrequently and for a short time. So, these data objects are allocated at run time.

What is dynamic in dynamic memory allocation ?

It is called dynamic because the memory is allocated at run-time as opposed to compile time. One more important thing to note about dynamic memory allocation is that the memory is allocated in heap as opposed to stack.

How to implement dynamic memory allocation ?

C provides four different functions for dynamic memory allocation. They are:

1. malloc : The malloc() function returns a void pointer to the allocated memory or NULL if the
memory could not be allocated. You should always check the returned pointer for NULL. Please note that there is a big difference between void pointer and NULL pointer. Void pointer does not have type but it does have a valid pointer to an address. However, NULL pointer does not have any address.

Syntax :  data_type *p = (data_type *) malloc(size_t);
(data_type *) is the cast. malloc returns a void pointer. So, it is important to type cast to correct pointer type.

Eg : int *data;
        *data = (int*) malloc(sizeof(int));

•  The pointer returned by malloc() should be saved in a static variable, unless you are sure that the memory block will be freed before the pointer variable is discarded at the end of the block or the function.
•  You should always free a block of memory that has been allocated by malloc() when you are finished with it. If you rely on the operating system to free the block when your program ends, there may be insufficient memory to satisfy additional requests for memory allocation during the rest of the program’s run.
• Avoid allocating small blocks (that is, less than 25 or 50 bytes) of memory. There is always some overhead when malloc() allocates memory—16 or more bytes are allocated in addition to the requested memory.
• Avoid allocating small blocks (that is, less than 25 or 50 bytes) of memory. There is always some overhead when malloc() allocates memory—16 or more bytes are allocated in addition to the requested memory.

2. calloc : The calloc library function assigns memory but with two major differences.

     a. Calloc takes two parameters, number of elements and size of element. The product of these                 elements determine the size of the memory block to allocate.

     b. It initializes the memory it allocates to zero.

      Syntax : data_type *p = (data_type *) calloc(n,size_t);

      Eg : int *data;

              *data = (int *) calloc(n, sizeof(int);

     There is a limit to the number of bytes that can be allocated by malloc or calloc function at one             time. That is 65,510 bytes in certain compiler.

3. free : This function returns allocated memory back to the operating system.The free() function is         almost foolproof. The pointer array is initialized to NULL which is a safe value because if someone tries to free the already freed pointer, there is no error. Errors could occur, however, when you try to free memory that

• Was not allocated with one of the memory allocation functions,
• Has been released through a prior call to free() or a call to realloc(),
• Is currently in use by another thread in a multi-threaded operating system,
• Is not yours to free.

4. realloc : When we are not sure as to how much of memory is required for certain operation we can first assign a small amount of memory using calloc() or malloc() and then call realloc() to make the block larger.

Syntax : void *realloc(void *ptr, size_t size) 

The pointer ptr points to memory block previously allocated with malloc, calloc or realloc. If is is NULL a new block of memory is allocated and the pointer to that block is returned.

size is the new size for the memory block, in bytes. If it is 0 and ptr points to an existing block of memory, the memory block pointed by ptr is deallocated and a NULL pointer is returned.

memset: This library function does not allocate or deallocate memory but initializes a block of memory to any value passed as it's parameter.

Syntax :  void *memset(void *str, int c, size_t n)

Parameters

• str -- This is a pointer to the block of memory to fill.
• c -- This is the value to be set. The value is passed as an int, but the function fills the block of memory using the unsigned char conversion of this value.

• n -- This is the number of bytes to be set to the value.

Array of Structure

We can use structure to store the value of one particular object but if we want to store the value of 100 such objects we need array of structure.

For eg: If we want to store the value of details of book like author, no of pages and price. We can define such structure as follows:

struct bookinfo{

    char[20] author;

    int pages;

    float price;

};

Now to define three similar structure we can define an array of the above defined structure as follows:

struct bookinfo record[3];

Lets's see this using a C program:

 #include
  struct bookinfo{
           char author[20];
           int pages;
           float price;
   };
 
   int main(){
       int i;
      struct bookinfo record[3];
      char suffix[3][3]={"st","nd","rd"};
      for(i=0;i<3 i="" p="">      {
             printf("Enter the author of first book: ");
             scanf("%s",record[i].author);
             printf("Enter the number of pages in the book: ");
             scanf("%d",&record[i].pages);
             printf("Enter the price of the book: ");
             scanf("%f",&record[i].price);
      }
 
      for(i=0;i<3 i="" p="">      {
 
         printf("\nThe author of %d%s book is: %s \n",i+1,suffix[i],record[i].author);
         printf("The number of pages in %d%s book is: %d \n",i+1,suffix[i],record[i].pages);
         printf("The price of %d%s book is: %f \n",i+1,suffix[i],record[i].price);
      }
      return 0;
  }

OUTPUT:

Enter the author of first book: fasdf
Enter the number of pages in the book: 32
Enter the price of the book: 34
Enter the author of first book: phy
Enter the number of pages in the book: 45
Enter the price of the book: 56.5
Enter the author of first book: math
Enter the number of pages in the book: 54
Enter the price of the book: 45.7

The author of 1st book is: fasdf
The number of pages in 1st book is: 32
The price of 1st book is: 34.000000

The author of 2nd book is: phy
The number of pages in 2nd book is: 45
The price of 2nd book is: 56.500000

The author of 3rd book is: math
The number of pages in 3rd book is: 54
The price of 3rd book is: 45.700001 

Function Pointers in C

Pointers are used to point to address of some variable. Pointers can be de-referenced to get the value of the data that the pointer points to. In addition to data, pointers can also be used to store the address of a function. Not only this, it can also be de-referenced to execute the function.

Lets understand with the following example:

#include <stdio.h>

int add(int x, int y){
 return x+y;
}

int main(){

    int c;
    int (*p)(int,int);
    p = add;  // p = &add can also be used to assign the address of  add function to p.
    c=  p(2,3); // c= (*p)(2,3) can also be used to de-reference the pointer p and run the function.
    printf("%d\n",c);
}

The add function adds two integers x and y and returns the sum of two integers.

In function main, the function pointer is defined using the syntax : int (*p) (int, int).
This means that, the pointer variable p is the function pointer for a function with two integers as the input variable and an integer as the return value.

The syntax, p= add ; or p= &add; is used to store the address of add function in the pointer variable p.

The syntax, c = p(2,3) or c= *p(2,3) can be used to call the function add by de-referencing the pointer p and the return value is stored in c as c is an int variable.

Windows Programming in C

The best tutorial that I have come across till now to get started with windows programming in C is:

http://www.winprog.org/tutorial/simple_window.html

The program compiles perfectly and the output is a basic window.
Although, we do not use C to do windows programming, it's good to understand what happens behind the scene when we create windows application using frameworks like .NET.

The code is as follows:

#include <windows.h>

const char g_szClassName[] = "myWindowClass";

// Step 4: the Window Procedure
LRESULT CALLBACK WndProc(HWND hwnd, UINT msg, WPARAM wParam, LPARAM lParam)
{
    switch(msg)
    {
        case WM_CLOSE:
            DestroyWindow(hwnd);
        break;
        case WM_DESTROY:
            PostQuitMessage(0);
        break;
        default:
            return DefWindowProc(hwnd, msg, wParam, lParam);
    }
    return 0;
}

int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance,
    LPSTR lpCmdLine, int nCmdShow)
{
    WNDCLASSEX wc;
    HWND hwnd;
    MSG Msg;

    //Step 1: Registering the Window Class
    wc.cbSize        = sizeof(WNDCLASSEX);
    wc.style         = 0;
    wc.lpfnWndProc   = WndProc;
    wc.cbClsExtra    = 0;
    wc.cbWndExtra    = 0;
    wc.hInstance     = hInstance;
    wc.hIcon         = LoadIcon(NULL, IDI_APPLICATION);
    wc.hCursor       = LoadCursor(NULL, IDC_ARROW);
    wc.hbrBackground = (HBRUSH)(COLOR_WINDOW+1);
    wc.lpszMenuName  = NULL;
    wc.lpszClassName = g_szClassName;
    wc.hIconSm       = LoadIcon(NULL, IDI_APPLICATION);

    if(!RegisterClassEx(&wc))
    {
        MessageBox(NULL, "Window Registration Failed!", "Error!",
            MB_ICONEXCLAMATION | MB_OK);
        return 0;
    }

    // Step 2: Creating the Window
    hwnd = CreateWindowEx(
        WS_EX_CLIENTEDGE,
        g_szClassName,
        "The title of my window",
        WS_OVERLAPPEDWINDOW,
        CW_USEDEFAULT, CW_USEDEFAULT, 240, 120,
        NULL, NULL, hInstance, NULL);

    if(hwnd == NULL)
    {
        MessageBox(NULL, "Window Creation Failed!", "Error!",
            MB_ICONEXCLAMATION | MB_OK);
        return 0;
    }

    ShowWindow(hwnd, nCmdShow);
    UpdateWindow(hwnd);

    // Step 3: The Message Loop
    while(GetMessage(&Msg, NULL, 0, 0) > 0)
    {
        TranslateMessage(&Msg);
        DispatchMessage(&Msg);
    }
    return Msg.wParam;
}

Scanset in C

scanf family functions support scanset specifiers which are represented by %[]. Inside scanset, we can specify single character or range of characters. While processing scanset, scanf will process only those characters which are part of scanset. We can define scanset by putting characters inside squre brackets. Please note that the scansets are case-sensitive.

For Eg:

If we want to get only capital letters from stdin we can use the following:

scanf("%[A-Z]s", str);

If we want to get only small letters from stdin we can use the following:

scanf("%[a-z]s", str);

If first character of scanset is ‘^’, then the specifier will stop reading after first occurrence of that character. For example, given below scanset will read all characters but stops after first occurrence of ‘o’

scanf("%[^o]s", str);

If we want to read a line from stdin into the buffer pointed to by s until either a terminating newline or EOF found.

scanf("%[^\n]s", str);

How are integers stored in binary

In a C program, when we use the following statements:

int a = 12;

The operating system allocates 4 bytes of memory for a and stores 12 in binary format in those 4 bytes.

In binary 12 = 1100, which when expanded to store in 4 bytes will be as follows:
00000000 00000000 00000000 00001100.

Lets assume the memory address to store these 4 bytes are 1001,1002,1003,1004
The rightmost bit is called the least significant bit and the leftmost bit is the most significant bit. Each byte is stored in a different memory address. If we store the bytes with the least significant byte in the lowest memory address ie store 00001100 in 1001, this method of storing in memory is called little endian. On the other hand, if we store the most significant byte in the lowest memory address ie store 00000000 in 1001, it is called big endian.

Integers can be positive or negative. One way to store negative numbers in binary is to set the most significant bit to 1 to denote that it is a negative number. So -12 is stored as follows:

10000000 00000000 00000000 00001100.
So, we have only 31 bits for the numbers. Thus the largest integer that can be stored is 2^31-1= 65535 and the lowest integer that can be stored is -2^31-1= -65535

However, there are two major problems when we store integers like this.

1. Lets suppose we want to store values from -3 to +3. There are 7 numbers in this range.

0 - 000
1 - 001
2 - 010
3 - 011
-0 - 100
-1 - 101
-2 - 110
-3 - 111

Here we can see that 0 has two representations which can create a big confusion.

2. Arithmetic operations do not give the correct results.

If we add +1 and -1, it should output 0. Here,

 001 + 101 = 110 which is -2 and that is wrong.

So, to avoid these we use 2's complement to store negative numbers. In 2's complement, to get the binary representation for a negative number, its positive conterpart is first complemented and 1 is added to the 1's complement.

The 2's complement of 1(001) is 111(110+1).

The above range can now be represented as follows:


0 - 000
1 - 001
2 - 010
3 - 011
-1 - 111
-2 - 110
-3 - 101
-4 - 100

Thus, we can see that both of the above problems are solved using the 2's complement. Also, we can store one more number as there is only 1 representation for 0. The range of number which can be represented using this method is -2^31 to 2^31-1.