Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Does anyone have a shorter more simple way of doing this?

/*
 * Next write a function invert(x,p,n) that returns x with the n bits
 * that begin at position p inverted, leaving the others unchange
 */

void printbits(unsigned x) {
    size_t size_of_int = sizeof(int) << 3;
    unsigned mask = 1;
    int i = 0;
    for(i = 1; i <= size_of_int; ++i, x >>= 1) {
       ((x & mask) == 0) ? printf("0") : printf("1");
       ((i & 3)==0) ? printf(" ") : printf("%s","");
    }
    printf("\n");
}

void invert(unsigned x, unsigned p, unsigned n) {
    printbits(((~((((~(~0 << n) << p))) & x)) & (~(~0 << n) << p)) | (x & ~(~(~0 << n) << p)));
}

int main(int argc, char *argv[]) {
    unsigned input=3082676239, begin=15, nbits=5;
    invert(input, begin, nbits);
    return(0);
}

Before mushing the parts together this is what I get in output:

              x = 1111 0000 0001 0111 1011 1101 1110 1101 
===================================================================
          mask0 = 1111 0000 0001 0110 0000 1101 1110 1101 
          mask1 = 1111 1111 1111 1110 0100 1111 1111 1111 
          mask2 = 0000 0000 0000 0001 1111 0000 0000 0000 
===================================================================
         output = 1111 0000 0001 0110 0100 1101 1110 1101 
share|improve this question
add comment

3 Answers

up vote 1 down vote accepted

Maybe:

void invert2(unsigned x, unsigned p, unsigned n) {
    printbits((~(~0 << n) << p) ^ x);
}
share|improve this answer
add comment

While @palacsint's code may work, it doesn't impress me as a model of clarity. I think I'd start from the fact that subtracting 1 from a number clears the least significant bit that was set, and sets all the less significant bits. If we start with a number that has only one bit set, that bit will be cleared, and all the less significant bits will be set. Based on that, getting a mask of N bits is pretty simple: take 1, shift it left N bits, and then subtract 1.

For example, consider creating a 5-bit mask in a 16-bit number:

0000 0000 0000 0001    // 1
0000 0000 0010 0000    // 1 << 5
0000 0000 0001 1111    // (1<<5)-1

Once we have that, we can shift it left p bits to get it to the right position, and xor with the input:

unsigned invert(unsigned x, unsigned p, unsigned n) { 
    unsigned mask = ((1u << n) - 1u) << p;
    return x ^ mask;
}

A couple minor points:

  1. I've removed printing from invert -- IMO, printing the result should be separate.
  2. This requires that n<size_of_int.

I think the printing can be simplified a bit as well. Although the "test for a multiple of 4" inside the loop does work, I think at least in this case a nested loop makes the intent clearer:

void print(unsigned x) { 
    static const int group_size = 4;
    int group, j;

    for (group = 0; group < size_of_int / group_size; group++) {
        for (j=0; j<group_size; j++, x >>= 1)
            printf("%c", (x & 1) + '0');
        printf(" ");
    }
}

Another possibility that might be worth considering would be a small lookup table to convert 4 bits at a time:

void print(unsigned x) { 
    static const int group_size = 4;
    // inverted order because you're printing the LSB first.
    static const char *outputs[] = {
        "0000", "1000", "0100", "1100", "0010", "1010", "0110", "1110", 
        "0001", "1001", "0101", "1101", "0011", "1011", "0111", "1111"
    };
    int group;

    for (group=0; group<size_of_int / group_size; group++, x >>= 4)
        printf("%s ", outputs[x & 0xf]);
}
share|improve this answer
 
+1 Jerry, I agree, your solution is much better and much more elaborated. To defend myself, my answer is only a quick note and it's still more simple than the one in the question. –  palacsint Nov 18 '11 at 9:34
 
@palacsint: Yup -- it's definitely an improvement, and in fairness, it seems pretty clear that the code in the question is the source of most of the obfuscation. My remark was intended mostly as saying that what you posted was a big improvement, but I thought it was possible to do even a little better still. –  Jerry Coffin Nov 18 '11 at 15:21
add comment

Oh for the love of obsuscation... You should certainly not write this as a one-line goo of bit-wise operators. Use the invert function below. For convenience, I added a function for programmers who don't read binary code.

#include <stdint.h>
#include <stdio.h>

uint32_t invert (uint32_t number, uint32_t pos, uint32_t bits_n)
{
  uint32_t i;

  for(i=pos; i<pos+bits_n; i++)
  {
    number ^= (1<<i);
  }

  return number;
}


void print_binary_because_I_dont_understand_hex (uint32_t number)
{
  uint32_t i;

  for(i=32; i!=0; --i)
  {
    if( number & (1<<(i-1)) )
    {
      printf("1");
    }
    else
    {
      printf("0");
    }
    if( ((i-1) % 4) == 0 )
    {
      printf(" ");
    }
  }
  printf("\n");
}

int main()
{
  uint32_t some_int = 0xFFFFAAAA;

  some_int = invert(some_int, 8, 16);

  printf("%X\n", some_int);
  print_binary_because_I_dont_understand_hex (some_int);

  getchar();
  return 0;
}
share|improve this answer
 
Hmmm...I can't really agree. A fair amount of work on this order is done in small embedded systems that frequently need real-time response. The routine I've given is likely to be 4 instructions long, and execute in constant time. Replacing that with a routine that's likely to be two or three times as long and have variable execution time just because you don't understand subtraction may be reasonable at times, but it's hardly universal. –  Jerry Coffin Nov 18 '11 at 15:42
 
@JerryCoffin: That's best left to the compiler I think. Bitwise operations and for loops should be easy to optimize for it. I suspect/hope most compilers translate that loop to a single XOR instruction, but I haven't checked. Also, from the OP's code we can tell that this is code for a hosted system, and likely not a small embedded one. –  Lundin Nov 18 '11 at 23:20
 
I have checked. Neither VC++ nor gcc does (and I'd be quite surprised to find a compiler that did). It seems likely to me that this is homework, so what he's writing for now and the ultimate target are likely to be two entirely different things. –  Jerry Coffin Nov 18 '11 at 23:35
 
@JerryCoffin: I tested it on some embedded compilers as well, indeed it turns out they won't optimize this code well. Then your code is more suitable for real-world implementations (if performance is critical). This code is however very easy to read and understand, for a beginner it is a good starting point before moving on to optimizations. –  Lundin Nov 21 '11 at 7:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.