How to set masked bits to a specified number?

Question

I haven't been able to find an answer to this on Google, nor do I have any better search ideas. If I have a 2 byte number, a mask, and a third number, how do I replace the masked bits with the third number. For example if I have 0xABCD, the mask 0x0F00, and third number 4 - I would like to replace B with 4 to get A4CD. In other words, I want to be able to replace arbitrary bits selected by a mask with the bits of another arbitrary number (we are assuming that the number replacing the bits fits - i.e. if I mask 5 bits, the number to replace those 5 bits requires 5 bits or less to represent.)

[Boolean algebra](https://en.wikipedia.org/wiki/Boolean_algebra)? — Ted Lyngmo, Sep 30 '21 at 22:34
`(0xABCD & 0xF000)|0x0400` will do it. But it's not clear exactly what your full requirements are and whether that meets the need. — kaylum, Sep 30 '21 at 22:38
@kaylum - that gives 0xA400 - I am trying to get 0xA4CD (in this example) - so far I have come up with VALUE & (~MASK & 0xFFFF) | REPLACEMENT_BITS. But lets say I only specify 4 - how do I determine from the mask that I need to put the 4 in the 3rd byte: f(value, mask, number) = value with masked bits replaced by number. In my example, (0xABCD & (~0x0F00 & 0xFFFF)) | 0x400. — tenspd137, Sep 30 '21 at 23:10
@tenspd137: you asked a fair question. You need to 1) shift the source bits, then 2) replace the target bits, 3) As you anticipated, you also need a bitmask so you can preserve the source bits you're not replacing. Look here: https://stackoverflow.com/a/5925794/421195 — paulsm4, Sep 30 '21 at 23:18
Yeah - AND the original value with the inverse of the bitmask - that gets you all the swap-bits set to zero. AND the replace value with the mask, that gets the bits to be inserted only. OR together and you're done. — Martin James, Oct 01 '21 at 13:38

chqrlie · Accepted Answer · 2021-10-02T10:14:43.380

2

The goal is to replace the bits of number selected by mask with those of value, shifted appropriately, assuming value does not exceed the target range.

Masking off the target bits is easy: number &= ~mask; achieves that simply.

The tricky part is to shift value to the left by the number of zero bits in mask below the set ones. You can write a loop for this.

Here is a simple implementation:

unsigned set_bits(unsigned number, unsigned mask, unsigned value) {
    // assuming mask != 0
    number &= ~mask;
    while (!(mask & 1)) {
        value <<= 1;
        mask >>= 1;
    }
    return number | value;
}

You can compute the shift value as a multiplier this way: subtracting one from the mask sets all its 0 low bits to 1, or-ing this value with mask sets all low bits to 1 and xor-ing with mask yields a mask with just the low bits set. Adding 1 to this mask gives the power of 2 by which to multiply value to shift it in place. This works also if there are no 0 bits in the low order bits of mask.

As commented by aschepler, (A ^ (A | B)) == (~A & B) so the expression ((mask ^ (mask | (mask - 1))) + 1) can be simplified as (((mask - 1) & ~mask) + 1).

An elegant simplification was provided by Falk Hüffner: (((mask - 1) & ~mask) + 1) is just mask & -mask.

Here is a branchless version using this trick:

unsigned set_bits(unsigned number, unsigned mask, unsigned value) {
    return (number & ~mask) | (value * (mask & -mask));
}

Making this an inline function may help the compiler generate optimal code for constant mask values.

edited Oct 02 '21 at 10:14

answered Oct 01 '21 at 19:21

chqrlie

131,814
10
121
189

1

`(A ^ (A | B)) == (~A & B)` always. So `return (number & ~mask) | (value * (((mask-1) & ~mask) + 1));` – aschepler Oct 01 '21 at 20:45
@aschepler: good point! I was wondering how to simplify this expression.. Answer updated – chqrlie Oct 01 '21 at 21:52
Another way would be to use the non-standard but widely available `ffs` function, or an equivalent intrinsic. `(number & ~mask) | (value << (ffs(mask)-1))`, if I'm not mistaken. – Nate Eldredge Oct 01 '21 at 21:57
@NateEldredge Though `ffs` can't benefit from the assumption that the set bits of `mask` are all contiguous, so might or might not perform better. There's also the six methods at https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightLinear if extreme optimization is needed. – aschepler Oct 01 '21 at 22:12
`(((mask - 1) & ~mask) + 1)` is just `mask & -mask`. – Falk Hüffner Oct 02 '21 at 06:54
@FalkHüffner: excellent! bit twiddling at its best כל הכבוד – chqrlie Oct 02 '21 at 10:17

How to set masked bits to a specified number?

1 Answers1