SyntaxPilot
Courses/C Programming/Lesson 18

C Programming · Lesson 18 of 30 · 14 min

Bitwise operators

queued

These are the notes for C episode 18. So far every variable held a whole number. Today you go one level deeper, inside the number, and switch its tiny pieces on and off one at a time. It starts with a phone's quick-settings panel: eight on/off switches stored as eight int variables waste 32 bytes. You fix it by learning bits, bytes and binary, packing all eight switches into one byte, and inventing the operators that check, set, clear and toggle one switch: &, |, & ~ and ^, plus the shifts << and >>. Then come the three traps that give wrong answers with no error (& vs &&, missing brackets, shifting too far), a one-bit odd/even test, and a mini project: a settings manager with a print_bits function. Every example below was compiled with gcc -O2 -Wno-unused-result main.c -o main -lm (gcc 13, the same command as the SyntaxPilot compiler) and run as shown.

The problem: 8 switches, 32 bytes

Pull down the quick-settings panel on any phone: Wi-Fi, Bluetooth, GPS, flight mode, dark mode, silent, auto-rotate, battery saver. Eight switches, and each one is only on or off. Now imagine the app that saves these settings for one million users. The obvious way is one int per switch:

#include <stdio.h>

int main() {
    int wifi = 1, bt = 0, gps = 1, flight = 0;
    int dark = 1, silent = 0, rotate = 1, saver = 0;

    printf("8 settings use %zu bytes\n",
           8 * sizeof(int));
    printf("Wi-Fi: %d, GPS: %d\n", wifi, gps);
    return 0;
}

Output:

8 settings use 32 bytes
Wi-Fi: 1, GPS: 1

32 bytes for eight yes/no answers; for a million users, 32 million bytes just for switches. It is clumsy too: passing the settings to a function means eight arguments, and a ninth setting changes every function.

Why it is wasteful

  • Inside the computer everything is stored as tiny pieces that are either 0 or 1. One piece is a bit.
  • 8 bits = 1 byte. An int is 4 bytes = 32 bits.
  • A yes/no needs only one bit, so 31 of every 32 bits do nothing.
  • Idea: give each switch one bit, and fit all eight switches inside a single byte.

Bits, bytes and binary

Real-life example: the switchboard in your room.

On the wall In C
One switch: on or off One bit: 1 or 0
A board of 8 switches in a row One byte = 8 bits (unsigned char is exactly 1 byte)
Switches numbered from the right, 0 to 7 bit 0 (rightmost) ... bit 7 (leftmost)

unsigned means "no minus sign": an unsigned char holds 0 to 255. (A plain char may be signed, -128 to 127.)

Binary: counting with only 0 and 1

In everyday (decimal) numbers each place is worth 10 times the place on its right: ones, tens, hundreds. In binary each place is worth 2 times:

bit:     7   6   5   4   3  2  1  0
value: 128  64  32  16   8  4  2  1

To read a byte, add the values of the places that are 1:

Binary Sum Decimal
0000 0101 4 + 1 5
0000 1101 8 + 4 + 1 13
1100 1000 128 + 64 + 8 200
1111 1111 everything 255 (all ON)

Bit n on its own is worth 2 to the power n. Bit 2 alone is 4, bit 3 alone is 8.

Shifts: << and >>

Real-life example: add a zero, get ten times. Write a zero after Rs 50 and you get Rs 500: every digit moved one place left. In binary, moving every bit one place left makes the number 2 times bigger.

Money Binary Meaning
Rs 50 → Rs 500 (add a zero) x << 1 bits move left: x × 2
Rs 500 → Rs 50 (rub out the zero) x >> 1 bits move right: x / 2 (rounded down)
1, 10, 100, 1000 1 << n a single 1 at position n: only switch n ON
#include <stdio.h>

int main() {
    int x = 5;
    printf("5 << 1 = %d\n", x << 1);
    printf("5 << 3 = %d\n", x << 3);
    printf("40 >> 2 = %d\n", 40 >> 2);
    printf("7 >> 1 = %d\n", 7 >> 1);

    for (int n = 0; n < 4; n++)
        printf("1 << %d = %d\n", n, 1 << n);
    return 0;
}

Output:

