Chapter 3¶
Exercise 3-1¶
main.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ARRAYLEN 1000000
#define SAMPLESIZE 10000
int binsearch(int x, const int v[], int n);
int binsearch1test(int x, const int v[], int n);
int main()
{
clock_t tic, toc;
int i;
int v[ARRAYLEN]; /* array to search */
for (i=0 ; i<ARRAYLEN; ++i){
v[i] = i;
}
int t[SAMPLESIZE]; /* random numbers to look for */
for (i=0 ; i<SAMPLESIZE; ++i){
v[i] = rand() % (ARRAYLEN + 1);
}
tic = clock();
for (i = 0 ; i < SAMPLESIZE ; ++i){
binsearch(t[i], v, ARRAYLEN);
}
toc = clock();
printf("binsearch: %6ld clock ticks \n", toc - tic);
tic = clock();
for (i = 0 ; i < SAMPLESIZE ; ++i){
binsearch1test(t[i], v, ARRAYLEN);
}
toc = clock();
printf("binsearch1test: %6ld clock ticks \n", toc - tic);
return 0;
}
int binsearch(int x, const 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{
return mid;
}
}
return -1;
}
int binsearch1test(int x, const int v[], int n)
{
int low, high, mid=0;
low = 0;
high = n - 1;
while (high - low > 1) {
mid = (low + high) / 2;
if (x < v[mid]){
high = mid - 1;
}else{
low = mid;
}
}
if (v[low] == x){
return low;
}else if (v[mid] == x){
return mid;
}else if (v[high] == x){
return high;
}
return -1;
}
Compilation and run:
$ gcc main.c
$ ./a.out
binsearch: 1062 clock ticks
binsearch1test: 777 clock ticks
Notes:
We use
clockfunction from<stdlib>to give an approximate measure of CPU time (in clock ticks) used forbinsearchandbinsearch1testfunctions.
binsearch1testis ~1.4x faster thanbinsearch. This suggest that the compiler cannot predict very accurately that the last branch of if-else statement inbinsearchis only hit once per call at most. So it may cause some missprediction penalty, increasing the CPU time. This can be researched further; Computer Systems - A Programmer’s Perspective is a good introductory book in the subject.
Note
Profiling is used to learn where a program spent its time, to identify the parts we should focus on in our optimization efforts. It is based on stack sampling technique.
Benchmarking is used to measure two or more competing options, in order to compare them. Different techniques may be used.
Using a profiler like gprof to measure the differences in run-time of the 2 functions would have been the wrong approach since a profiler should not be used to measure performance.
Exercise 3-2¶
main.c
#include <stdio.h>
#include <stdlib.h>
#define MAXLINE 80
void escape(char s[], const char t[]);
void unescape(char s[], const char t[]);
int main()
{
char s[MAXLINE];
char *t;
int len;
long unsigned n;
t = NULL;
n = 0;
while ((len = getline(&t, &n, stdin)) > 0){
if (len >= MAXLINE){
printf("error: line too long (max. size:%d)\n", MAXLINE);
return 1;
}
escape(s, t);
printf("%s\n", s);
unescape(t, s);
printf("%s", t);
}
free(t);
return 0;
}
void escape(char s[], const char t[])
{
int i, j;
for (i = 0, j = 0; t[i] != '\0'; ++i, ++j) {
switch (t[i]) {
case '\a':
s[j] = '\\';
s[++j] = 'a';
break;
case '\b':
s[j] = '\\';
s[++j] = 'b';
break;
case '\f':
s[j] = '\\';
s[++j] = 'f';
break;
case '\n':
s[j] = '\\';
s[++j] = 'n';
break;
case '\r':
s[j] = '\\';
s[++j] = 'r';
break;
case '\t':
s[j]= '\\';
s[++j] = 't';
break;
case '\\':
s[j] = '\\';
s[++j] = '\\';
break;
case '\?':
s[j] = '\\';
s[++j] = '\?';
break;
case '\'':
s[j] = '\\';
s[++j] = '\'';
break;
case '\"':
s[j] = '\\';
s[++j] = '\"';
break;
default:
s[j] = t[i];
}
}
s[j] = '\0';
}
void unescape(char s[], const char t[])
{
int i, j;
for (i = 0, j = 0; t[i] != '\0'; ++i, ++j) {
if (t[i] != '\\'){
s[j] = t[i];
}else{
switch (t[i+1]) {
case 'a':
s[j] = '\a';
++i;
break;
case 'b':
s[j] = '\b';
++i;
break;
case 'f':
s[j] = '\f';
++i;
break;
case 'n':
s[j] = '\n';
++i;
break;
case 'r':
s[j] = '\r';
++i;
break;
case 't':
s[j] = '\t';
++i;
break;
case '\\':
s[j] = '\\';
++i;
break;
case '\?':
s[j] = '\?';
++i;
break;
case '\'':
s[j] = '\'';
++i;
break;
case '\"':
s[j] = '\"';
++i;
break;
default:
s[j] = '\\';
}
}
}
s[j] = '\0';
}
Compilation and run:
$ gcc main.c
$ ./a.out
\Difficult subjects cannot be described with light prose
\\Difficult\tsubjects cannot be described\twith light prose\n
\Difficult subjects cannot be described with light prose
Notes:
Notice that, while we do not need to define the size of
tbecause it is allocated bygetlinefunction, we do need to define the size of arrays(dynamic memory allocation is not used until solutions of Chapter 5)
Exercise 3-3¶
main.c
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#define MAXLINE 100
int expand(const char s1[], char s2[], int n);
int main()
{
char *in;
char out[MAXLINE];
long unsigned n;
in = NULL;
n = 0;
while (getline(&in, &n, stdin) > 0){
if (expand(in, out, MAXLINE) == -1){
printf("error expand: insufficient length for s2 (max. size: %d)\n", MAXLINE);
return -1;
}
printf("%s", out);
};
free(in);
return 0;
}
int expand(const char s1[], char s2[], int n)
{
int i, j;
int start, mid, end;
for (i = 0, j = 0; s1[i] != '\0'; i++) {
start = s1[i];
mid = s1[i + 1];
end = mid != '\0' ? s1[i + 2] : '\0';
if (mid == '-' && end > start && ((isdigit(start) && isdigit(end)) ||
(isupper(start) && isupper(end)) ||
(islower(start) && islower(end)) )) {
while (end != start){
s2[j++] = start++;
if (j >= n){
return -1;
}
}
++i;
}else{
s2[j++] = s1[i];
if (j >= n){
return -1;
}
}
}
s2[j] = '\0';
return j;
}
Compilation and run:
$ gcc main.c
$ ./a.out
Normal usage: a-z k-p 0-9 1-4
Normal usage: abcdefghijklmnopqrstuvwxyz klmnop 0123456789 1234
Some things that should not convert: d-c a-4 3-1 b-9 a-Z a--z -z
Some things that should not convert: d-c a-4 3-1 b-9 a-Z a--z -z
Interesting case: a-z0-9
Interesting case: abcdefghijklmnopqrstuvwxyz0123456789
Interesting cases: -a-d- -4-5- a-b-c-d
Interesting cases: -abcd- -45- abcd
Notes:
We added an additional parameter to the original
expanddeclaration to specifys2size and avoid buffer overflowing, since it is not possible to know a priori how much the strings1will be expanded.
Exercise 3-4¶
main.c
#include <stdio.h>
#include <limits.h>
#define CINTLEN 20
#define V_LEN 6
enum {POSITIVE, NEGATIVE};
void itoa(int n, char s[]);
void reverse(char s[]);
int main()
{
char s[CINTLEN];
int n;
while (scanf("%d", &n) == 1){
itoa(n, s);
printf("%s\n", s);
}
return 0;
}
void itoa(int n, char s[])
{
int i;
int sign;
unsigned un;
un = (unsigned) n;
sign = n < 0 ? NEGATIVE : POSITIVE;
if (n < 0){
un = ~un + 1;
}
i = 0;
do{
s[i++] = un % 10 + '0';
} while ((un /= 10) > 0);
if (sign == NEGATIVE){
s[i++] = '-';
}
s[i] = '\0';
reverse(s);
}
void reverse(char s[])
{
int i, j;
char c;
for (j = 0; s[j] != '\0'; ++j);
--j;
for (i = 0; i < j; ++i, --j) {
c = s[i];
s[i] = s[j];
s[j] = c;
}
}
Compilation and run:
$ gcc main.c
$ ./a.out
1234
1234
-4321
-4321
-2147483648
-2147483648
Notes:
The largest negative number cannot be handled in the book version of
itoabecausen = -n;fail; there is no positive representation of it (abs(INT_MAX) < abs(INT_MIN)). We convert any negative value into a positive one by bit manipulation instead of using the unary-operator. We useunsignedtype to manipulate bits, knowing that every absolute value of an integer in a two’s complement representation can be represented in an unsigned representation.Notice that the maximum lenght of
sis not an aleatory number; we use the maximum string length of an integer of at least 8 bytes in a 2 complement representation (2**63 has 20 digits including-). More precise would have been to take into account the byte length of aninttype usingsizeofand to calculate the maximum number of digits.We reuse
reversefunction from Exercise 1-19.
Useful References:
Exercise 3-5¶
main.c
#include <stdio.h>
#include <limits.h>
#define CINTLEN 64
enum {POSITIVE, NEGATIVE};
int itob(int n, char s[], int b);
void reverse(char s[]);
int main()
{
char s[CINTLEN];
int n, b;
while (scanf("%d %d", &n, &b) == 2){
if (itob(n, s, b) != 0){
printf("error itob: invalid base (%d)\n", b);
return 1;
}
printf("%s\n", s);
}
return 0;
}
/* return 0 on sucess an -1 on error */
int itob(int n, char s[], int b)
{
int i;
int sign;
unsigned un;
if (b < 2 || b > (26+10)){
return -1;
}
un = (unsigned) n;
sign = n < 0 ? NEGATIVE : POSITIVE;
if (n < 0){
un = ~un + 1;
}
unsigned next;
i = 0;
do {
next = un % b;
s[i++] = (next <= 9) ? next + '0' : next - 10 + 'A';
} while ((un /= b) != 0);
if (sign == NEGATIVE){
s[i++] = '-';
}
s[i] = '\0';
reverse(s);
return 0;
}
void reverse(char s[])
{
int i, j;
char c;
for (j = 0; s[j] != '\0'; ++j);
--j;
for (i = 0; i < j; ++i, --j) {
c = s[i];
s[i] = s[j];
s[j] = c;
}
}
Compilation and run:
$ gcc main.c
$ ./a.out
15 16
F
15 2
1111
2147483647 2
1111111111111111111111111111111
28 28
10
27 28
R
111 -3
error itob: invalid base (-3)
Notes:
We use the same estructure as Exercise 3-4. One important difference between
itoaanditobis thatitobreturn anintto report errors to the caller.
Useful References:
Exercise 3-6¶
main.c
#include <stdio.h>
#include <limits.h>
#include <string.h>
#define CINTLEN 100
#define V_LEN 6
enum {POSITIVE, NEGATIVE};
int itoa_v2(int n, char s[], int blanks);
void itoa(int n, char s[]);
void reverse(char s[]);
int main()
{
char s[CINTLEN];
int n;
int width;
while (scanf("%d %d", &n, &width) == 2){
if(itoa_v2(n, s, width) != 0){
printf("error itoa: %d too big (max. width: %d)\n", width, CINTLEN);
return 1;
}
printf("%s\n", s);
}
return 0;
}
/* return 0 if success and -1 on error */
int itoa_v2(int n, char s[], int blanks)
{
itoa(n, s);
int len = strlen(s);
if (blanks > CINTLEN){
return -1;
}else if (blanks > len){
int i, j;
for (i = blanks, j = len; i >= 0 ; --i, --j){
s[i] = j >= 0 ? s[j] : ' ';
}
}
return 0;
}
void itoa(int n, char s[])
{
int i;
int sign;
unsigned un;
un = (unsigned) n;
sign = n < 0 ? NEGATIVE : POSITIVE;
if (n < 0){
un = ~un + 1;
}
i = 0;
do{
s[i++] = un % 10 + '0';
} while ((un /= 10) > 0);
if (sign == NEGATIVE){
s[i++] = '-';
}
s[i] = '\0';
reverse(s);
}
void reverse(char s[])
{
int i, j;
char c;
for (j = 0; s[j] != '\0'; ++j);
--j;
for (i = 0; i < j; ++i, --j) {
c = s[i];
s[i] = s[j];
s[j] = c;
}
}
Compilation and run:
$ gcc main.c
$ ./a.out
t
1234 1
1234
1234 5
1234
-123 5
-123
-2147483648 15
-2147483648
12345 999
error itoa: 999 too big (max. width: 100)
Notes:
We use the code of Exercise 3-4 and instead of modifying
itoawe make a wrapper functionitoa_v2.
Useful References:
