Bitwise operations

Bitwise operators work on each bit separately.

Operator	Name	Bit rule	Example
`a & b`	AND	1 if both are 1	`1100 & 1010 = 1000`
`a \| b`	OR	1 if either is 1	`1100 \| 1010 = 1110`
`a ^ b`	XOR	1 if they differ	`1100 ^ 1010 = 0110`
`~a`	NOT	flips every bit	`~1100 = 0011` (in 4 bits)
`a << k`	left shift	moves bits left, filling with 0	`0011 << 2 = 1100`
`a >> k`	right shift	moves bits right	`1100 >> 2 = 0011`

Flags: many yes/no values in one number

#include <stdio.h>

#define READ 1    // bit 0
#define WRITE 2   // bit 1
#define EXEC 4    // bit 2

int main(void) {
    int perms = READ;
    perms |= WRITE;   // set
    printf("can write: %d\n", (perms & WRITE) != 0);
    printf("can run: %d\n", (perms & EXEC) != 0);
    perms &= ~READ;   // clear
    perms ^= EXEC;    // toggle
    printf("perms = %d\n", perms);
    return 0;
}

Open in compiler

Each permission is one bit: READ is bit 0 (value 1), WRITE bit 1 (2), EXEC bit 2 (4). One int holds all three:

set a flag with OR: perms |= WRITE;
test a flag with AND: if (perms & EXEC)
clear a flag with AND NOT: perms &= ~READ;
toggle a flag with XOR: perms ^= EXEC;

Operating systems store file permissions, and hardware its settings, exactly like this.

Shifts and tricks

#include <stdio.h>

int main(void) {
    int x = 7;
    printf("%d << 3 = %d, %d >> 1 = %d\n", x, x << 3, x, x >> 1);
    int n = 44;   // 101100
    int ones = 0;
    int m = n;
    while (m != 0) {
        m = m & (m - 1);   // clears the lowest 1 bit
        ones++;
    }
    printf("%d has %d bits set\n", n, ones);
    printf("64 is a power of two: %d\n", (64 & 63) == 0);
    printf("odd: %d %d\n", 9 & 1, 10 & 1);
    return 0;
}

Open in compiler

x << k is x × 2ᵏ, and x >> k is x ÷ 2ᵏ (for non-negative numbers). 1 << k is a number with only bit k set.
n & (n - 1) clears the lowest set bit, so a loop of it counts the 1 bits, and n & (n - 1) == 0 tests for a power of two.
x & 1 is 1 for odd numbers: the lowest bit says odd or even.

Common mistakes

Mixing up & (bitwise) with && (logical), or | with ||.
Forgetting brackets: x & 1 == 0 means x & (1 == 0), because == binds more tightly. Write (x & 1) == 0.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.

Flags: many yes/no values in one number

Shifts and tricks

Quick check

Practice problems for this lesson

Keep going