Blog Posts

Exercise 3.1 Our binary search makes two tests inside the loop, when one would suffice (at the price of more tests outside). Write a version with only one test inside the loop and measure the difference in run-time.

Original for loop code:

/* binsearch: find x in v[0] <= v[1] <= ... <= v[n-1] */
int binsearch(int x, int v[], int n)
{
    int low, high, mid;
    low = 0;
    high = n - 1;
    while (low <= high) {
        mid = (low + high) / 2;
        if (x < v[mid])
            high = mid + 1;
        else if (x > v[mid])
            low = mid + 1;
        else /* found match */
            return mid;
    }
    return -1; /* no match */
}

Modified code:

#include<stdio.h>

int binsearch(int x, int v[], int n);

main() {
    int arr[] = { 1,3,5,7,8,10,22,24,26,28,41,43,45,47,50,51 };
    printf("%d", binsearch(7,arr,10));
}

int binsearch(int x, int v[], int n) {
    int low, high, mid;

    low = 0;
    high = n - 1;

    mid = (low + high) / 2;

    while (low < high && x != v[mid]) {
        if (x > v[mid]){
            low = mid + 1;
        } else {
            high = mid - 1;
        }
        mid = (low + high) / 2;
    }
    if (x == v[mid]){
        return mid;
    } else {
        return -1;
    }
}

Exercise 3.2 Write a function escape(s,t) that converts characters like newline and tab into visible escape sequences like \n and \t as it copies the string t to s . Use a switch . Write a function for the other direction as well, converting escape sequences into the real characters.

Exercise 2-1. Write a program to determine the ranges of char , short , int , and long variables, both signed and unsigned , by printing appropriate values from standard headers and by direct computation. Harder if you compute them: determine the ranges of the various floating-point types.

#include<stdio.h>
#include<limits.h>

/* determine ranges of types */
main() {
    /* signed types */
    printf("signed char min = %d\n", SCHAR_MIN);
    printf("signed char max = %d\n", SCHAR_MAX);
    printf("signed short min = %d\n", SHRT_MIN);
    printf("signed short max = %d\n", SHRT_MAX);
    printf("signed int min = %d\n", INT_MIN);
    printf("signed int max = %d\n", INT_MAX);
    printf("signed long min = %d\n", LONG_MIN);
    printf("signed long max = %d\n", LONG_MIN);

    /* unsigned types */
    printf("unsigned char max = %u\n", UCHAR_MAX);
    printf("unsigned short max = %u\n", USHRT_MAX);
    printf("unsigned int max = %u\n", UINT_MAX);
    printf("unsigned long max = %lu\n", ULONG_MAX);
}

Output Result:

signed char min = -128
signed char max = 127
signed short min = -32768
signed short max = 32767
signed int min = -2147483648
signed int max = 2147483647
signed long min = -2147483648
signed long max = -2147483648
unsigned char max = 255
unsigned short max = 65535
unsigned int max = 4294967295
unsigned long max = 4294967295

#include<stdio.h>

/* determine ranges of types */
main() {
    /* signed types */
    printf("signed char min = %d\n",
                    -(char)((unsigned char)~0 >> 1));
    printf("signed char max = %d\n",
                    (char)((unsigned char)~0 >> 1));
    printf("signed short min = %d\n",
                    -(short)((unsigned short)~0 >> 1));
    printf("signed short max = %d\n",
                    (short)((unsigned short)~0 >> 1));
    printf("signed int min = %d\n",
                    -(int)((unsigned int)~0 >> 1));
    printf("signed int max = %d\n",
                    (int)((unsigned int)~0 >> 1));
    printf("signed long min = %d\n",
                    -(long)((unsigned long)~0 >> 1));
    printf("signed long max =  %d\n",
                    (long)((unsigned long)~0 >> 1));

    /* unsigned types */
    printf("unsigned char max = %u\n", 
                    (unsigned char)~0);
    printf("unsigned short max = %u\n",
                    (unsigned short)~0);
    printf("unsigned int max = %u\n",
                    (unsigned int)~0);
    printf("unsigned long max = %u\n",
                    (unsigned long)~0);
}

Output Result:

signed char min = -127
signed char max = 127
signed short min = -32767
signed short max = 32767
signed int min = -2147483647
signed int max = 2147483647
signed long min = -2147483647
signed long max =  2147483647
unsigned char max = 255
unsigned short max = 65535
unsigned int max = 4294967295
unsigned long max = 4294967295

Exercise 2-2. Write a loop equivalent to the for loop above without using && or ||.

Original for loop code:

for(i=0; i<lim-1 && (c=getchar()) != '\n' && c != EOF; ++i)
  s[i] = c;

Modified code:

#include<stdio.h>

/*
  for(i=0; i<lim-1 && (c=getchar()) != '\n' && c != EOF; ++i)
    s[i] = c;
*/

enum loop {NO, YES};
enum loop okloop = YES;
#define MAXLINE 80

main(){
    int c, i = 0, s[MAXLINE];
    int lim = MAXLINE;
    while (okloop == YES){
        if (i >= lim-1){
            okloop = NO;
        } else if ((c = getchar()) != '\n'){
            okloop = NO;
        } else if (c != EOF){
            okloop = NO;
        } else {
            s[i] = c;
            ++i;
        }
    }
}

