K&R2 solutions:Chapter 2:Exercise 7 - clc-wiki

The C Programming Language, 2nd Edition, by Kernighan and Ritchie
Exercise 2.07 on page 49

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.

Contents

1 Solution by Vidhan Gupta

2 Solution by Gregory Pietsch

3 Solution by Pilcrow

4 Solution by Luke Panayi

5 Solution by Codybartfast (cat 0)

6 Solution by anonymous

7 Solution by Foowar

Solution by Vidhan Gupta

/* Write a function invert (x,p,n) that returns x with the n bits that begin at position p
inverted (i.e., 1 change to 0 and vice versa), leaving the others unchanged */
#include<stdio.h>

unsigned invert(int x, int p, int n);
void printBinary(int n);

int main(){
    int test = 85;
    printBinary(test);
    printBinary(invert(test,4,3));
    return 0;
}

unsigned invert(int x, int p, int n){
    int h = ~(~(~0<<n)<<(p+1-n));
    return (x&h)|(~x&~h);
}

void printBinary(int n){
    int h = sizeof(n) * 8;
    for (int i = h-1; i >= 0; i--)
    {
        int curBit = (n >> i) & 1;
        printf("%d",curBit);
    }
    printf("\n");
}

OUTPUT:-
00000000000000000000000001010101
00000000000000000000000001001001

Solution by Gregory Pietsch

unsigned invert(unsigned x, int p, int n)
{
    return x ^ (~(~0U << n) << p);
}

/*
main driver added, in a hurry while tired, by RJH. Better test driver suggestions are welcomed!

main driver fixed by Flash Gordon as it was passing the parameters in the wrong order and
hex is a more useful output format than decimal for checking the result. Also start at 0
for n,p as they are valid inputs.
*/

#include <stdio.h>

int main(void)
{
  unsigned x;
  int p, n;

  for(x = 0; x < 700; x += 49)
    for(n = 0; n < 8; n++)
      for(p = 0; p < 8; p++)
        printf("%x, %d, %d: %x\n", x, p, n, invert(x, p, n));
  return 0;
}

Solution by Pilcrow

I seem to be all alone here. Oh, well.

GP is in error. Here is a correct solution.

unsigned invert(unsigned x, int p, int n)
{
	return x ^ ((~(~0<<n))<< p+1-n);
}

The another correct solution :

unsigned invert(unsigned x, int p, int n)
{
       return (x ^ (((1 << (n)) - 1) << (p - n + 1)));
}

Solution by Luke Panayi

Fear not Pilcrow, I'll keep you company.

#include <stdio.h>

unsigned invert(unsigned x, int p, int n)
{
	/*
		Example from right to left with x = 01011010 (90 in decimal), p = 4, n = 3
			mask (has the position of bits to be inverted):
			00001111 ^ 00000001 = 00001110
			return:
			01011010 & 11110001 = 01010000 
			10100101 & 00001110 = 00000100 
			01010000 | 00000100 = 01010100
	*/
	unsigned mask = (~(~0 << p)) ^ ~(~0 << p-n);
	return ((x & ~mask) | (~x & mask));
}

int main()
{
	printf("%d\n", invert(90, 4, 3));
	return 0;
}

Solution by Codybartfast (cat 0)

unsigned invert(unsigned x, unsigned p, unsigned n)
{
	return setbits(x, p, n, ~x);
}

Solution by anonymous

getbits based on book and printBinary based on Pilcrow's asbits. To support most data types, long long ints were used for the function's x and y values. The p and n values were set to unsigned chars since the values must be positive and valid values should never be much longer than 64 based on the current minimum size of long long ints (64 bits). If a system has a data type that is larger than 256 bits, than it would be necessary to change the data type to a short or int

Comments were added to thoroughly explain what is going on.

#include <stdio.h>

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

long long int getbits(long long int x, unsigned char p, unsigned char n);
void printBinary(long long int x, size_t size);
long long int invert(long long int x, unsigned char p, unsigned char n);

int main(void)
{
    unsigned char x = 193; // 1100 0001
    printBinary(x, sizeof(x));
    x = invert(x, 4, 3);
    printBinary(x, sizeof(x));

    return 0;
}

