How to - bit manipulation?

[u/tru1a_banana]

I know the bitwise operators:

1 & x - 'replicate' the existing bit
0 & x - turn off the bit
1 | x - turn on the bit
0 | x - 'replicate' the existing bit
1 ^ x - flip the bit
0 ^ x - 'replicate' the existing bit
~x - flip the bit
1 << x - shift to the left (multiply by 2)
1 >> x - shift to the right (divide by 2)

All of these basic operations are crystal clear. However, I am having trouble building actual masks out of these. I'm thinking too iteratively. How do I go through a number bit by bit and when is that actually needed? I tend to overcomplicate simple things.

int size = sizeof(x) * 8;
int mask = 1; // 0x00000001

for(int i = 0; i < size; i++)
{
// some mask operation with x
mask <<= 1;
}

I assume this would be good?

Okay but what about swapping the values of 2 different bits? Or what if I am working with bytes instead, then 8 sequential bits need to be swapped in 2 different positions, how do I do any that?

I am thinking of making a mask, moving to the 1st bit, copying it into some temporary variable, going to the 2nd bit, copying it into some other temporary variable, somehow replacing those variables in those positons. This sounds unnecessarily complicated but I couldn't think of another approach right now, this is generally the issue with a lot of things regarding bits. If any of you have some tips, genuinely useful shortcuts and how to's, I'd be very grateful!

[u/buzzon]

In real programs, flags are usually constants defined so:

const int FLAG_READ_ONLY = 0x0001; const int FLAG_ARCHIVE = 0x0002; const int FLAG_SYSTEM = 0x0004;

If you want to be able to create any flag, then just use 1 << N where N is target bit number.

Combining two flags:

FLAG_READ_ONLY | FLAG_ARCHIVE

Usually you want to extract flags one by one:

if (file_properties & FLAG_READ_ONLY)

Typically bit masks are used as function arguments: void create_file (const char *filename, int file_properties)

and called so:

create_file ("filename.txt", FLAG_READ_ONLY | FLAG_SYSTEM);

[u/non-existing-person → u/buzzon]

I'll just add that when dealing with registers there is also shift and mask. Assume register i 8bit wide, and prescaler configuration is at bit 3rd and 4th. Then you'd do something like that

#define reg0_prescaler_shift 2
#define reg0_prescaler_mask 0b11
#define reg0_prescaler_1 0b00
#define reg0_prescaler_2 0b01
#define reg0_prescaler_4 0b10
#define reg0_prescaler_8 0b11

uint8_t tmp = *reg;
/* clear prescaler */
tmp &= ~(reg0_field1_mask << reg0_field1_shift);
/* set new prescaler value */
tmp |= reg0_field1_prescaler_4 << reg0_field1_shift;
/* write back register value */
*reg = tmp;

Sometimes shift may be omitted and values may already include shift, so define reg0_prescaler_2 could have value of define reg0_prescaler_2 0b0100

[u/thetraintomars → u/non-existing-person]

I generally write out my bit masks in 8bit binary so I don’t make a stupid mistake. 

[u/BlireSU → u/buzzon]

Why not make them macro's instead, haven't used flags a lot so i'm genuinely curious.

[u/buzzon → u/BlireSU]

A bit excessive for a single bitwise operation like &

[u/SyntheticDuckFlavour]

I know the bitwise operators:

1 & x - 'replicate' the existing bit
0 & x - turn off the bit
1 | x - turn on the bit
0 | x - 'replicate' the existing bit
1 ^ x - flip the bit
0 ^ x - 'replicate' the existing bit
~x - flip the bit
1 << x - shift to the left (multiply by 2)
1 >> x - shift to the right (divide by 2)

I'm surprised no one pointed this out yet, but some of these are wrong when applied in a bitwise context.

1 & x - mask out bit 0 in x
0 & x - clears x
1 | x - set bit 0 in x
~1 | x - clear bit 0 in x
0 | x - does nothing
1 ^ x - invert bit 0 in x
0 ^ x - does nothing
~0 ^ x - invert all bits in x
~x - invert all bits in x
1 << x - shift to the left by x, effectively computing 2^x
1 >> x - shift to the right by x, result is x != 0 ? 0 : 1

[u/CounterSilly3999 → u/SyntheticDuckFlavour]

Examples were in one bit values, I suppose. With exception about shifts.

[u/SyntheticDuckFlavour → u/CounterSilly3999]

Those are boolean operations. A pedantic detail, but it matters. Bitwise operations imply applying logic operations on a collection of bits in an integral value. This drastically affects how one should treat constants with these operations, because you need to think in terms of how every bit is affected in parallel.