5 << 1 = 10
5 << 3 = 40
40 >> 2 = 10
7 >> 1 = 3
1 << 0 = 1
1 << 1 = 2
1 << 2 = 4
1 << 3 = 8
  • x << n = x × 2ⁿ (as long as nothing falls off the left end).
  • x >> n = x / 2ⁿ, rounded down: the bits that fall off the right end are lost, so 7 >> 1 is 3, like integer division.
  • 1 << n builds a number with only bit n on. That is how we name each switch.

Masks and flags: check with &, set with |

Real-life example: masking tape. Before painting a wall, painters cover what must not be touched with masking tape; only the gaps get paint.

Painting a wall In C
Masking tape covers what you must not touch A mask: a number with only the bits you care about, e.g. GPS = 1 << 2
Peek through one gap s & GPS: non-zero only if the GPS bit is ON (check)
Flip one switch up, others unchanged s = s | GPS: turns GPS ON (set)
  • & (bitwise AND): a 1 only where both numbers have a 1.
  • | (bitwise OR): a 1 where either number has a 1.
  • A single on/off value stored as one bit is called a flag.
#include <stdio.h>
#define WIFI (1 << 0)
#define BT   (1 << 1)
#define GPS  (1 << 2)

int main() {
    unsigned char s = 0;     // all switches off
    s = s | WIFI;            // Wi-Fi on
    s = s | GPS;             // GPS on
    printf("s = %d, size = %zu byte\n", s, sizeof s);

    if (s & GPS) printf("GPS is ON\n");
    if (s & BT)  printf("BT is ON\n");
    return 0;
}

Output:

s = 5, size = 1 byte
GPS is ON

s is 0000 0101 = 5: bit 0 (Wi-Fi) and bit 2 (GPS). Bluetooth's bit is 0, so its line is not printed. Eight switches now fit in 1 byte instead of 32; a million users need 1 million bytes, not 32 million. The masks use #define from episode 16, with brackets around (1 << 0) so they are safe inside bigger expressions.

Clearing a bit: why subtracting fails, and & ~

The obvious way to turn GPS off: GPS is worth 4, so subtract 4.

#include <stdio.h>
#define WIFI (1 << 0)
#define GPS  (1 << 2)

int main() {
    unsigned char s = WIFI | GPS;   // 5
    s = s - GPS;     // GPS off
    printf("s = %d\n", s);
    s = s - GPS;     // pressed "off" again
    printf("s = %d\n", s);
    if (s & GPS) printf("GPS is ON again?!\n");
    return 0;
}

Output:

s = 1
s = 253
GPS is ON again?!

The first subtraction works. The second one does 1 - 4. An unsigned char cannot be negative, so it wraps around from the top (like an odometer rolling back past zero) to 253 = 1111 1101: seven switches on, including GPS. Subtraction is arithmetic; it borrows from other bits.

The fix: ~ (bitwise NOT) flips every bit. ~GPS is 1111 1011: all ones except bit 2. AND-ing with it keeps every bit except GPS, which is forced to 0:

#include <stdio.h>
#define WIFI (1 << 0)
#define GPS  (1 << 2)

int main() {
    unsigned char s = WIFI | GPS;   // 5
    s = s & ~GPS;     // GPS off
    printf("s = %d\n", s);
    s = s & ~GPS;     // pressed "off" again
    printf("s = %d\n", s);
    if (s & GPS) printf("GPS is ON again?!\n");
    return 0;
}

Output:

s = 1
s = 1

Clearing a bit that is already 0 changes nothing. This is called clearing a bit.

Toggling a bit with ^

Real-life example: the TV remote's power button. Press: on. Press again: off. You don't need to know what it was; you just flip it.

^ (bitwise XOR, "exclusive or") gives 1 where the two bits are different. s ^ SILENT flips the silent bit and leaves the rest alone. Flipping is called toggling.

#include <stdio.h>
#define SILENT (1 << 3)

int main() {
    unsigned char s = 0;
    for (int press = 1; press <= 4; press++) {
        s = s ^ SILENT;          // flip
        printf("press %d: %s\n", press,
               (s & SILENT) ? "silent" : "ringing");
    }
    return 0;
}

Output:

press 1: silent
press 2: ringing
press 3: silent
press 4: ringing

