These are the notes for C Coding Questions, episode 25, placement practice for people who finished the SyntaxPilot C course. Bit manipulation questions: a warm-up on odd or even with &, then checking, setting, clearing and toggling the k-th bit, swapping two numbers without a temporary variable (and the trap that zeroes a value), and the single number that appears once among pairs.
Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.
Every program was compiled with gcc -Wall -O2 -Wno-unused-result main.c -o main -lm (gcc 13.3, glibc, Linux x86-64: 32-bit int and unsigned, two's complement), the SyntaxPilot compiler's C command with warnings on, and every output below is real. Timings depend on the machine.
Real-life pictures
| In real life | In C |
|---|---|
| a switchboard with 8 switches, each on or off | bits: 8 bits make a byte; 1 = on, 0 = off |
| turn one switch on, off, or flip it, leaving the others alone | set, clear, toggle bit k with a mask 1u << k |
| swapping two glasses of juice without a third glass | the XOR swap |
| socks from the laundry: every sock has a pair except one | the single number: pairs cancel with XOR |
Binary and the six bit operators
A number is stored as a row of bits. Bits are counted from the right: bit 0 is worth 1, bit 1 is worth 2, bit 2 is worth 4, and so on. 10 = 8 + 2 = 00001010.
| Operator | Name | Rule (bit by bit) | Example |
|---|---|---|---|
a & b |
AND | 1 only where both are 1 | 12 & 10 = 1100 & 1010 = 1000 = 8 |
a \| b |
OR | 1 where either is 1 | 12 \| 10 = 1110 = 14 |
a ^ b |
XOR (exclusive or) | 1 where they differ | 12 ^ 10 = 0110 = 6 |
~a |
NOT | flips every bit | ~0u = 4294967295 |
a << k |
left shift | moves bits k places left (× 2^k) | 1u << 3 = 8 |
a >> k |
right shift | moves bits k places right, dropping the last k | 10u >> 1 = 5 |
- A mask is a number used to pick out bits.
1u << kis a single 1 at bit k. - Use
unsignedfor bit work: shifts and~behave simply, and there's no sign bit.1 << 31with a signedintoverflows (undefined behaviour);1u << 31is fine. - Shifting by a negative amount or by 32 or more on a 32-bit number is undefined behaviour: C doesn't say what happens.
- Don't confuse
&/|(bits) with&&/||(logic: true or false, and they stop early).
Warm-up: Odd or even
Problem. Read numbers; print whether each is odd or even. 7 10 0 -3 -8 → odd, even, even, odd, even.
Edge cases: 0, negative numbers.
The obvious attempt: n % 2 == 1
#include <stdio.h>
int main() {
int n;
while (scanf("%d", &n) == 1) {
if (n % 2 == 1) printf("%d is odd\n", n);
else printf("%d is even\n", n);
}
return 0;
}
Input: 7 10 0 -3 -8
7 is odd
10 is even
0 is even
-3 is even
-8 is even
Why it failed
In C, % keeps the sign of the left operand (since C99, division truncates toward zero): -3 % 2 is -1, not 1. So the test said "even".
The fix: look at the last bit
Bit 0 is the ones place: it is 1 exactly for odd numbers. In two's complement (how every modern machine stores negative numbers, and required from C23), -3 is ...11111101, whose last bit is 1.
#include <stdio.h>
int main() {
int n;
while (scanf("%d", &n) == 1) {
if (n & 1) printf("%d is odd\n", n); /* last bit 1 = odd */
else printf("%d is even\n", n);
}
return 0;
}
7 is odd
10 is even
0 is even
-3 is odd
-8 is even
The portable arithmetic fix is n % 2 != 0. Complexity: O(1) time, O(1) space.
Q1: Check, set, clear and toggle the k-th bit
Problem. Read n and k. Say whether bit k of n is 1, then print n with bit k set, cleared and toggled.
Think out loud.
5 = 00000101: bit 0 → 1, bit 1 → 0, bit 2 → 1.10 = 00001010, k = 2: set →00001110(14), clear →00001010(unchanged), toggle →00001110.- Edge cases: the bit is already on/off; k = 31 (the top bit, needs
1u); k ≥ 32 or negative is invalid.
The obvious attempt: n & 1u << k == 0
#include <stdio.h>
int main() {
unsigned n;
int k;
while (scanf("%u %d", &n, &k) == 2) {
if (n & 1u << k == 0) printf("bit %d of %u is 0\n", k, n);
else printf("bit %d of %u is 1\n", k, n);
}
return 0;
}
Input: 5 0, 5 1, 5 2 (one pair per line)
main.c: In function 'main':
main.c:7:25: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
7 | if (n & 1u << k == 0) printf("bit %d of %u is 0\n", k, n);
| ~~~~~~~~^~~~
bit 0 of 5 is 1
bit 1 of 5 is 1
bit 2 of 5 is 1
Why it failed
Operator precedence (the order C applies operators): << first, then ==, and & last. So the condition means n & ((1u << k) == 0), which is n & 0, which is always 0. The if is never true, and every bit "is 1". gcc's -Wparentheses warning (part of -Wall) points straight at it.
The fix: brackets, and four one-line tools
| Operation | Code | Why |
|---|---|---|
| get bit k | (n >> k) & 1u |
bring bit k to position 0, keep only it |
| set bit k | n \| (1u << k) |
OR with 1 turns a bit on |
| clear bit k | n & ~(1u << k) |
AND with 0 turns it off; ~mask is all 1s except bit k |
| toggle bit k | n ^ (1u << k) |
XOR with 1 flips a bit |
#include <stdio.h>
int get_bit(unsigned n, int k) { return (n >> k) & 1u; }
unsigned set_bit(unsigned n, int k) { return n | (1u << k); }
unsigned clear_bit(unsigned n, int k) { return n & ~(1u << k); }
unsigned toggle_bit(unsigned n, int k) { return n ^ (1u << k); }
void show(const char *label, unsigned n) { /* last 8 bits */
printf(" %s ", label);
for (int k = 7; k >= 0; k--) putchar(get_bit(n, k) ? '1' : '0');
}
int main() {
unsigned n;
int k;
while (scanf("%u %d", &n, &k) == 2) {
if (k < 0 || k > 31) { printf("k=%d: must be 0..31\n", k); continue; }
printf("n=%u k=%d bit=%d", n, k, get_bit(n, k));
show("set", set_bit(n, k));
show("clear", clear_bit(n, k));
show("toggle", toggle_bit(n, k));
putchar('\n');
}
return 0;
}
Input: 10 1, 10 2, 10 0, 255 7, 0 3, 5 40
n=10 k=1 bit=1 set 00001010 clear 00001000 toggle 00001000
n=10 k=2 bit=0 set 00001110 clear 00001010 toggle 00001110
n=10 k=0 bit=0 set 00001011 clear 00001010 toggle 00001011
n=255 k=7 bit=1 set 11111111 clear 01111111 toggle 01111111
n=0 k=3 bit=0 set 00001000 clear 00000000 toggle 00001000
k=40: must be 0..31
Complexity: each operation is O(1) time and O(1) space (one or two machine instructions). That's why flags in drivers, games, file permissions and network headers are stored as bits: 8 yes/no flags fit in one byte.
Q2: Swap two numbers without a temporary variable
Problem. Write swap(int *x, int *y) with no third variable, then use it to reverse an array.
Think out loud.
- XOR facts:
x ^ x = 0,x ^ 0 = x, and XOR is commutative and associative (order and grouping don't matter). a ^= b; b ^= a; a ^= b;with a = 5 (101), b = 3 (011): a = 110 (6), b = 011 ^ 110 = 101 (5), a = 110 ^ 101 = 011 (3). Swapped.1 2 3 4 5→5 4 3 2 1;1 2 3 4→4 3 2 1.- Edge cases: odd length (a middle element), one element, equal values.
The obvious attempt: XOR swap in a two-pointer reverse
#include <stdio.h>
void swap(int *x, int *y) { /* no temp: XOR swap */
*x = *x ^ *y;
*y = *x ^ *y;
*x = *x ^ *y;
}
int main() {
int a[100], n = 0;
while (n < 100 && scanf("%d", &a[n]) == 1) n++;
for (int i = 0, j = n - 1; i <= j; i++, j--)
swap(&a[i], &a[j]);
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}
Input: 1 2 3 4 5
5 4 0 2 1
The middle 3 became 0. Other inputs show the same thing:
| Input | Output |
|---|---|
1 2 3 4 |
4 3 2 1 |
-7 9 -7 |
-7 0 -7 |
42 |
0 |
Even lengths work; every odd length loses its middle element.
Why it failed
The loop runs while i <= j. With an odd length, the last round has i == j, so swap(&a[2], &a[2]): x and y point to the same box. *x = *x ^ *y is 3 ^ 3 = 0, and since *y is the same box, both "copies" are now 0. Nothing can bring the 3 back.
Equal values in two different boxes are fine (7 ^ 7 = 0, then 0 ^ 7 = 7, then 7 ^ 0 = 7); only the same address breaks it.
The fix: return when both pointers are the same
#include <stdio.h>
void swap(int *x, int *y) { /* no temp: XOR swap */
if (x == y) return; /* same box: x ^ x would be 0 */
*x = *x ^ *y;
*y = *x ^ *y;
*x = *x ^ *y;
}
int main() {
int a[100], n = 0;
while (n < 100 && scanf("%d", &a[n]) == 1) n++;
for (int i = 0, j = n - 1; i <= j; i++, j--)
swap(&a[i], &a[j]);
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}
| Input | Output |
|---|---|
1 2 3 4 5 |
5 4 3 2 1 |
1 2 3 4 |
4 3 2 1 |
-7 9 -7 |
-7 9 -7 |
42 |
42 |
(Writing i < j in the loop also avoids the self-swap.)
Two more facts interviewers like:
a = a + b; b = a - b; a = a - b;also swaps without a temp, buta + bcan overflow, and signed overflow is undefined behaviour.- In real code, use a temporary variable. It is just as fast (the compiler keeps it in a register), always correct, and clear to read.
Complexity: each swap O(1); reversing n numbers O(n) time, O(1) extra space.
Q3: The single number
Problem. n numbers; every number appears exactly twice except one, which appears once. Find it.
Think out loud.
4 1 2 1 2→ 4;-5 3 3 -5 9 0 0→ 9.- Edge cases: n = 1; the single number is 0; negatives; a big input (100,001 numbers).
The obvious attempt: count every number
#include <stdio.h>
int main() {
int a[1000], n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < n; i++) { /* count each number */
int count = 0;
for (int j = 0; j < n; j++)
if (a[j] == a[i]) count++;
if (count == 1) { printf("single: %d\n", a[i]); break; }
}
return 0;
}
Input: 5 then 4 1 2 1 2
single: 4
Correct, but for each number it walks the whole array again. Timed on 50,000 pairs plus one single at the very end, next to the XOR way:
#include <stdio.h>
#include <time.h>
#define N 100001 /* 50000 pairs + 1 single */
int a[N];
double secs(clock_t start) {
return (double)(clock() - start) / CLOCKS_PER_SEC;
}
int nested_way(const int a[], int n) {
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = 0; j < n; j++)
if (a[j] == a[i]) count++;
if (count == 1) return a[i];
}
return -1;
}
int xor_way(const int a[], int n) {
int x = 0;
for (int i = 0; i < n; i++) x ^= a[i]; /* pairs cancel */
return x;
}
int main() {
for (int i = 0; i < N - 1; i++) a[i] = i / 2 + 1; /* 1 1 2 2 3 3 ... */
a[N - 1] = -7; /* once, at the end */
clock_t t = clock();
int s1 = nested_way(a, N);
printf("nested: %d, %.2f s\n", s1, secs(t));
t = clock();
int s2 = xor_way(a, N);
printf("xor: %d, %.2f s\n", s2, secs(t));
return 0;
}
nested: -7, 3.26 s
xor: -7, 0.00 s
(One real run; your timings will differ, but the gap won't.)
Why it was slow
For each of n numbers we scan n numbers: n × n ≈ 10 billion comparisons for n = 100,001. That's O(n²): double n, four times the time.
The fix: XOR everything
XOR every number into x. Because order doesn't matter, the pairs meet and cancel (v ^ v = 0), and x ^ 0 = x leaves only the single number:
4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4.
#include <stdio.h>
int main() {
int n, x = 0, v;
if (scanf("%d", &n) != 1 || n < 1) return 1;
for (int i = 0; i < n; i++) {
scanf("%d", &v);
x ^= v; /* v ^ v = 0, v ^ 0 = v */
}
printf("single: %d\n", x);
return 0;
}
| Input | Output |
|---|---|
5 / 4 1 2 1 2 |
single: 4 |
7 / -5 3 3 -5 9 0 0 |
single: 9 |
1 / 42 |
single: 42 |
3 / 0 7 7 |
single: 0 |
5 / -1 -1 2147483647 -9 -9 |
single: 2147483647 |
Complexity: O(n) time, O(1) space; we don't even store the array. (Sorting would be O(n log n); a counting array needs memory for every possible value and fails for negatives.)
Complexity summary
| Question | Time | Extra space |
|---|---|---|
Odd or even (n & 1) |
O(1) | O(1) |
| Get / set / clear / toggle bit k | O(1) | O(1) |
| Reverse an array with swaps | O(n) | O(1) |
| Single number, nested counting | O(n²) (over 3 s for 100,001) | O(n) |
| Single number, XOR | O(n) (0.00 s) | O(1) |
Common mistakes (and the real results)
| Mistake | What happens | Why | Fix |
|---|---|---|---|
if (n % 2 == 1) |
-3 is even |
-3 % 2 is -1 |
n & 1 or n % 2 != 0 |
n & 1u << k == 0 |
warning: suggest parentheses around comparison in operand of '&' [-Wparentheses], every bit "is 1" |
== runs before & |
((n >> k) & 1u) == 0 |
1 << 31 with int |
prints -2147483648 here, but it's undefined behaviour |
overflows a signed int | 1u << 31 |
n << 32 on a 32-bit number |
undefined behaviour | shift ≥ the width | check 0 <= k <= 31 |
| XOR swap of a box with itself | the value becomes 0 (5 4 0 2 1) |
x ^ x = 0 |
if (x == y) return; |
a & b where you meant a && b |
wrong answer | bits vs logic | && / \|\| for conditions |
a = a + b; b = a - b; a = a - b; |
may overflow | signed overflow is UB | use a temp |
Your turn: two numbers appear once (solution)
Problem. Every number appears twice, except two numbers that appear once. Print both, smaller first. 1 2 1 3 2 5 → 3 5.
Idea. XOR of everything is a ^ b (the pairs cancel), and it isn't 0 because a ≠ b. Any 1 bit in it is a bit where a and b differ; take the lowest one with x & (~x + 1u) (in unsigned arithmetic, ~x + 1 is -x). Split all numbers into two groups by that bit: a and b land in different groups, and each pair lands together. XOR each group. O(n) time, O(1) extra space (the array here is only kept for the second pass; you could read the input twice instead).
#include <stdio.h>
int main() {
int n, a[1000];
if (scanf("%d", &n) != 1 || n < 2 || n > 1000) return 1;
unsigned x = 0;
for (int i = 0; i < n; i++) { scanf("%d", &a[i]); x ^= (unsigned)a[i]; }
unsigned low = x & (~x + 1u); /* lowest bit where the two differ */
unsigned p = 0, q = 0;
for (int i = 0; i < n; i++)
if ((unsigned)a[i] & low) p ^= (unsigned)a[i];
else q ^= (unsigned)a[i];
int r = (int)p, s = (int)q;
if (r > s) { int t = r; r = s; s = t; }
printf("%d %d\n", r, s);
return 0;
}
| Input | Output |
|---|---|
6 / 1 2 1 3 2 5 |
3 5 |
4 / -4 7 7 9 |
-4 9 |
2 / 0 8 |
0 8 |
Converting the unsigned results back with (int) is implementation-defined for values above INT_MAX, and gcc defines it as the two's complement value we want.
Practice questions (with solutions)
1. Count the set bits (1 bits) of a number.
Solution
n & (n - 1) clears the lowest 1 bit, so the loop runs once per 1 bit (Brian Kernighan's method).
#include <stdio.h>
int count_bits(unsigned n) {
int c = 0;
while (n != 0) {
n &= n - 1; /* clears the lowest 1 bit */
c++;
}
return c;
}
int main() {
unsigned n;
while (scanf("%u", &n) == 1)
printf("%u has %d set bits\n", n, count_bits(n));
return 0;
}
Input: 0 1 12 255 4294967295
0 has 0 set bits
1 has 1 set bits
12 has 2 set bits
255 has 8 set bits
4294967295 has 32 set bits
O(number of 1 bits) time, at most 32 rounds; O(1) space.
2. Reverse the 32 bits of an unsigned number.
Solution
#include <stdio.h>
unsigned reverse_bits(unsigned n) { /* 32-bit unsigned */
unsigned r = 0;
for (int i = 0; i < 32; i++) {
r = (r << 1) | (n & 1u); /* take n's last bit */
n >>= 1;
}
return r;
}
int main() {
unsigned n;
while (scanf("%u", &n) == 1)
printf("%u -> %u\n", n, reverse_bits(n));
return 0;
}
Input: 1 2 4294967295 0 43261596
1 -> 2147483648
2 -> 1073741824
4294967295 -> 4294967295
0 -> 0
43261596 -> 964176192
O(32) = O(1) time and space.
3. Store 8 yes/no answers in one unsigned char.
Solution
#include <stdio.h>
int main() {
unsigned char answers = 0; /* 8 yes/no answers, bit k = question k */
int yes[] = {0, 2, 3, 7}; /* questions answered "yes" */
for (int i = 0; i < 4; i++)
answers |= (unsigned char)(1u << yes[i]);
answers &= (unsigned char)~(1u << 3); /* changed their mind on question 3 */
for (int k = 0; k < 8; k++)
printf("Q%d: %s\n", k, (answers >> k) & 1u ? "yes" : "no");
printf("stored in %zu byte, value %u\n", sizeof answers, answers);
return 0;
}
Q0: yes
Q1: no
Q2: yes
Q3: no
Q4: no
Q5: no
Q6: no
Q7: yes
stored in 1 byte, value 133
133 = 1 + 4 + 128 = bits 0, 2 and 7. Eight ints would take 32 bytes; this takes 1.
Quick quiz
#include <stdio.h>
int main() {
unsigned x = 12;
printf("%u\n", x & (x - 1));
return 0;
}
What does it print? (A) 12 (B) 11 (C) 8 (D) 4
Answer
(C) 8 (real output: 8). 12 = 1100, 11 = 1011, and 1100 & 1011 = 1000 = 8. x & (x - 1) always clears the lowest 1 bit: it's the power-of-two check from episode 6 (n != 0 && (n & (n - 1)) == 0) and practice question 1 above.
Interview questions
- How do you check odd or even without
%?n & 1(1 = odd). - Set, clear, toggle and check bit k?
n | (1u << k),n & ~(1u << k),n ^ (1u << k),(n >> k) & 1u. - Why does
n & 1 << k == 0not work?==has higher precedence than&. - Swap two numbers without a temp?
a ^= b; b ^= a; a ^= b;and the trap: if both are the same variable (same address) the value becomes 0. - Why prefer a temp in real code? Clear, always correct, and just as fast.
- Find the element that appears once when every other appears twice? XOR all of them: O(n) time, O(1) space.
- What does
x & (x - 1)do? Clears the lowest set bit;x & (x - 1) == 0means x is a power of two (or 0). - What does
x & -x(orx & (~x + 1)) give? The lowest set bit alone. - Is right-shifting a negative number defined? It's implementation-defined (gcc does an arithmetic shift, copying the sign bit). Use unsigned.
- Why is
1 << 31dangerous? It overflows a 32-bit signed int: undefined behaviour. Use1u << 31.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Bit | One binary digit, 0 or 1 | a switch, off or on |
| Byte | 8 bits | unsigned char |
| Binary | Base 2: each place is worth twice the one to its right | 10 = 1010 |
| Bit k | The bit worth 2^k, counted from the right starting at 0 | bit 0 = the ones place |
Bitwise AND & |
1 where both bits are 1 | 12 & 10 = 8 |
Bitwise OR \| |
1 where either bit is 1 | 12 \| 10 = 14 |
XOR ^ |
Exclusive or: 1 where the bits differ | 12 ^ 10 = 6 |
NOT ~ |
Flips every bit | ~(1u << 3) |
Left shift << |
Moves bits left, filling with 0 | 1u << 3 = 8 |
Right shift >> |
Moves bits right, dropping the last ones | 10u >> 1 = 5 |
| Mask | A number used to pick out or change certain bits | 1u << k |
| Set / clear / toggle | Turn a bit on / off / flip it | \|, & ~, ^ |
unsigned |
An integer type with no sign: 0 to 4294967295 here | unsigned n; |
1u |
The constant 1 as an unsigned int | 1u << 31 |
| Two's complement | How negative numbers are stored: invert the bits and add 1 | -3 = ...11111101 |
| Sign bit | The top bit of a signed number in two's complement | bit 31 of an int |
| Operator precedence | The order operators are applied | == before & |
-Wparentheses |
gcc warning (in -Wall) about confusing precedence |
Q1 |
| Undefined behaviour (UB) | The C standard says nothing about what happens | 1 << 31, shift by 32 |
| Implementation-defined | The compiler must choose and document the behaviour | >> on a negative int |
| XOR swap | Swapping with three XORs and no temp | a ^= b; b ^= a; a ^= b; |
| Aliasing | Two pointers to the same memory | swap(&a[2], &a[2]) |
| Single number | The one value without a pair | Q3 |
| Lowest set bit | The rightmost 1 bit | x & (~x + 1u) |
| O(1), O(n), O(n²) | Work that stays constant / grows with n / grows with n squared | Q3: 3 s vs 0.00 s |
Summary
- A number is a row of bits; bit 0 is the ones place.
n & 1tells odd from even for any sign;n % 2 == 1fails for negatives. - A mask
1u << ktouches one bit: set with|, clear with& ~, toggle with^, read with(n >> k) & 1u. Brackets always:==runs before&. Use unsigned, and keep k in 0..31. - The XOR swap works for two different boxes but zeroes a box swapped with itself. In real code, use a temp.
- XOR everything and the pairs cancel: the single number in O(n) time and O(1) space.
x & (x - 1)clears the lowest 1 bit.
Next episode: Linked list questions I: build and print a list, insert at the head and the tail, and delete a node by value (the head, the middle, the tail and a missing value).