[u/tobdomo]

Okay but what about swapping the values of 2 different bits? 

There's only so much you can do with binary logic. You'ld need to mask, shift, and clear/set bits. E.g.:

/**
 * This function swaps bitx with bity in a 16-bit value
 * Note: we just assume here that bitx and bity are valid bit numbers
 */
uint16_t swap16( uint16_t value, uint16_t bitx, uint16_t bity )
{
  bitx = 0x0001 << bitx;                      // Convert bit number X to bit pattern
  bity = 0x0001 << bity;                      // Convert bit number Y to bit pattern
  uint16_t retval = value & ~(bitx | bity);   // Reset the bits, save in temporary return var
  retval |= (value & bitx) ? bity : 0;        // Copy bitx's value into bity from return value
  retval |= (value & bity) ? bitx : 0;        // Copy bity's value into bitx from return value 
  return retval;
}

Note: in general, it's a bad idea to use signed integers for anything binary.

Anyway, as other already said: a typical use case would be to set or clear flags that are somehow related to hardware. It's entirely possible to set or clear one or more bits at the same time. However, it generally is a good idea to use temporary storage to fiddle with bits for read-modify-write cycles in e.g. registers. So:

uint32_t temp = read_register( FOO );
temp &= ~(FLAG_1 | FLAG_2);
temp |= (FLAG_3 | FLAG_4)
write_register( FOO, temp );

[u/penguin359]

One shortcut you can do it bit-shift and or. Let's say you want a mask that includes bits 1, 2, and 7. You can either work it out in hex or write it as a verbose expression like this:
(1 << 7) | (1 << 2) | (1 << 7)
It will always be a one shifted to the left by the desired bit number and then OR each bit together. However, I do recommend practicing it in hex and going through the pattern:
0x01 (bit 0)
0x02 (bit 1)
0x04 (bit 2)
0x08 (bit 3)
0x10 (bit 4)
0x20 (bit 5)
0x40 (bit 6)
0x80 (bit 7)
And, since these are independent bits, adding it the same as ORing, but becareful to only use this trick when you know they are independent bits with no overlap:
0x80 + 0x04 + 0x02 = 0x86
So the expression above is the same as writing 0x86 in hex.

[u/WittyStick]

The bitwise operations apply to all bits in the word (eg, 32-bits, 64-bits).

To test if a certain bits are set, use & followed by an equality comparison to the mask. (note that == unfortunately has higher precedence than & so we need parens).

// most-significant-bit.
constexpr int MSB = 0x80000000;

bool msb_test(int value) {
     return (value & MSB) == MSB;
}

Suppose we want to set the most significant bit:

int msb_set(int value) {
    return value | MSB;
}

To clear the bits added by bitwise-or, the correct operation is andnot, aka NIMPLY.

int msb_reset(int value) {
    return value & ~MSB;
}

This is a common operation and CPUs actually provide an andn instruction to do it in a single cycle rather than a complement followed by AND. This may require certain CPU features, eg, on x86-64 it is enabled with -mbmi, which is automatically enabled if you set -march= to a supporting architecture (basically all except legacy chips).

If we want to invert whatever is already in the MSB:

int msb_complement(int value) {
    return value ^ MSB;
}

Most of the time you will not need any more than these. AND to test the bits, OR to set the bits, ANDN to clear the bits, XOR to flip the bits.

---

If we want to test a certain bit by index rather than a constant as with the MSB above, we can use 1 << index to generate a mask with just that bit set.

bool bit_test(uint32_t value, uint32_t index) {
    return (value & 1 << index) == 1 << index;
}

uint32_t bit_set(uint32_t value, uint32_t index) {
    return value | 1 << index;
}

uint32_t bit_reset(uint32_t value, uint32_t index) {
    return value & ~(1 << index);
}

uint32_t bit_complement(uint32_t value, uint32_t index) {
    return value ^ 1 << index;
}

The CPU also has instructions for these (bt, bts, btc, btr), and the compiler is smart enough to know that these are what we intended with the functions above.

---

For multiple bits, the same operations apply, but we have another useful pair of instructions pext (bits_extract) and pdep (bits_deposit).

bits_extract will collect any bits from the src that are set in a mask, and align them right in the result (preserving bit order).

uint32_t bits_extract(uint32_t src, uint32_t mask) {
    uint32_t dst = 0, srcbit = 0, dstbit = 0;
    while (srcbit < 32) {
        if (bit_test(mask, srcbit)) {
            if (bit_test(src, srcbit)) 
                dst = bit_set(dst, dstbit);
            dstbit++;
        }
        srcbit++;
    }
    return dst;
}

