2

I want to develop a function in C that set a binary field in array starting from a given offset and finish with a given length.

For example, my binary array is:

01101011 10010101 11001011 11010001 11000101 00101011

the buffer used for set:

10011001 01011011 10100010

So if the offset = 5 and the length = 7, the result will be

we will set the 7 first bit from the set buffer (1001100) in the binary buffer starting from the offset 5:

01101100 11000101 11001011 11010001 11000101 00101011
     ^      ^
     |      |__End of set field (len=7)
   offset=5

Are there predefined algorithms for that? using bitwise operators?

MOHAMED
  • 41,599
  • 58
  • 163
  • 268

1 Answers1

2

Given char * arrays, you can easily implement operators set and get to set and retrieve, respectively, the i-th bit:

void set(char *a, int position, int value) {
     int byte = position >> 3;
     int bit = 1 << (position & 0x07); // 00000001b to 10000000b
     a[byte] = value ? 
           a[byte] | bit :  // on
           a[byte] & ~bit;  // off
}

int get(char *a, int position) {
     return a[position>>3] & (1 << (position&0x07)) ? 1 : 0;
}

This can be made slightly faster with compiler intrinsics to get both division and modulus at the same time, and there is probably some bitwise trick to avoid branching in 'set' - but hopefully this code communicates the gist of the operation.

Implementing your desired function is essentially an extension of the code in my set function, where instead of only touching one bit, you continue until you run out of bits to modify, starting at the indicated offset.

Edit: adding a bitwise trick from this answer to remove branching from set:

void set(char *a, int position, int value) {
     int byte = position >> 3;
     int offset = position & 0x07);
     a[byte] = (a[byte] & ~(1<<offset)) | (value<<offset);
}

Note that this version requires value to be either 0 or 1; the previous version would work with any false or true (=zero vs. non-zero) value.

tucuxi
  • 17,561
  • 2
  • 43
  • 74