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
0or1. One piece is a bit. - 8 bits = 1 byte. An
intis 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, so7 >> 1is3, like integer division.1 << nbuilds 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): a1only where both numbers have a1.|(bitwise OR): a1where either number has a1.- 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
- Use
print_bitsto print any number from 0 to 255 in binary (try 200). - Write
count_on(n): how many bits are ON inn? (13 → 3, 255 → 8) - Check if a number is a power of 2 using
n & (n - 1). - 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
nofx? (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 & 1andn >>= 1, or Kernighan'sn &= n - 1until 0; gcc also has__builtin_popcount.) - What does
x << 1do?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
unsignedtypes? - 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 asO_RDONLY | O_CREAT.) - What is
~0for anunsigned char(255) and for anint(-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 << nbuilds a mask with only switch n on.- Check
s & M· sets |= M· clears &= ~M· toggles ^= M. - Never switch bits with
+or-: carries and borrows change other bits (253!). &&for conditions,&for bits;1 & 2is 0.==runs before&: always write(s & M) == M.- Shift only by 0 to width − 1, on unsigned values (
1u << 31). n & 1is 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.