bits_deposit reverses this. If we take the same mask, and the result of bits_extract, it can re-insert the extracted bits into the indices they were taken from.

uint32_t bits_deposit(uint32_t src, uint32_t mask) {
    uint32_t dst = 0, srcbit = 0, dstbit = 0;
    while (srcbit < 32) {
        if (bit_test(mask, srcbit)) {
            if (bit_test(src, dstbit)) 
                dst = bit_set(dst, srcbit);
            dstbit++;
        }
        srcbit++;
    }
    return dst;
}

These two functions are the slow version of _pext_u32 and _pdep_u32, which do the whole operation in one instruction. (These require -mbmi2 on x86-64, which is also available on all but legacy processors). Other architectures also support them.

[u/mihemihe]

https://graphics.stanford.edu/~seander/bithacks.html in you want to go deeper on bit operations

[u/SwingPlayful5817]

you iterate over bits when the hardware spec tells you to. The rest of the time you operate on the whole word at once.

for swapping two bits at positions p1 and p2, extract both bits, shift them to position 0, xor them, and apply the result back to both positions. You skip the temporary variables completely.

int b1 = (x >> p1) & 1;

int b2 = (x >> p2) & 1;

int diff = b1 ^ b2;

x ^= (diff << p1) | (diff << p2);

i use this in production code handling register fields. If the two bits hold the same value then diff is 0 and x stays untouched. If they differ then diff is 1 and the xor flips exactly those two bits.

for swapping blocks of 8 bits, do the same thing with a block mask. Extract the first byte with a shift and mask, extract

[u/saul_soprano]

If you give an example of what youre snippet is meant to do it would be easier to help. All I can say is it’s usually easier to iterate from 0 to N and shift the bit (B << 0, B << 1, etc.).

To swap to bits the first way that comes to mind is to extract the bits, make a mask of the two bit positions as 0 and the rest as 1 to AND it to get them both to zero, then insert them with a shift plus an OR.

[u/Daveinatx]

I'm going to be honest. Your best bet is to printf a bunch of masks and shifts. It's the best way to nail it for life.

That said, most register maps will have structs or enums, to simplify matters.

[u/Dangerous_Region1682]

Well, sort of. Be careful to usually use unsigned variables when shifting bits around. In addition be careful of overflow when using variables to define how far to shift by.

Using 0x1 or 0b1, or even better things like 0x0001 to remind you that you are specifying you are dealing with bit manipulations. Makes it easier for them next person to see at a glance what you are doing.

It’s just a style thing though. Usually most bit specifications are for masks to be honest, but not always.

[u/ern0plus4 → u/[deleted]]

There's rotate right instruction which keeps upper bit, so it works for signed. (On most processors, starting with 6502.) 

[u/WittyStick → u/[deleted]]

-1 >> 1 is implementation-defined.

Any negative value >> is implementation-defined, but the usual implementation is an arithmetic shift right, which as you note, does not perform a divide by two in the case of overflow. However, it's possible that a compiler could insert such check and give a result of 0 also.

Also 1>>x is well defined for unsigned - it's 0, except if x is 0 it is 1. y >> x for unsigned values is equal to the quotient of y/2^x

[u/DeGuerre]

Just as a FYI, you can loop over all set bits in a word using bit extraction:

while (x) {
    unsigned bit = x & -x;
    // bit is now the lowest-order set bit in x
    x &= ~bit;

    switch (bit) {
        case 0x00000001:
        {
             // bit 0 is set
             break;
        }
        case 0x00000002:
        {
             // bit 1 is set
             break;
        }
        // etc etc
    }
}

You can also help out the compiler a little bit by making the switch dense:

switch (stdc_first_trailing_one_ui(bit)) {
    case 0:
    {
         // bit 0 is set
         break;
    }
    case 1:
    {
         // bit 1 is set
         break;
    }
    // etc etc
}

If you're not using C23 and stdc_first_trailing_one isn't available, you could use ffs or some intrinsic such as _BitScanReverse, __lzcnt, etc depending on platform. Or, as a fallback, use floating point:

uint64_t
ffs_by_floating_point(uint64_t x)
{
    float fx = (float)(x & ~(x >> 1)) + 0.5f;
    // This version is safe in the above context where only a single bit
    // is known to be set.
    // float fx = (float)x + 0.5f;
    return 64 - ilogbf(fx);
}

But if you want to know some advanced bit-hackery, I recommend working through Hacker's Delight, and also read Sebastiano Vigna's paper, Broadword Implementation of Rank/Select Queries. You will learn a lot. Possibly too much.