The four bit operators side by side

  12 = 1100       12 = 1100       12 = 1100
& 10 = 1010     | 10 = 1010     ^ 10 = 1010
   8 = 1000       14 = 1110        6 = 0110
Operator Name Rule per bit Job with a mask Short form
& AND 1 if both are 1 check: s & GPS s &= m;
| OR 1 if either is 1 set: s | GPS s |= m;
& ~ AND NOT keep all, force mask bits to 0 clear: s & ~GPS s &= ~m;
^ XOR 1 if they differ toggle: s ^ GPS s ^= m;
~ NOT flips every bit builds the clear mask —
<< / >> shifts move all bits left / right build masks: 1 << n s <<= n; / s >>= n;

The short forms work like += from episode 3: s |= GPS; means s = s | GPS;.

Trap 1: & instead of &&

#include <stdio.h>

int main() {
    int wifi = 1, bt = 2;    // both non-zero: both ON

    if (wifi && bt) printf("&&: both are ON\n");
    if (wifi & bt)  printf("&:  both are ON\n");

    printf("wifi && bt = %d\n", wifi && bt);
    printf("wifi &  bt = %d\n", wifi & bt);
    return 0;
}

Output:

&&: both are ON
wifi && bt = 1
wifi &  bt = 0

&& (logical AND) asks "are both true (non-zero)?". & (bitwise AND) compares bits: 01 & 10 = 00 = 0, because 1 and 2 share no bit. && for conditions, & for flags. The same goes for || vs |.

Trap 2: precedence, s & GPS == GPS

#include <stdio.h>
#define WIFI (1 << 0)
#define GPS  (1 << 2)

int main() {
    unsigned char s = GPS;    // only GPS is on

    if (s & GPS == GPS) printf("GPS is ON\n");
    else                printf("GPS is OFF?!\n");

    if ((s & GPS) == GPS) printf("GPS is ON\n");
    return 0;
}

Output:

GPS is OFF?!
GPS is ON

== runs before &. So s & GPS == GPS is s & (GPS == GPS) = s & 1, which checks bit 0, Wi-Fi, not GPS. With -Wall gcc warns:

main.c:8:11: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
    8 |     if (s & GPS == GPS) printf("GPS is ON\n");
      |           ^

Always put brackets around a bit test: (s & GPS) == GPS, or simply if (s & GPS).

Trap 3: shifting too far

#include <stdio.h>

int main() {
    unsigned int flags = 1 << 32;
    printf("flags = %u\n", flags);
    return 0;
}

Output:

main.c: In function 'main':
main.c:4:28: warning: left shift count >= width of type [-Wshift-count-overflow]
    4 |     unsigned int flags = 1 << 32;
      |                            ^~
flags = 0

A 32-bit unsigned int has bits 0 to 31; there is no bit 32. Shifting by the width of the type or more is undefined behaviour: this run printed 0, but C promises nothing. The top bit is bit 31, and shift an unsigned 1 (1u) so it does not land in an int's sign bit:

#include <stdio.h>

int main() {
    unsigned int top = 1u << 31;
    printf("top = %u\n", top);
    return 0;
}

Output:

top = 2147483648

Rule: shift amounts must be from 0 to (number of bits − 1), and do bit work on unsigned types. Shifting a negative number left, or 1 << 31 on a plain int, is also undefined behaviour.

Bonus: odd or even with n & 1

Bit 0 is the only odd place value (1), so every odd number ends in 1 in binary:

#include <stdio.h>

int main() {
    int nums[] = {7, 10, 13, 24};
    for (int i = 0; i < 4; i++) {
        int n = nums[i];
        printf("%2d -> %s\n", n, (n & 1) ? "odd" : "even");
    }
    return 0;
}

Output:

 7 -> odd
10 -> even
13 -> odd
24 -> even

Same answer as n % 2 for non-negative numbers, with a single bit check.

Common mistakes (and the real gcc messages)

