#define abs(x) ((x) < 0 ? -(x) : (x))
/* itoa :convert n to characters in s modified */
void itoa(int n, char s[]){
int i, sign;
void reverse(char s[]);
sign = n; /* record sign */
i = 0;
do { /*generate digits in reverse order */
s[i++] = abs(n % 10) + '0'; /* get next digit */
}while((n /= 10) != 0); /*delete it */
if (sign < 0)
s[i++] = '-';
s[i] = '\0';
reverse(s);
}Write a function expand(s1,s2) that expands shorthand notation like a-z in the string s1 into the equivalent complete list abc—-xyz in s2.Allow for letters of either case and digits, and be prepared to handle cases like a-b-c and a -z0-9 and -a-z.Arrange that a leading or trailing – is taken literally.
/*expand: expand shorthand notation in s1 into string s2 */
void expand(char s1[], char s2[]){
char c;
int i, j;
i =j = 0;
while((c =s1[i++]) != '\0') /* fetch a char from s1[] */
if (s1[i] == '-' && s1[i+ 1] >= c){
i++;
while(c < s1[i]) /* expand shorthand */
s2[j++] = c++;
}else
s2[j++] = c; /* copy the character */
s2[j] = '\0';
}+
+
Write a function escape(s, t) that converts characters like newline and tab int 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.
/*escape: expand newline and tab into visible sequences */
/* while copying the string t to s */
void escape(char s[], char t[]){
switch(t[i]){
case '\n':
s[j++] = '\\';
s[j++] = 'n';
break;
case '\t':
s[j++] = '\\';
s[j++] = 't';
break;
default:
s[j++] = t[i]; /* all other chars */
break;
}
s[j] = '\0';
}
/*unescape: convert escape sequences int real characters */
/* while copying the string t to s */
void unescape(char s[], char t[]){
int i, j;
for(i = j= 0; t[i] != '\0'; i++)
if (t[i] != '\\')
s[j++] = t[i];
else /* it is a backslash */
switch(t[++i]){
case 'n': /* real newline */
s[j++] = '\n';
break;
case 't': /*real tab */
s[j++] = '\t';
break;
default:
s[j++] = '\\';
s[j++] = t[i];
break;
}
s[j] = '\0';
}Write a version of binary search with only one test inside the loop.
/*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;
mid = (low + high) /2;
while (low <= high && x != v[mid]){
if (v < v[mid])
high = mid - 1;
else
low = mid + 1;
mid = (low + high) /2;
}
if (x == v[mid])
return mid; /* found match */
else
return -1; /* no match */
}Rewrite the function lower, which converts upper case letters to lower case, with a conditional expression instead of if-else.
/*lower: convert c to lower case (ASCII only)
int lower(int c){
return c >= 'A' && c <= 'Z' ? c + 'a' - 'A' : c;
}In a two’s complement number system, x &= (x~1) deletes the rightmost 1-bit in x. Explain why.Use this observation to write a faster version of bitcount.
/*bitcount: count 1 bits in x -faster version */
int bitcount(unsigned x){
int b;
for(b =0; x != 0; x &= x~1)
++b;
return b;
}Write a function righrot(x, n) that returns the value of the integer x rotated to the right by n bit positions.
/*rightrot: rotate x to the right by n positions */
unsigned rightrot(unsigned x, int n){
int wordlength(void);
int rbit; /*rightmost bit */
while(n-- > 0){
rbit = (x & 1) << (wordlength() - 1);
x = x >> 1; /*shift x 1 position right */
x = x | rbit; /* complete one rotation */
}
return x;
}
/* wordlength: computes word length of the machine */
int wordlength(void){
int i;
unsigned v = (unsigned) ~0;
for (i =1; (v = v >> 1) > 0; i++)
;
return i;
}
//Alternate solution
/*rightrot: rotate x to the right by n positions */
unsigned rightrot(unsigned x, int n){
int wordlength(void);
unsigned rbits;
if ((n =n % wordlength()) > 0){
rbits = ~(~0 <<n) & x; /*n rightmost bits of x */
/*n rightmost bits to left */
rbits = rbits <<(wordlength() - n);
x = x >> n; /* x shifted n positions right */
x = x | rbits; /* rotation completed */
}
return x;
}
/* ~0 << n => all ones are shifted n positions to the left leaving n in the rightmost positions.
~(~0 << n) all ones are in the n rightmost positionsWrite a function setbits(x, p, n ,y) that returns x with the n bits that begin at position p set to the rightmost n bits of y, leaving the other bits unchanged.
/*setbits: set n bits of x at position p with bits of y */
unsigned setbits(unsigned x, int p, int n, unsigned y){
return x & (~(~(~0 << n) << (p + 1 - n)) | (y & ~(~0 << n)) <<(p +1 - n);
}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.)
/* any:return first location in s1 where any char from s2 occurs */
int any(char s1[], char s2[]){
int i, j;
for(i =0; s1[i] != '\0'; i++)
for (j=0; s2[j] != '\0'; j++)
if(s1[i] == s2[j] /* match found? */
return i;
return -1;
}Write an alternate version of squeeze(s1, s2) that deletes each character in s1 that matches any character in the string s2.
/*squeeze: delete each char in s1 which is i n s2 */
void squeeze(char s1[], char s2[]){
int i, j, l;
for(i=k= 0; s1[i] != '\0'; i++){
for(j=0; s2[j] != '\0' && s2[j] != s1[i]; j++)
;
if (s2[j] == '\0') /*end of string- no match */
s1[k++] =s1[i];
}
}
KandRcode.com 