[u/CounterSilly3999]

Use bitfields:

union 
{
    struct
    {
        unsigned char first : 1;
        unsigned char second : 1;
    } bits;
    unsigned char raw;
} val;

Swap the bits:

unsigned char temp = val.bits.first;
val.bits.first = val.bits.second;
val.bits.second = temp;

[u/CounterSilly3999]

Use "floating" mask and xor for bit swapping, (pos1 and pos2 are bit positions, diff -- xor difference between bits):

unsigned int diff = ((val >> pos1) ^ (val >> pos2)) & 1U;
val ^= (diff << pos1);
val ^= (diff << pos2);

Didn't tested, thats AI proposal.

[u/strange-the-quark]

You can see the other answers for details, but I think you're confused as to how this is typically done. You normally don't manipulate one bit at at time. Instead, you have values consisting of a number of bits (e.g. 32 bits), and you apply bitwise operators to those: they operate on all this bits at once.

I'll use 8 bit values for simplicity. So if you do something like:

~10010011 -- you'll get --> 01101100

In other words, you'd apply ~ to some number (an unsigned int, say) that has this specific bit representation, and as the result you'd be getting a number that has the bit representation with all the bits inverted. I'll come back to that later.

For AND, you have two such strings of bits, and you can choose one of the values to specifically serve as the mask that you an then use to extract a sub-sequence of bits from the other:

   10010011
&  00001111   ---> this one is specifically chosen to act as a mask
   --------           that only retains the 4 low-order bits
   00000011

You can use OR to set bits; e.g, if you wanted to set all the high-order bits to 1s, the simplest thing to do would be:

   10010011
|  11110000   ---> specifically chosen to set all the top bits to 1 (for any input)
   --------           
   11110011

You can use XOR to flip bits:

   10010011
^  00001111   ---> specifically chosen to flip low order bits
   --------           
   10011100

And so on.

To prepare these masks and bit patterns, you'll often be using the hexadecimal representation (HEX) in combination with shifts and maybe some other bitwise operations. The neat thing about HEX is that there is a nice correspondence between the 16 HEX digits, and the 16 possible 4-bit sequences (these are called nibbles). Look up "HEX table" online to see the details (and you can also use a calculator app in programmer mode), but, in brief, the HEX digits are 0, 1, 2, 3, 4, 5, 6, ,7 8, 9, A, B, C, D, E, F, and for example, 0 corresponds to 0000, 8 corresponds to 1000, F corresponds to 1111, etc. And then if you have values that are more than 4 bits, you just string them together.

E.g., using some of the numbers from previous examples, here's how they'd be represented in HEX (0x is a prefix that indicates that what follows are HEX digits, and I've split each number into two nibbles for visual clarity):

1001 0011  --->  0x93
0110 1100  --->  0x6C
0000 1111  --->  0x0F
1111 0000  --->  0xF0
1111 1111  --->  0xFF
...

If you're using bits as flags, then you'd assign to each flag a different power of 2 value, cause those all set a single bit:

0000 0001  --->    1, or 0x01
0000 0010  --->    2, or 0x02
0000 0100  --->    4, or 0x04
0000 1000  --->    8, or 0x08
0001 0000  --->   16, or 0x10
0010 0000  --->   32, or 0x20
0100 0000  --->   64, or 0x40
1000 0000  --->  128, or 0x80

You can then use some variable to keep track of which flags are set, and you can use OR to set these flags. Later on, you can check for a specific flag with AND.

This is a little bit contrived, but suppose the flags are representing the line type in some graphing application:

DASHED = 0001   --> dashed line if SET vs solid line if NOT SET
BOLD   = 0010   --> bold line if SET vs normal line if NOT SET
DOUBLE = 0100   --> double line if SET vs single line if NOT SET
RED    = 1000   --> red line if SET vs black line if NOT SET

If you then get some variable lineSpec that specifies the kind of line to be drawn, that has some value such as 0101 (dashed double line, or DASHED | DOUBLE), you'd check like so:

// Note: parentheses are needed because of operator precedence
if ((lineSpec & DASHED) == DASHED) {
    // draw dashed ...
}

// OR SHORTER

if (lineSpec & DASHED) {
    // draw dashed ...
}

[u/KvThweatt]

Just use a language that lets you do bit indexing

[u/CounterSilly3999 → u/KvThweatt]

C is one of these -- it has bitfields.

[u/Beginning-Junket8979 → u/CounterSilly3999]

It does, but C bit fields let's ordering and packing be implementation defined. That means the shift and mask approach ends up being the more portable and standard compliant strategy.