Mistake What you see Why Fix
s = s - GPS; to switch off No error: s becomes 253, GPS ON again Subtraction borrows from other bits s &= ~GPS;
s = s + GPS; to switch on No error: if GPS was already on, the carry turns other bits on Addition carries into other bits s |= GPS;
if (wifi & bt) for logic No error: 1 & 2 is 0 & compares bits if (wifi && bt)
if (s & GPS == GPS) warning: suggest parentheses around comparison in operand of '&' [-Wparentheses] (with -Wall) == runs before & if ((s & GPS) == GPS)
1 << 32 warning: left shift count >= width of type [-Wshift-count-overflow] No bit 32 in 32 bits 1u << 31 at most
#define GPS 1 << 2 (no brackets) No error: s & GPS mixes with other operators wrongly, e.g. GPS * 2 = 1 << 4 = 16 Macros are pasted as text (episode 16) #define GPS (1 << 2)
Using ^ for "power" No error: 2 ^ 3 is 1 ^ is XOR, not power 1 << 3, or pow(2, 3)

Mini project: a settings manager with print_bits

#include <stdio.h>
#define WIFI   (1 << 0)
#define BT     (1 << 1)
#define GPS    (1 << 2)
#define SILENT (1 << 3)

void print_bits(unsigned char s) {
    for (int i = 7; i >= 0; i--)
        printf("%d", (s >> i) & 1);
    printf("\n");
}

int main() {
    unsigned char s = 0;
    s |= WIFI | GPS;   print_bits(s);
    s ^= SILENT;       print_bits(s);
    s &= ~WIFI;        print_bits(s);
    printf("GPS: %s\n", (s & GPS) ? "ON" : "OFF");
    printf("Wi-Fi: %s\n", (s & WIFI) ? "ON" : "OFF");
    return 0;
}

Output:

00000101
00001101
00001100
GPS: ON
Wi-Fi: OFF

How print_bits works: for each position i from 7 down to 0, s >> i moves bit i to position 0, and & 1 keeps only that bit, giving 0 or 1. WIFI | GPS builds a mask with two bits at once, so one |= turns on two switches.

Try it: add #define DARK (1 << 4), turn it on, and toggle Bluetooth twice; check that print_bits shows what you expect.

Practice

  1. Use print_bits to print any number from 0 to 255 in binary (try 200).
  2. Write count_on(n): how many bits are ON in n? (13 → 3, 255 → 8)
  3. Check if a number is a power of 2 using n & (n - 1).
  4. Store 5 hostel room permissions (entry, Wi-Fi, laundry, mess, guest) in one byte. Start with entry, Wi-Fi and mess; block Wi-Fi; allow a guest; print the bits and check laundry and guest.
Solutions

All four in one program (verified):

#include <stdio.h>
#define ENTRY   (1 << 0)
#define WIFI    (1 << 1)
#define LAUNDRY (1 << 2)
#define MESS    (1 << 3)
#define GUEST   (1 << 4)

void print_bits(unsigned char s) {
    for (int i = 7; i >= 0; i--)
        printf("%d", (s >> i) & 1);
    printf("\n");
}

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

int is_power_of_2(unsigned int n) {
    return n != 0 && (n & (n - 1)) == 0;
}

int main() {
    print_bits(200);
    printf("bits ON in 13: %d\n", count_on(13));
    printf("bits ON in 255: %d\n", count_on(255));
    for (unsigned int n = 6; n <= 8; n++)
        printf("%u power of 2? %s\n", n, is_power_of_2(n) ? "yes" : "no");

    unsigned char room = ENTRY | WIFI | MESS;
    room &= ~WIFI;            // Wi-Fi blocked for late fees
    room |= GUEST;            // guest allowed this weekend
    print_bits(room);
    printf("Laundry: %s\n", (room & LAUNDRY) ? "yes" : "no");
    printf("Guest:   %s\n", (room & GUEST) ? "yes" : "no");
    return 0;
}

Output:

11001000
bits ON in 13: 3
bits ON in 255: 8
6 power of 2? no
7 power of 2? no
8 power of 2? yes
00011001
Laundry: no
Guest:   yes

Why n & (n - 1) works: a power of 2 has exactly one bit on (1000). Subtracting 1 turns that bit off and all the bits below it on (0111), so the AND is 0. Any other number keeps at least one bit. The n != 0 check is needed because 0 & (0 - 1) is also 0.

Quick quiz

What does this print?

