Bit Manipulation & Operators
Every value in a C program is, at its physical level, a pattern of bits — voltages on silicon, magnetic states on disk, pulses of light through fiber. Most C programmers operate at a level of abstraction where int x = 5 is a mathematical value, not a bit pattern. But when you write device drivers, implement cryptographic algorithms, optimize network protocols, or squeeze performance from embedded processors, the abstraction leaks. Bit manipulation is the craft of reaching through that abstraction to control individual bits directly — and in C, you have some of the sharpest bit-level tools of any high-level language.
1. The Bitwise Operators: A Complete Reference
Before we write code, you must be able to visualize bit patterns in your head. Let's use an 8-bit unsigned char as our canvas. Assume a = 0b01101001 (105 decimal) and b = 0b01011100 (92 decimal).
OPERATOR NAME EXAMPLE (a=01101001, b=01011100) TRUTH TABLE PER BIT
--------- ------ --------------------------------- -------------------
& AND a & b = 01001000 (72) 1&1=1, all others 0
| OR a | b = 01111101 (125) 0|0=0, all others 1
^ XOR a ^ b = 00110101 (53) bits differ -> 1
~ NOT ~a = 10010110 (150) flip every bit
<< LEFT SHIFT a << 2 = 10100100 (164) shift left, pad 0
>> RIGHT SHIFT a >> 2 = 00011010 (26) shift right, pad?
ASCII DIAGRAM: a = 0 1 1 0 1 0 0 1, b = 0 1 0 1 1 1 0 0
AND: 0 1 0 0 1 0 0 0 (only bits where both are 1 survive)
OR: 0 1 1 1 1 1 0 1 (any bit where either is 1 becomes 1)
XOR: 0 0 1 1 0 1 0 1 (bits where a and b differ become 1)
1.1 Right Shift: Arithmetic v
s. Logical — The Sign Bit TrapLeft shift (<<
>>) has two variants, and which one you get depends on whether the type is signed:
- Logical right shift: fills vacated bits with
0. Used forunsigned types. - Arithmetic right shift: fills vacated bits with a copy of the sign bit (most significant bit). Used for
signedtypes on most implementations. This preserves the sign during division by powers of two.
/* The right-shift sign trap — ALWAYS use unsigned for bit twiddling */
#include <stdio.h>
int main() {
signed char s = -16; /* binary (8-bit): 11110000 */
unsigned char u = 240; /* binary (8-bit): 11110000 — same bits! */
printf("signed -16 >> 2 = %d\n", s >> 2); /* -4: 11111100 (arithmetic) */
printf("unsigned 240 >> 2 = %u\n", u >> 2); /* 60: 00111100 (logical) */
return 0;
}
The iron rule of bit manipulation: always use unsigned integer types. Signed right shifts are implementation-defined, and signed overflow during shifts is undefined behavior. unsigned types have well-defined wrap-around semantics.
2. The Four Fundamental Bitmask Operations
A bitmask is an integer where specific bit positions are 1 and the rest are 0. By combining masks with bitwise operators, you can read, set, clear, or toggle individual bits without affecting their neighbors. This is the foundation of all bit-level programming.
(1 << n)
#define BIT(n) (1U << (n)) /* always use unsigned 1: 1U */
/* BIT(0) = 00000001
BIT(3) = 00001000
BIT(7) = 10000000 */
2
.2 Set a Bit (OR with mask)unsigned char flags = 0; /* 00000000 */
flags |= BIT(2); /* 00000100 — bit 2 is now 1 */
flags |= BIT(5); /* 00100100 — bits 2 and 5 are both 1 */
2.3 Clear a Bit (AND with inverted mask)
flags &= ~BIT(2); /* 00100000 — bit 2 cleared, bit 5 untouched */
/* ~BIT(2) = ~(00000100) = 11111011
AND with flags: 00100100
& 11111011
= 00100000 */
2.4 Toggle
a Bit (XOR with mask)flags ^= BIT(5); /* 00000000 — bit 5 toggled from 1 to 0 */
flags ^= BIT(5); /* 00100000 — toggle again: back to 1 */
/* XOR is its own inverse: (x ^ mask) ^ mask == x */
2.5 Test a Bit (
AND with mask, check non-zero)if (flags & BIT(5)) {
printf("Bit 5 is set\n");
}
/* BIT(5) = 00100000; flags & BIT(5) is either 0 or BIT(5).
Any non-zero value is truthy in C, so the if triggers when bit 5 is 1. */
3. Real-World Bitmasking: A Permission System
#include <stdio.h>
/* Define permission bits — each is a distinct power of two */
#define PERM_READ (1U << 0) /* 00000001 = 1 */
#define PERM_WRITE (1U << 1) /* 00000010 = 2 */
#define PERM_EXEC (1U << 2) /* 00000100 = 4 */
#define PERM_DELETE (1U << 3) /* 00001000 = 8 */
#define PERM_ADMIN (1U << 4) /* 00010000 = 16 */
void print_perms(unsigned char perms) {
printf("Permissions [");
if (perms & PERM_READ) printf(" READ");
if (perms & PERM_WRITE) printf(" WRITE");
if (perms & PERM_EXEC) printf(" EXEC");
if (perms & PERM_DELETE) printf(" DELETE");
if (perms & PERM_ADMIN) printf(" ADMIN");
printf(" ] (raw: 0x%02X)\n", perms);
}
int main() {
/* A typical user: read + write + execute */
unsigned char user = PERM_READ | PERM_WRITE | PERM_EXEC;
print_perms(user);
/* Grant admin (accumulate): */
user |= PERM_ADMIN;
print_perms(user);
/* Revoke write: */
user &= ~PERM_WRITE;
print_perms(user);
/* Check a specific permission: */
if ((user & PERM_DELETE) == 0) {
printf("User cannot delete files.\n");
}
return 0;
}
This pattern stores 8 independent boolean flags in a single byte. Compare that to 8 separate int variables consuming 32 bytes. In a kernel process table with thousands of entries, the memory savings are profound.
4. Advanced Techniques
4.1 Isolating the Lowest Set Bit: x & -x
Two's complement negation (-x = ~x + 1) produces a fascinating property: x & -x isolates the least significant 1 bit of x.
unsigned int x = 0b01011000; /* 88 in decimal */
unsigned int lsb = x & -x; /* 0b00001000 = 8 — the rightmost 1 bit */
/* How it works:
x = 01011000
-x = 10101000 (two's complement: flip bits then add 1)
& = 00001000 ← only the rightmost 1 survives! */
This is the core operation behind Fenwick trees (Binary Indexed Trees), used in competitive programming and database indexing for O(log n) prefix sum queries with point updates.
4.2 Clearing the Lowest Set Bit: x & (x - 1)
unsigned int x = 0b01011000; /* 88 */
unsigned int y = x & (x - 1); /* 0b01010000 = 80 — rightmost 1 cleared */
This is the basis of Brian Kernighan's algorithm for counting set bits (population count):
int popcount(unsigned int x) {
int count = 0;
while (x) {
x &= x - 1; /* clear the lowest set bit */
count++;
}
return count;
}
/* Every iteration removes exactly one set bit. O(number of 1-bits).
For sparse bit patterns, this is faster than testing all 32/64 bits. */
4.3 Swapping Without a Temporary: XOR Swap
void xor_swap(int *a, int *b) {
if (a == b) return; /* CRITICAL: prevents zeroing out when aliased */
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
/* Trace with a=5 (0101), b=3 (0011):
a ^= b => a = 0110, b = 0011
b ^= a => a = 0110, b = 0101 (5 — original a!)
a ^= b => a = 0011 (3 — original b!), b = 0101 */
Caveat: XOR swap is a clever trick but rarely faster than a temp-variable swap on modern compilers (which optimize both to register operations). Its real value is in constrained environments where you cannot spare even a single extra register — think 8-bit microcontrollers with 32 bytes of RAM.
5. Pitfalls That Even Experts Hit
5.1 Operator Precedence Surprises
Bitwise operators have lower precedence than comparison operators. This is a constant source of bugs:
/* WRONG: == binds tighter than & */
if (flags & BIT(3) == 0) { /* parsed as: flags & (BIT(3) == 0)
which is: flags & 1 — NOT what you meant */
/* RIGHT: use parentheses */
if ((flags & BIT(3)) == 0) { /* this is what you actually want */
5.2 Shift by >= Type Width is Undefined
uint32_t x = 1;
x <<= 32; /* UNDEFINED BEHAVIOR on 32-bit int — shift amount >= bit width */
x <<= 31; /* OK: defined behavior */
5.3 Sign Extension When Promoting char to int
unsigned char a = 0xFF; /* 255 */
int b = ~a; /* surprising! ~a promotes to int first:
a becomes signed int 255 (0x000000FF),
~0x000000FF = 0xFFFFFF00 = -256
NOT 0x00000000 as you might expect */
unsigned char c = ~a; /* c = 0x00 (0) — truncation after int promotion */
6. Key Takeaways
- Always use
unsignedtypes for bit manipulation. Signed right shifts are implementation-defined; signed overflow during shifts is undefined. - The four fundamental operations — set (
|=), clear (&= ~), toggle (^=), test (&) — are the building blocks of every bitmasking system. - Use
(1U << n)to create single-bit masks. TheUsuffix ensures unsigned arithmetic and prevents undefined shifts. - Bitwise operators have lower precedence than
==,!=,<,>. Always parenthesize conditions:(flags & MASK) == 0. - Bit-level tricks (
x & -x,x & (x-1)) are beautiful but prioritize clarity over cleverness in production code. Add explanatory comments.
7. Practice Exercises
Exercise 1: Bit Counter
Write a function int count_set_bits(unsigned int n) that returns the number of 1 bits in n. Implement it two ways: (a) using Brian Kernighan's algorithm, (b) using a lookup table for 8-bit chunks. Compare their performance on a loop of 10 million calls.
int count_set_bits_kernighan(unsigned int n);
int count_set_bits_lookup(unsigned int n);
Hint for lookup: Precompute bitcount[256] where bitcount[i] = number of set bits in byte i. Then sum the counts for each byte of the integer.
Exercise 2: Endianness Detector
Write a program that determines whether the machine it runs on is little-endian or big-endian using only bitwise operations and a union or pointer cast. Print the result.
/* Little-endian: least significant byte at lowest address
Big-endian: most significant byte at lowest address
Example: 0x12345678 stored as:
Little-endian memory: 78 56 34 12
Big-endian memory: 12 34 56 78 */
int is_little_endian(void);
Hint: Store 0x0001 in a 16-bit integer and inspect the first byte. If it's 0x01, you're little-endian.
Exercise 3: RGB Color Packer
Write a macro or function that packs three 8-bit R, G, B values into a single 32-bit integer, and corresponding extractor macros. The packed format should be: bits 0–7 = Blue, bits 8–15 = Green, bits 16–23 = Red, bits 24–31 = 0 (or Alpha).
#define PACK_RGB(r, g, b) /* TODO */
#define UNPACK_R(rgb) /* TODO */
#define UNPACK_G(rgb) /* TODO */
#define UNPACK_B(rgb) /* TODO */
Hint: Pack with ((r & 0xFF) << 16) and OR. Unpack with right shift and mask.
Exercise 4: Power of Two Check
A number is a power of two if it has exactly one bit set. Write a one-liner expression that returns non-zero if x is a power of two, and zero otherwise. Handle the edge case x == 0 (which is not a power of two, but 0 & -0 is... tricky).
int is_power_of_two(unsigned int x) {
return /* TODO: single expression */;
}
Hint: Combine two properties: (1) x != 0, and (2) (x & (x - 1)) == 0.