Exercise 2-7 (Invert bits)

Chapter_2     Exercise_2-6

Exercise_2-8

---

---

Exercise 2-7     K&R, p. 49

Exercise 2-7. Write a function invert(x,p,n) that returns x with the n bits that begin at position p inverted (i.e. 1 changed into 0 and vice versa), leaving the others unchanged.

invert.c         download

#include <stdio.h> // for printf(), scanf(), putchar()

#define LENGTH 100 // bits

// invert the last n bits of x starting at position p:
unsigned invert(unsigned x, int p, int n);
// reverse s[], knowing its length:
void reverse(char s[], int len);
// get the bits of x into bits[], return length of bits[] (no of bits):
int bitstring (char bits[], unsigned x);

int main()
{
char bits[LENGTH];
unsigned x;
int len, p, n, diff;

printf("Give a positive integer: ");
scanf("%u", &x);

len = bitstring(bits, x);

printf("x: %s\n", bits);

printf("Invert last 0 <= n <= %d bits of x ", len);
printf("starting at position max(0, n-1) <= p <=%d:\n", len-1);
printf ("n = ");
scanf("%d", &n);
printf ("p = ");
scanf("%d", &p);

x = invert(x,p,n);
len = bitstring(bits, x);
diff = n - len;
while (diff > 0)
{
putchar('0');
diff--;
}
printf("%s\n", bits);

return 0;
}
// invert the last n bits of x starting at position p:
unsigned invert(unsigned x, int p, int n)
{ // exclusive OR with 1 inverts the bit, exclusive OR with 0 changes nothing
unsigned mask = ~(~0 << n); // ends in n bits of 1s
mask = mask << (p+1-n); // 0..0(n bits of 1)0..0

return mask ^ x; // invert the last n bits of x starting at position p
}
// reverse s[], knowing its length:
void reverse(char s[], int len)
{
int i = 0, j = len-1;
char temp;

while (i < j)
{
temp = s[i];
s[i] = s[j];
s[j] = temp;
i++;
j--;
}
}
// get the bits of x into bits[], return length of bits[] (no of bits):
int bitstring (char bits[], unsigned x)
{
int i = 0;

if (x == 0)
{
bits[i++] = '0';
bits[i] = '\0';

return i;
}

while (x > 0)
{ // last bit gives the parity:
bits[i++] = '0' + x % 2; // 0 for even, 1 for odd
x /= 2; // x = x / 2; // lose last bit
}
bits[i] = '\0'; // end the string

reverse(bits, i);

return i;
}
/*
gcc invert.c -o invert
./invert
Give a positive integer: 74
x: 1001010
Invert last 0 <= n <= 7 bits of x starting at position max(0, n-1) <= p <=6:
n = 3
p = 4
1010110

./invert
Give a positive integer: 83
x: 1010011
Invert last 0 <= n <= 7 bits of x starting at position max(0, n-1) <= p <=6:
n = 7
p = 6
0101100

./invert
Give a positive integer: 12345
x: 11000000111001
Invert last 0 <= n <= 14 bits of x starting at position max(0, n-1) <= p <=13:
n = 5
p = 10
11011111111001
*/

---

---

Chapter_2     Exercise_2-6

BACK_TO_TOP

Exercise_2-8