Bit Manipulation
This is the volume that makes C an embedded language. Hardware is controlled one bit at a time, so firmware sets, clears, flips and tests bits all day long. Here are the four operators that do it, the shift that builds a mask, the pattern for multi-bit fields, and the puzzles interviewers ask to see whether you really understand them.
- What AND, OR, XOR and NOT each do to a bit, and which one to reach for
- How shifts build masks, and the two edges where shifting misbehaves
- The four one-line patterns: set, clear, toggle and test a bit
- How to read and write a multi-bit field without disturbing its neighbours
- What bit-fields in structs are good for, and why drivers still prefer masks
- The classic puzzles: counting set bits, powers of two, swapping without a temporary
4.1 AND, OR, XOR and NOT
Four operators work on bits instead of numbers. AND clears, OR sets, XOR flips, and NOT inverts everything. Every driver you will ever write is built from these.
a 1100 1010 0xCA
b 0110 1111 0x6F
a & b 0100 1010 0x4A
a | b 1110 1111 0xEF
a ^ b 1010 0101 0xA5
~a 0011 0101 0x35
Each result is worked out one column at a time, with no carrying between columns. That is the whole difference from ordinary arithmetic.
| Bit in a | Bit in b | a & b |
a \| b |
a ^ b |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
What each one is really for
A mask is a value whose 1 bits mark the bits you care about. You choose the operator by what you want done to those bits: AND to clear, OR to set, XOR to flip.
XOR has a second use worth remembering: applying the same value twice gives the original back.
0x33 ^ 0x5A = 0x69, and ^ 0x5A again gives 0x33
You want to clear the bits marked by MASK and leave everything else alone. Which line does it?
Show the answer
Answer: C. ~MASK has 0 where MASK had 1, and 1 everywhere else. ANDing with it clears exactly the marked bits and keeps the rest.
4.2 Shifts
A shift slides every bit left or right. It is how a mask is built from a bit number, and how a field is moved into place.
0x03 << 1 = 0x06
0x03 << 4 = 0x30
0x03 << 7 = 0x80 (bits fall off the top)
0x80 >> 3 = 0x10
25 << 3 = 200, which is 25 * 8
200 >> 2 = 50, which is 200 / 4
Bits pushed off the end are gone, and zeros come in behind. A left shift by n multiplies by 2ⁿ; a right shift on an unsigned value divides by it and throws away the remainder.
Building a mask from a bit number
This one line is the foundation of the rest of the volume:
#define BIT(n) (1u << (n))
bit 0 is 0x01 bit 4 is 0x10
bit 1 is 0x02 bit 5 is 0x20
bit 2 is 0x04 bit 6 is 0x40
bit 3 is 0x08 bit 7 is 0x80
Shifting by the width or more is undefined behaviour. 1u << 32 on a 32-bit unsigned is not
0 - it is undefined, and different chips really do give different answers. Keep the shift below the
width of the type.
Right-shifting a negative number is up to the compiler. On gcc, -8 >> 1 gives −4, because the
sign bit is copied in. The standard does not promise that. Shift unsigned values, and you never
have to care.
Shifting a value that is too narrow. On a 32-bit register you must write 1u << 20, not 1 << 20
in an 8-bit or 16-bit variable. The constant 1 is an int, so 1 << 31 is already on the edge;
1u << 31 is safe. For 64-bit work, use 1ull << n.
What does 1u << 5 give?
Show the answer
Answer: B. The single 1 bit moves five places left, landing in bit 5, which is worth 32 - that is 0x20. This is the standard way to write "the mask for bit 5".
4.3 Set, clear, toggle and test a bit
Four one-line patterns, learned once, used for ever: set a bit, clear a bit, toggle a bit, test a bit.
#define BIT(n) (1u << (n))
#define SET_BIT(r, n) ((r) |= (uint8_t)BIT(n)) /* OR with the mask */
#define CLEAR_BIT(r, n) ((r) &= (uint8_t)~BIT(n)) /* AND with the inverted mask */
#define TOGGLE_BIT(r, n) ((r) ^= (uint8_t)BIT(n)) /* XOR with the mask */
#define TEST_BIT(r, n) (((r) & BIT(n)) != 0u) /* AND, then compare */
after setting bit 3: 0x08
after setting bit 5: 0x28
after clearing bit 3: 0x20
after toggling bit 5: 0x00
after toggling again: 0x20
bit 7 set? yes
bit 0 set? no
read 0xA0, set bit 1, wrote 0xA2
three bits in one write: 0x51
Setting several bits at once needs only one OR:
port |= (uint8_t)(BIT(0) | BIT(4) | BIT(6)); /* 0x51 */
Each of those lines is a read-modify-write: the chip reads the register, changes the bits, and writes the whole value back. It is three steps, not one. Volume 11 shows what happens when an interrupt lands in the middle of those three steps, and how to stop it mattering.
Writing the whole register when you meant to change one bit:
PORT = BIT(3); /* every other pin on that port is now 0 */
PORT |= BIT(3); /* only bit 3 changes */
The first line is right only when you genuinely want to set the whole register at once, which is rare outside initialisation.
port holds 0xA0. What does port |= BIT(1); leave in it?
Show the answer
Answer: A. BIT(1) is 0x02. ORing sets that bit and keeps the rest, so 0xA0 becomes 0xA2 - exactly what the program printed.
4.4 Masks and fields
Real registers hold several small numbers side by side. To read one, mask then shift. To write one, clear the field first, then drop the new value in.
Take a control register laid out like this:
| Bits | Field | Meaning |
|---|---|---|
| 1:0 | mode | 0 to 3 |
| 3:2 | gain | 0 to 3 |
| 11:4 | divisor | 0 to 255 |
| 12 | enable | on or off |
#define MODE_SHIFT 0u
#define MODE_MASK (0x3u << MODE_SHIFT)
#define GAIN_SHIFT 2u
#define GAIN_MASK (0x3u << GAIN_SHIFT)
#define DIVISOR_SHIFT 4u
#define DIVISOR_MASK (0xFFu << DIVISOR_SHIFT)
#define ENABLE_BIT (1u << 12)
static uint32_t field_get(uint32_t reg, uint32_t mask, uint32_t shift)
{
return (reg & mask) >> shift; /* keep the field, then slide it down */
}
static uint32_t field_set(uint32_t reg, uint32_t mask, uint32_t shift, uint32_t value)
{
reg &= ~mask; /* clear the old field */
reg |= (value << shift) & mask; /* drop the new one in */
return reg;
}
ctrl = 0x1686
mode = 2
gain = 1
divisor = 104
enabled = yes
after changing only the divisor: 0x1346
mode is still 2, gain is still 1
ORing 7 into a field holding 52 gives 55, not 7
That last line is the mistake to remember. OR can only ever set bits. Writing a new value into a field without clearing it first merges the two values. 52 is 0011 0100 and 7 is 0000 0111, so the OR gives 0011 0111, which is 55. Always clear, then set.
The & mask in field_set is a seat belt. If someone passes a value too big for the field, it is
trimmed instead of spilling into the neighbouring field and changing something else.
A field sits in bits 11:4. Which line reads its value?
Show the answer
Answer: B. Masking keeps the field but leaves it high up in the word, so it still has to slide down by the shift. Masking after shifting would need the mask to move as well, which is why mask-then-shift is the habit to learn.
4.5 Bit-fields in structs
C can declare struct members that are a few bits wide. They read beautifully, and the standard does not say where the compiler must put them - which is why drivers still use masks.
struct ctrl_bits {
uint32_t mode : 2;
uint32_t gain : 2;
uint32_t divisor : 8;
uint32_t enable : 1;
uint32_t : 19; /* the rest, unnamed */
};
c.mode = 2u; /* no masks, no shifts */
c.divisor = 104u;
sizeof(struct ctrl_bits) = 4 bytes
mode=2 gain=1 divisor=104 enable=1
the same struct, read as a word: 0x1686
On this compiler the struct lands on exactly the same word, 0x1686, as the hand-written masks. On another compiler it might not, and nothing in C promises it will.
- Which end the fields start from. Some compilers fill from the lowest bit, some from the highest.
- Whether fields may cross a storage boundary, and how padding is inserted.
- The type you may use. Plain
intbit-fields may be signed or unsigned. - How the compiler reads and writes them. A one-bit write may become a read-modify-write of the whole word, which is not always safe on a register.
None of that matters for a struct you invented. All of it matters for a struct that has to match a hardware register exactly.
Overflowing a field. Writing 5 into a 2-bit field keeps only the bottom two bits, giving 1. With warnings on, gcc refuses to build it at all:
error: conversion from 'unsigned int' to 'unsigned char:2'
changes value from '5' to '1'
That is a compile-time catch only for constants. A value arriving in a variable is trimmed at run time, silently.
Going deeper: where bit-fields are a good fit
Bit-fields shine in your own data structures, where packing matters and nothing outside the program sees the layout. Good examples are flags in a protocol state machine, small counters in a table, or a compact record in RAM. The rule of thumb in firmware is simple. Talking to hardware, or to another machine: masks and shifts. Packing your own data: bit-fields are fine, and much easier to read.
Why do most driver headers use masks and shifts rather than bit-fields for hardware registers?
Show the answer
Answer: C. Bit ordering, packing and padding are all implementation-defined. A struct that matches the register on one compiler may not on another, while a mask names the exact bits everywhere.
4.6 Classic bit puzzles
A handful of bit tricks come up again and again - in real firmware and in interviews. Each one is a single line once you have seen it.
0xB7 has 6 bits set
Kernighan's loop runs once per set bit, not once per bit
powers of two: 1 2 4 8 16
flags 0x00B0: lowest set bit is 0x10, and clearing it leaves 0x00A0
after the XOR swap: a = 0xA5, b = 0x3C
0xB2 reversed is 0x4D
round up 100 -> 128, 128 -> 128, 1000 -> 1024
7 is odd, 8 is even (tested with & 1)
The puzzles, and why each works
| Task | The line | Why it works |
|---|---|---|
| Is it odd? | v & 1u |
The bottom bit is the ones place |
| Multiply or divide by 2ⁿ | v << n, v >> n |
Each place is worth twice the one to its right |
| Is it a power of two? | v && !(v & (v - 1)) |
A power of two has one bit set; subtracting 1 flips it and everything below |
| Clear the lowest set bit | v & (v - 1) |
The same trick, kept rather than tested |
| Isolate the lowest set bit | v & (~v + 1) |
Also written v & -v on unsigned types |
| Count the set bits | loop v &= v - 1 |
Kernighan's method: one turn per set bit |
| Swap without a temporary | a ^= b; b ^= a; a ^= b; |
XOR undoes itself |
unsigned count_bits(uint32_t v)
{
unsigned n = 0;
while (v != 0u) {
v &= v - 1u; /* clears the lowest set bit */
n++;
}
return n;
}
A plain loop over 32 bits always takes 32 turns. This one takes as many turns as there are set bits, which for a register with two flags set is two.
Using the XOR swap in real code. It looks clever, it saves nothing on any modern compiler, and it silently destroys the value when both arguments are the same variable. Use a temporary. Know the trick for interviews; do not ship it.
Going deeper: rounding up to a power of two
The line v--; v |= v>>1; v |= v>>2; v |= v>>4; v |= v>>8; v |= v>>16; v++; fills every bit below
the highest set bit with 1s, then adds one, which carries all the way and leaves a single bit. It
is how buffer sizes get rounded up to something a mask can wrap. The program above rounds 100 to
128, leaves 128 alone, and rounds 1000 to 1024.
What does v & (v - 1) do?
Show the answer
Answer: B. Subtracting 1 turns the lowest set bit into 0 and sets every bit below it. ANDing the two keeps everything above and clears that bit - which is why the result is zero exactly when only one bit was set.
What you learned
- AND clears, OR sets, XOR flips, NOT inverts - and a mask marks the bits you mean.
1u << nbuilds the mask for bit n; shifting by the width of the type is undefined.- Set with
|=, clear with&= ~, toggle with^=, test with&and a comparison. - Every one of those is a read-modify-write, not a single step.
- To read a field: mask, then shift. To write one: clear the field, then OR the new value in.
- OR can only set bits, so writing a field without clearing it merges the old and new values.
- Bit-fields in structs are readable, but their layout is up to the compiler.
- The classic tricks:
v & 1,v & (v - 1),v & -v, and Kernighan's bit count.
Key words from this volume
Every word below has a plain-English entry in the glossary.
Practice
Write the four lines
A status register STATUS is 32 bits. Bit 7 is READY and bit 12 is ERROR. Write the code to set
READY, clear ERROR, flip READY, and test whether ERROR is set.
Show the solution
#define READY_BIT (1u << 7)
#define ERROR_BIT (1u << 12)
STATUS |= READY_BIT; /* set */
STATUS &= ~ERROR_BIT; /* clear */
STATUS ^= READY_BIT; /* toggle */
if ((STATUS & ERROR_BIT) != 0u) { /* test */
handle_error();
}
Two details worth keeping. The masks are named, so the code reads like the datasheet. And the test
is written != 0u rather than == 1, because STATUS & ERROR_BIT is 4096 when the bit is set,
not 1.
Extract the field
A 32-bit register holds a channel number in bits 19:16. Write get_channel and set_channel.
Show the solution
#define CHAN_SHIFT 16u
#define CHAN_MASK (0xFu << CHAN_SHIFT) /* four bits: 0 to 15 */
uint32_t get_channel(uint32_t reg)
{
return (reg & CHAN_MASK) >> CHAN_SHIFT;
}
uint32_t set_channel(uint32_t reg, uint32_t channel)
{
reg &= ~CHAN_MASK; /* clear first */
reg |= (channel << CHAN_SHIFT) & CHAN_MASK;
return reg;
}
Four bits hold 0 to 15. The & CHAN_MASK on the way in means that a caller passing 20 cannot
spill a stray bit into bit 20 and change a different setting.
Predict the output
What does this print?
uint8_t v = 0x2Cu; /* 0010 1100 */
v |= (1u << 1);
v &= (uint8_t)~(1u << 3);
v ^= (1u << 5);
printf("0x%02X\n", v);
Show the solution
0x06. Write the eight bits down at each step, which is the habit this exercise is really teaching:
| Step | Binary | Hex |
|---|---|---|
| start | 0010 1100 | 0x2C |
\|= BIT(1) sets bit 1 |
0010 1110 | 0x2E |
&= ~BIT(3) clears bit 3 |
0010 0110 | 0x26 |
^= BIT(5) flips bit 5, which was 1 |
0000 0110 | 0x06 |
The last step is the one people miss: XOR flips, so a bit that was already set comes back off.
Count without a loop over 32 bits
Write a function that returns the number of set bits in a uint32_t, running one turn per set bit
rather than 32 turns.
Show the solution
unsigned count_bits(uint32_t v)
{
unsigned n = 0;
while (v != 0u) {
v &= v - 1u;
n++;
}
return n;
}
Each turn clears the lowest set bit, so the loop ends as soon as the value reaches zero. For a register with two flags set it runs twice, whatever the width of the type.
Interviewers often follow up with "and how would you do it in constant time?" The answer is a lookup table of 256 entries, one per byte, adding up four lookups. That is what a real driver does when it needs this in a hot path.
Interview corner
Set a bit without touching the others
"Set bit 5 of a register without changing any other bit. Now clear it."
Show the solution
"reg |= (1u << 5); to set it, and reg &= ~(1u << 5); to clear it. OR only ever sets, and AND
with the inverted mask only ever clears, so every other bit is carried through untouched. I would name the mask after the datasheet field, rather than leaving a bare 5 in the code. I would
also remember that both lines are read-modify-writes. If an interrupt can touch the same register,
they need protecting."
Powers of two
"How do you test whether an unsigned value is a power of two, in one line?"
Show the solution
"(v != 0) && ((v & (v - 1)) == 0). A power of two has exactly one bit set. Subtracting one turns
that bit into a zero and sets every bit below it, so the AND comes out zero. The extra test rules
out zero itself, which would otherwise pass. The same v & (v - 1) is how you clear the lowest set
bit, and Kernighan's bit count is that line in a loop."
Next, Volume 05 moves from bits to structure: where variables live, how long they last, and what
static, const and volatile really do in firmware.