// returns x with the n bits inverted that begin at position p and end of p + n by performing the one's complement. The other bits are unchanged.
// p and n must be positive values less than 256
long long int invert(long long int x, unsigned char p, unsigned char n)
{
    // creates a mask n bits long (e.g. if n = 3, then mask == 0000000000000000000000000000000000000000000000000000000000000011)
    long long int mask = ~(~0ULL << n);
    
    // shift is set to the size of the position p minus the length of n. p is zero based
    // this is used to move over the mask that will be used to clear (left side) and invert (rigth side) x's bits
    unsigned int shift = p + 1 - n;

    // x is bitwised AND with the one's complement of shifted mask to zero out the bits at position p to p + n
    // next, x is bitwised OR with the inversed x that was bitwised AND with the shifted mask that only keeps the bits
    // at position p to p + n
    return (x & ~(mask << shift)) | (~x & (mask << shift));
    /*
        For example: this is what would happen if invert(193, 4, 3); was called (all of the leading zeros/ones were removed for brevity):

        long long int mask = ~(~0ULL << n)
        long long int mask = ~(~0ULL << 3)
        long long int mask = ~(~00000000 << 3)
        long long int mask = ~(11111111 << 3)
        long long int mask = ~11111000
        long long int mask = 00000111

        unsigned int shift = p + 1 - n
        unsigned int shift = 4 + 1 - 3
        unsigned int shift = 2

        (193 & ~(mask << shift)) | (~193 & (mask << shift))
        (11000001 & ~(mask << shift)) | (~11000001 & (mask << shift))
        (11000001 & ~(mask << shift)) | (00111110 & (mask << shift))
        (11000001 & ~(00000111 << 2)) | (00111110 & (00000111 << 2))
        (11000001 & ~00011100) | (00111110 & 00011100)
        (11000001 & 11100011) | (00111110 & 00011100)
        11000001 | 00011100
        return 11011101
    */
}

// prints out the binary representation of a value
void printBinary(long long int x, size_t size)
{
    int i;
    for(i = size * 8 - 1; i >= 0; i--)
    {
        if (getbits(x, i, 1) == 1)
            printf("1");
        else
            putchar('0'); // printf("0"); was here but clc-wiki <c> code blocks apparently don't allow "0" unless it is in a comment. Bug?

        if(i % 4 == 0)
            printf(" ");
    }
    printf("\n");
}

// get n bits from position p. Does not support negative numbers for p or n, p is zero based index
// doesn't seem to care if right shift is arithmetic or logical. Returns -1 if p and/or n is invalid
long long int getbits(long long int x, unsigned char p, unsigned char n)
{
    size_t size = sizeof(x) * 8;
    char shift = p + 1 - n;
    if (p >= size || shift < 0)
        return -1;
    else if (n == size && shift == 0)
        return x;

    return (x >> shift) & ~(~0ULL << n);
}

Solution by Foowar

/*
 * 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.
 */

/*
 * the second function is simpler and shorter (better), when I was writing this
 * function I wasn't aware of the property of XOR but it works
 */
unsigned int
invert(unsigned int x, int p, int n)
{
	unsigned int mask;
	unsigned int bits;

	mask = ~(~0 << n);
	mask <<= p+1-n;

	bits = ~(x & mask);
	bits &= mask;

	/* clear the n-bit field from x */
	x &= ~mask;

	return x | bits;
}

/*
 * this function exploit this property of the XOR function:
 * A XOR 0 == A
 * A XOR 1 == NOT A
 */
unsigned int
invert(unsigned int x, int p, int n)
{
	unsigned int mask;

	mask = ~(~0 << n);
	mask <<= p+1-n;

	return x ^ mask;
}

From clc-wiki

Contents

Solution by Vidhan Gupta

Solution by Gregory Pietsch

Solution by Pilcrow

Solution by Luke Panayi

Solution by Codybartfast (cat 0)

Solution by anonymous

Solution by Foowar

Views

Personal tools

Site_logo

Search

Content_hierarchy

Tools