Chapter 8 · Lesson 1

Bitwise Operators

Every value in memory is ultimately a sequence of bits. Bitwise operators let you inspect and manipulate individual bits directly — a skill essential for systems programming, embedded development, and performance-critical code.

The Six Bitwise Operators

Operator	Name	Example (8-bit)
`&`	AND	`0b1010 & 0b1100 = 0b1000`
`	`	OR
`^`	XOR	`0b1010 ^ 0b1100 = 0b0110`
`~`	NOT (bitwise complement)	`~0b10110001 = 0b01001110`
`<<`	Left shift	`1 << 3 = 8`
`>>`	Right shift	`16 >> 2 = 4`

AND (&)

Each output bit is 1 only when both input bits are 1. Use it to clear or mask bits — keep only the bits you care about:

unsigned char nibble = value & 0x0F;  /* keep only lower 4 bits */

OR (|)

Each output bit is 1 when at least one input bit is 1. Use it to set bits:

value |= 0x01;  /* set bit 0 */

XOR (^)

Each output bit is 1 when the input bits differ. Use it to toggle bits or for the classic swap trick:

a ^= b; b ^= a; a ^= b;  /* swap a and b without a temp variable */

NOT (~)

Flips all bits. On a 32-bit int, ~0 gives 0xFFFFFFFF (all ones, which is -1 in two's complement). Be careful: ~ always operates on the promoted type.

Shift Operators

Left shift x << n is equivalent to multiplying by 2^n (fast!). Right shift x >> n divides by 2^n — but only reliably for unsigned values. For signed integers, right shift of a negative value is implementation-defined (most implementations arithmetic-shift, replicating the sign bit, but you cannot rely on this in portable code). Always use unsigned types with bitwise operations.

Practical Bit Tricks

Checking parity (is a number even or odd):

if (n & 1) { /* odd */ }

This is faster than n % 2 because it avoids division.

Testing power of 2: A power of 2 has exactly one bit set. n & (n - 1) clears the lowest set bit; the result is zero only for powers of 2 (and zero itself):

int is_power_of_two = (n > 0) && ((n & (n - 1)) == 0);

Counting set bits (popcount):

int count = 0;
unsigned v = n;
while (v) { count += (v & 1); v >>= 1; }

Modern compilers provide __builtin_popcount(n) as a single instruction on most hardware.

Code Examples

All Bitwise Operators Demonstratedc

#include <stdio.h>

/* Print an 8-bit value as binary string */
void print_bits8(unsigned char v) {
    for (int i = 7; i >= 0; i--)
        putchar((v >> i) & 1 ? '1' : '0');
}

int main(void) {
    unsigned char a = 0xAC;  /* 10101100 */
    unsigned char b = 0x6F;  /* 01101111 */

    printf("a         = "); print_bits8(a); printf("  (0x%02X = %u)\n", a, a);
    printf("b         = "); print_bits8(b); printf("  (0x%02X = %u)\n", b, b);
    printf("a & b     = "); print_bits8(a & b); printf("  (AND)\n");
    printf("a | b     = "); print_bits8(a | b); printf("  (OR)\n");
    printf("a ^ b     = "); print_bits8(a ^ b); printf("  (XOR)\n");
    printf("~a        = "); print_bits8(~a);    printf("  (NOT)\n");

    /* Shifts */
    unsigned char c = 0x0B;  /* 00001011 */
    printf("\nc         = "); print_bits8(c); printf("  (0x%02X)\n", c);
    printf("c << 2    = "); print_bits8((unsigned char)(c << 2)); printf("  (left shift 2, *4)\n");
    printf("c >> 1    = "); print_bits8(c >> 1); printf("  (right shift 1, /2)\n");

    /* Power-of-2 multiplication via shift */
    unsigned int x = 7;
    printf("\n7 << 3 = %u  (7 * 8 = 56)\n", x << 3);
    printf("56 >> 3 = %u  (56 / 8 = 7)\n", (x << 3) >> 3);

    return 0;
}

The print_bits8 function isolates each bit by shifting the value right and masking with 1. AND keeps only bits set in both operands, OR sets bits present in either, XOR produces 1 where bits differ. Shifts are equivalent to multiplication/division by powers of 2.

XOR Swap and Parity Checkc

#include <stdio.h>

/* XOR swap — swaps two integers without a temporary variable.
   WARNING: a and b must be different variables (not aliases)! */
void xor_swap(int *a, int *b) {
    if (a == b) return;   /* same address: do nothing */
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

/* Check parity: returns 1 if n is odd, 0 if even */
static inline int is_odd(unsigned int n) {
    return n & 1;
}

/* Count number of 1-bits (popcount) in an unsigned int */
int popcount(unsigned int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

int main(void) {
    /* XOR swap */
    int x = 42, y = 99;
    printf("Before swap: x=%d, y=%d\n", x, y);
    xor_swap(&x, &y);
    printf("After  swap: x=%d, y=%d\n", x, y);

    /* Parity */
    printf("\nParity check:\n");
    for (int i = 0; i <= 8; i++) {
        printf("  %d is %s\n", i, is_odd(i) ? "odd" : "even");
    }

    /* Popcount */
    printf("\nBit counts:\n");
    unsigned int vals[] = {0, 1, 7, 15, 255, 0xDEADBEEF};
    for (int i = 0; i < 6; i++) {
        printf("  popcount(0x%08X) = %d\n", vals[i], popcount(vals[i]));
    }

    return 0;
}

XOR swap works because A^B^B = A and A^A^B = B — XOR-ing a value with itself gives zero, which is the identity for XOR. The alias guard (a == b) is critical: XOR-swapping a variable with itself zeroes it out. Popcount shifts through each bit and adds it.

Power-of-2 Check and Bit Manipulationc

#include <stdio.h>

/* Is n a power of 2? Works because powers of 2 have exactly one bit set.
   n & (n-1) clears the lowest set bit. Result is 0 iff exactly one bit. */
static inline int is_power_of_two(unsigned int n) {
    return (n > 0) && ((n & (n - 1)) == 0);
}

/* Round n up to the next power of 2 (useful for buffer sizing) */
unsigned int next_power_of_two(unsigned int n) {
    if (n == 0) return 1;
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n + 1;
}

/* Extract the lowest set bit of n */
static inline unsigned int lowest_set_bit(unsigned int n) {
    return n & (~n + 1);  /* equivalent to n & (-n) for two's complement */
}

/* Clear the lowest set bit */
static inline unsigned int clear_lowest_bit(unsigned int n) {
    return n & (n - 1);
}

int main(void) {
    printf("Power-of-2 test:\n");
    unsigned int tests[] = {0, 1, 2, 3, 4, 15, 16, 17, 1024};
    for (int i = 0; i < 9; i++) {
        printf("  %5u : %s\n", tests[i], is_power_of_two(tests[i]) ? "YES" : "NO");
    }

    printf("\nNext power of 2:\n");
    unsigned int sizes[] = {1, 5, 8, 9, 100, 1000};
    for (int i = 0; i < 6; i++) {
        printf("  %4u -> %u\n", sizes[i], next_power_of_two(sizes[i]));
    }

    printf("\nLowest set bit and clear:\n");
    unsigned int v = 0b10110100;
    printf("  v              = %08X\n", v);
    printf("  lowest_set_bit = %08X\n", lowest_set_bit(v));
    printf("  clear_lowest   = %08X\n", clear_lowest_bit(v));

    return 0;
}

The power-of-2 trick n & (n-1) == 0 works because subtracting 1 from a power of 2 flips all lower bits. next_power_of_two uses a filling trick: OR-ing with progressively larger right shifts propagates the highest set bit downward, then adding 1 carries everything up. These patterns appear constantly in allocators and hash table implementations.

Quick Quiz

1. What is the result of 0b1011 & 0b1101 in binary?

2. What does the expression (n & (n - 1)) == 0 test for (given n > 0)?

3. Why should bitwise operations generally be performed on unsigned integer types?

4. What is the value of ~0 on a system with 32-bit int?

Was this lesson helpful?