Exercise 2-3. Write the function htoi(s) , which converts a string of hexadecimal digits (including an optional 0x or 0X) into its equivalent integer value. The allowable digits are 0 through 9, a through f, and A through F .

#include<stdio.h>

#define MAXLINE 100
#define YES 1
#define NO  0

int getline(char line[], int maxline);
int htoi(char s[]);

main(){
    int value;
    char line[MAXLINE];
    getline(line, MAXLINE);
    value = htoi(line);

    printf("The value of %s is %d \n", line, value);
}

int getline(char s[], int lim){
    int c, i;
    for (i = 0; i < lim-1 && ((c = getchar()) != EOF) && c != '\n'; ++i){
        s[i] = c;
    }
    if (c == '\n'){
        s[i] = c;
        ++i;
    }
    s[i] = '\0';
    return i;
}

/* htoi: convert hexadecimal string's to integer*/
int htoi(char s[]){
    int hexdigit, i, inhex, n;

    i = 0;
    if (s[i] == '0'){       /* skip optionel 0x or 0X*/
        ++i;
        if (s[i] == 'x' || s[i] == 'X'){
            ++i;
        }
    }
    n = 0;                  /* integer value to be returned    */
    inhex = YES;            /* assume valid hexedecimal digit  */
    for ( ; inhex == YES; ++i){
        if (s[i] >= '0' && s[i] <= '9'){
            hexdigit = s[i] - '0';
        } else if (s[i] >= 'a' && s[i] <= 'f'){
            hexdigit = s[i] - 'a' + 10;
        } else if (s[i] >= 'A' && s[i] <= 'F'){
            hexdigit = s[i] - 'A' + 10;
        } else {
            inhex = NO;     /* not a valid hexadecimal digit    */
        }
        if (inhex == YES){
            n = 16 * n + hexdigit;
        }
    }
    return n;
}

For example to convert 0XAF.

1. We strip off 0X.
2. For A, we get the value hexdigit = 10
3. n = 16 * 0 + 10 = 10
4. We gather F, we store hexdigit = ‘F’ – ‘A’ + 10;= 70 – 65 + 10; (70 is ascii value for F, 65 is ascii value for A) = 15
5. n = 16 n + hexdigit = 16 10 + 15 = 160 + 15 = 175

Exercise 2-4. Write an alternate version of squeeze(s1,s2) that deletes each character in the string s1 that matches any character in the string s2 .

#include<stdio.h>
#define MAXLINE 1000

int mgetline(char line[], int maxline);
void squeeze(char s1[], char s2[]);

main(){
    char s1[MAXLINE], s2[MAXLINE];
    putchar('s');
    putchar('1');
    mgetline(s1, MAXLINE);

    putchar('s');
    putchar('2');
    mgetline(s2, MAXLINE);

    squeeze(s1, s2);

    printf("%s",s1);

    return 0;

}

int mgetline(char s[], int lim){
    int i, c;

    for (i = 0; 1 < lim-1 && (c = getchar()) != EOF && c != '\n'; ++i){
        s[i] = c;
    }
    if (c == '\n'){
        s[i++] = c;
    }
    s[i] = '\0';
}

void squeeze(char s1[],char s2[]){
    int i, j, k;
    k = 0;

    for (i = 0; s1[i] != '\0'; ++i){
        for (j = 0; (s1[i] != s2[j]) && s2[j] != '\0'; ++j)
            ;
        if (s2[j] == '\0'){
            s1[k++] = s1[i];
        }
    }
    s1[k] = '\0';
}

Explanation:

Let’s take the two inputs strings as:

s1: Hello,World

s2: ol

Our desired output is:

He,Wrd

This has removed the characters o and l from the first string. The way squeeze works is, it take each character from the first string and if there is no match found, stores it with a new index k. If there is a match found in s2, it simply skips it. The way it skips is realized by the following:

for(j=0; (s1[i]!=s2[j]) && s2[j]!='\0' ;++j)
    ;
if(s2[j]=='\0')
    s1[k++] = s1[i];

When the match is found s1[i] == s2[j] so our first for loop will end. The second if condtion will fail too as s2 is not iterated till the end, so we do not place the character in s1[k++] and we have successfully skipped it.

Exercise 2-5: Write the function any(s1,s2) , which returns the first location in the string s1 where any character from the string s2 occurs, or -1 if s1 contains no characters from s2 . (The standard library function strpbrk does the same job but returns a pointer to the location.)

#include<stdio.h>
#define MAXLINE 1000

int getline(char line[], int maxline);
int any(char s1[], char s2[]);

main(){
    char s1[MAXLINE], s2[MAXLINE];
    int val;

    getline(s1, MAXLINE);

    getline(s2, MAXLINE);

    val = any(s1, s2);
    printf("%d", val);
    return 0;
}

int getline(char s[], int lim){
    int i, c;
    for (i = 0; i < lim-1 && (c = getchar()) != EOF && c != '\n'; ++i){
        s[i] = c;
    }
    if (c == '\n'){
        s[i++] = c;
    }
    s[i] = '\0';
}

int any(char s1[], char s2[]){
    int i, j;
    for (i = 0; s1[i] != '\0'; ++i){
        // iterate through s2 while trying to find matching character from s1
        for (j = 0; (s1[i] != s2[j]) && s2[j] != '\0'; ++j)
            ;   //continue
        if (s2[j] != '\0' && s2[j] != '\n'){
            return i;
        }

    }
    return -1;
}