Search code examples
bit-manipulationbitwise-operators

How to efficiently replace a contiguous set of bits


Let's say I have a binary number 1001100, and I want to substitute it with 1011 at the section [2, 6).

It would look something like this:

Binary: 1001100
Sub:    --1011-
Result: 1010110

I know it's possible to repeatedly set a single bit multiple times using this code:
number |= 1UL << n;

But I was wondering if there was a way to generally achieve this, in a more efficient way.


Solution

  • Lets consider a more general problem: you have a binary number a, and you want to replace its bits by bits of another number b, only when the corresponding bit of third number m is one.

    For your specific problem:

    a = 1001100
    b = xx1011x
    m = 0011110
    

    but there is no need to have m correspond to a single range.

    A pseudo code to compute the result r would be

    for all i in 0 to 6
      if m[i]=1
         r[i]=a[i]
      else
        r[i]=b[i]  
    

    or equivalently

    for all i in 0 to 6
      r[i] = (a[i] and (m[i]=1)) or (b[i] and (m[i]=0))
    

    We can easily deduce from this that the loop is useless and that the expression

    r = (a & m) | (b & ~m)
    

    gives the correct result.

    Note that if you want to have a replacement on a specific range k to l (1 to 5 for instance in your case), the mask will be (2^l - 1) - (2^k - 1) = 2^l - 2^k

    So here is corresponding C code

    unsigned int replace_bit(unsigned int a, unsigned int b, int k, int l){
      unsigned int mask=(1<<l) - (1<<k)
      return  (a & mask) | (b & ~mask) ;
    }