printf("%d", 12 & 10);
  • A. 8
  • B. 14
  • C. 6
  • D. 22
Answer

A: 8. 12 is 1100, 10 is 1010. Only bit 3 is on in both, and bit 3 is worth 8. 14 would be 12 | 10, 6 would be 12 ^ 10, and 22 is 12 + 10. (Verified output: 8.)

Interview questions

  • What is the difference between & and &&? Between | and ||? (Bitwise vs logical; && and || also short-circuit: they skip the right side when the answer is already known.)
  • How do you set, clear, toggle and check bit n of x? (x |= 1u << n, x &= ~(1u << n), x ^= 1u << n, (x >> n) & 1)
  • How do you check if a number is odd using bits? (n & 1)
  • How do you check if a number is a power of 2? (n && !(n & (n - 1)))
  • How do you count the set bits of a number? (Loop with n & 1 and n >>= 1, or Kernighan's n &= n - 1 until 0; gcc also has __builtin_popcount.)
  • What does x << 1 do? x >> 1? When is shifting undefined behaviour? (Shift count negative or ≥ the width; left-shifting a negative or overflowing a signed value.)
  • Why do bit manipulations usually use unsigned types?
  • Swap two variables with XOR without a third variable (a ^= b; b ^= a; a ^= b;). Why is it rarely a good idea in real code?
  • What is a bit mask? Where are flags used in real systems? (File permissions like rwx, hardware registers, network packet headers, open() flags such as O_RDONLY | O_CREAT.)
  • What is ~0 for an unsigned char (255) and for an int (-1)?

Glossary

Term Meaning Example
Bit The smallest piece of data: a single 0 or 1 One switch on the board
Byte A group of 8 bits unsigned char is 1 byte
Binary Writing numbers with only 0 and 1, each place worth 2× the one on its right 1101 = 13
Place value What a position is worth: 1, 2, 4, 8, 16, 32, 64, 128 Bit 3 is worth 8
Bit position Which bit, counted from 0 at the right Bit 0 = rightmost
unsigned A type with no minus sign; all bits hold the value unsigned char: 0 to 255
Bitwise operator An operator that works on each bit separately &, |, ^, ~, <<, >>
Bitwise AND & 1 only where both bits are 1 12 & 10 = 8
Bitwise OR | 1 where either bit is 1 12 | 10 = 14
Bitwise XOR ^ 1 where the two bits differ 12 ^ 10 = 6
Bitwise NOT ~ Flips every bit ~GPS = 1111 1011 (as a byte)
Left shift << Moves all bits left; each step doubles 5 << 1 = 10
Right shift >> Moves all bits right; each step halves (rounded down) 7 >> 1 = 3
Mask A number with only the bits you care about switched on GPS = (1 << 2) = 4
Flag One on/off setting stored as one bit The GPS bit
Set a bit Make it 1, leave the others s |= GPS;
Clear a bit Make it 0, leave the others s &= ~GPS;
Toggle a bit Flip it (1 → 0, 0 → 1) s ^= SILENT;
Check a bit Test whether it is 1 if (s & GPS)
Wrap-around An unsigned value going below 0 (or above the max) restarts from the other end 1 - 4 in an unsigned char = 253
Precedence Which operator runs first when there are no brackets == runs before &
Undefined behaviour Code whose result the C standard does not define; anything can happen 1 << 32
Logical AND && True if both sides are non-zero (whole values, not bits) 1 && 2 = 1

Summary

  • Eight ints for eight on/off settings waste 32 bytes; one bit per switch fits all eight in one byte.
  • Binary: each place is worth 2× the one on its right (1, 2, 4, ..., 128); bit n alone is 2ⁿ.
  • << doubles, >> halves; 1 << n builds a mask with only switch n on.
  • Check s & M · set s |= M · clear s &= ~M · toggle s ^= M.
  • Never switch bits with + or -: carries and borrows change other bits (253!).
  • && for conditions, & for bits; 1 & 2 is 0.
  • == runs before &: always write (s & M) == M.
  • Shift only by 0 to width − 1, on unsigned values (1u << 31).
  • n & 1 is 1 for odd numbers; n & (n - 1) is 0 for powers of 2.

Next episode: Command-line arguments: argc and argv, giving your program its input right when you start it.