These are the notes for C Coding Questions, episode 6, placement practice for people who finished the SyntaxPilot C course. The last number questions, about bits: decimal to binary and back, counting set bits and checking a power of two with n & (n - 1). Two of the obvious attempts never finish, and one prints a number that isn't binary at all.
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, Linux x86-64, 32-bit int), the SyntaxPilot compiler's C command with warnings on, and every output below is real. The compiler stops a program after 8 seconds (Time Limit Exceeded), like an online judge.
Binary in one picture: a board of light switches
| On a festival light board | In C |
|---|---|
| each switch is on or off | a bit is 1 or 0; an int has 32 of them |
| switch k (from the right, starting at 0) is worth 2ᵏ bulbs: 1, 2, 4, 8, … | place values double: binary 1101 = 8 + 4 + 1 = 13 |
| compare two boards switch by switch | the bitwise operators |
Binary is base 2: every place is worth twice the place to its right.
| Operator | Name | Result bit is 1 when… | 12 (1100) with 10 (1010) |
|---|---|---|---|
& |
AND | both bits are 1 | 1000 = 8 |
| |
OR | either bit is 1 | 1110 = 14 |
^ |
XOR (exclusive or) | the bits differ | 0110 = 6 |
~ |
NOT | the bit is 0 (flips every bit) | ~0u = 4294967295 |
<< |
left shift | moves every bit left (× 2 per place) | 1 << 3 = 8 |
>> |
right shift | moves every bit right (÷ 2 per place) | 12 >> 2 = 3 |
#include <stdio.h>
int main() {
printf("%d %d %d\n", 12 & 10, 12 | 10, 12 ^ 10);
return 0;
}
Output:
8 14 6
Two's complement. Computers store negative ints so that -1 is all 32 bits set, and INT_MIN (-2,147,483,648) is just the leftmost bit, the sign bit.
Q1: Decimal to binary
Problem. Read an int n ≥ 0 and print it in binary.
| Input | Output |
|---|---|
5 |
101 |
10 |
1010 |
1024 |
10000000000 |
0 |
0 |
2147483647 |
31 ones |
-5 |
rejected |
Think out loud
Like % 10 and / 10 for decimal digits (episode 3): n % 2 is the last bit and n / 2 drops it. For 10: 0, 1, 0, 1, then n is 0. The bits come out last-first, so they must be printed in the other order.
The obvious attempt: bits as decimal digits of an int
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
int bin = 0, place = 1;
while (n > 0) {
bin = bin + (n % 2) * place;
place = place * 10;
n = n / 2;
}
printf("%d\n", bin);
return 0;
}
Input 10:
1010
Input 1023:
1111111111
Input 1024:
1410065408
1024 "in binary-looking decimal" is 10,000,000,000: eleven decimal digits, but an int holds at most 2,147,483,647 (ten digits). bin and place overflow: undefined behaviour, no warning. The result even contains digits like 4 and 6.
The fix: keep the bits as characters
char bits[32]holds one character per bit (enough for any non-negativeint).'0' + n % 2is the character'0'or'1'(characters are small integers, and'1'comes right after'0').- A do-while runs once before checking, so 0 still produces the bit
0. - Print the array backwards.
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
if (n < 0) {
printf("enter 0 or more\n");
return 0;
}
char bits[32];
int len = 0;
do {
bits[len] = '0' + n % 2;
len++;
n = n / 2;
} while (n > 0);
for (int i = len - 1; i >= 0; i--) printf("%c", bits[i]);
printf("\n");
return 0;
}
Input 10:
1010
Input 1024:
10000000000
Input 0:
0
Input 1:
1
Input 2147483647:
1111111111111111111111111111111
Input -5:
enter 0 or more
Q1, the other way: binary to decimal
Problem. Read a string of up to 32 zeros and ones and print its value.
Read left to right; each new bit doubles the value so far and adds itself: 1010 → 0 → 1 → 2 → 5 → 10. s[i] - '0' turns the character '1' into the number 1. %39s reads at most 39 characters, so the 40-char array can't overflow. value is an unsigned int so that 32 ones (4,294,967,295) fit; printed with %u.
#include <stdio.h>
int main() {
char s[40];
scanf("%39s", s);
unsigned int value = 0;
int len = 0;
for (int i = 0; s[i] != '\0'; i++) {
if (s[i] != '0' && s[i] != '1') {
printf("not a binary number\n");
return 0;
}
value = value * 2 + (s[i] - '0');
len++;
}
if (len > 32) printf("too many bits\n");
else printf("%u\n", value);
return 0;
}
Input 1010:
10
Input 0:
0
Input 10000000000:
1024
Input 11111111111111111111111111111111:
4294967295
Input 102:
not a binary number
Input 111111111111111111111111111111111:
too many bits
Complexity (both directions): one step per bit, O(log n) time (at most 32 steps), O(1) space.
Q2: Count the set bits
Problem. A set bit is a bit that is 1. Read an int n and print how many of its 32 bits are set (this is also called the population count).
| Input | Bits | Output |
|---|---|---|
7 |
111 |
3 |
8 |
1000 |
1 |
-1 |
32 ones (two's complement) | 32 |
-2147483648 |
only the sign bit | 1 |
0 |
0 |
The obvious attempt
n & 1 is the last bit; n >> 1 drops it.
#include <stdio.h>
int main() {
int n, count = 0;
scanf("%d", &n);
while (n != 0) {
if (n & 1) count++;
n = n >> 1;
}
printf("%d\n", count);
return 0;
}
Input 7:
3
Input -1:
Time Limit Exceeded (stopped after 8 seconds, no output)
Why: right-shifting a negative int
In C, right-shifting a negative signed value is implementation-defined: each compiler chooses and documents the rule. gcc does an arithmetic shift: it copies the sign bit into the gap. So -1 >> 1 is still -1 (all ones), n never reaches 0, and the loop runs forever. (Left-shifting a negative value is undefined behaviour.)
The fix: do bit work on unsigned int. Converting -1 to unsigned int is well defined and gives 4,294,967,295, the same 32 ones, and shifting an unsigned value right always brings in zeros.
Brian Kernighan's trick: u & (u - 1)
Subtracting 1 turns the lowest 1 bit into 0 and every 0 below it into 1; ANDing with the original cancels exactly that part:
| bits | |
|---|---|
u |
1011 0100 |
u - 1 |
1011 0011 |
u & (u - 1) |
1011 0000 (lowest 1 switched off) |
So the loop runs once per set bit, not once per bit. Named after Brian Kernighan, co-author of The C Programming Language.
#include <stdio.h>
int main() {
int n, count = 0;
scanf("%d", &n);
unsigned int u = (unsigned int)n;
while (u != 0) {
u = u & (u - 1);
count++;
}
printf("%d\n", count);
return 0;
}
Input 7:
3
Input 8:
1
Input -1:
32
Input 0:
0
Input -2147483648:
1
Input 2147483647:
31
Complexity: O(number of set bits) time, at most 32; O(1) space. (gcc also offers __builtin_popcount(u), which is not standard C.)
Q3: Is n a power of two?
Problem. The powers of two are 1, 2, 4, 8, 16, … (2⁰, 2¹, 2², …). Read an int n and print yes or no.
| Input | Output |
|---|---|
1, 8, 1024, 1073741824 (2³⁰) |
yes |
6, 0, -8, 2147483647 |
no |
The obvious attempt: keep halving
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
while (n % 2 == 0) n = n / 2;
if (n == 1) printf("yes\n");
else printf("no\n");
return 0;
}
Input 8:
yes
Input 6:
no
Input 0:
Time Limit Exceeded (stopped after 8 seconds, no output)
0 % 2 == 0, so 0 counts as even, and 0 / 2 is 0 again: the loop never ends.
The fix: exactly one set bit
A power of two has exactly one set bit (8 = 1000). n & (n - 1) switches off the lowest set bit, so for a power of two it leaves 0: 8 & 7 = 1000 & 0111 = 0, but 6 & 5 = 0110 & 0101 = 0100. Zero also gives 0, so require n > 0 too.
&&short-circuits: ifn > 0is false, the right side is never evaluated, son - 1can't overflow forINT_MIN.- The brackets matter:
==binds tighter than&.
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
if (n > 0 && (n & (n - 1)) == 0) printf("yes\n");
else printf("no\n");
return 0;
}
Input 0:
no
Input 8:
yes
Input 6:
no
Input 1:
yes
Input -8:
no
Input 1073741824:
yes
Input 2147483647:
no
Input -2147483648:
no
Without the brackets, gcc -Wall warns:
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
if (n & (n - 1) == 0) printf("yes\n");
else printf("no\n");
return 0;
}
main.c: In function ‘main’:
main.c:6:21: warning: suggest parentheses around comparison in operand of ‘&’ [-Wparentheses]
6 | if (n & (n - 1) == 0) printf("yes\n");
| ~~~~~~~~^~~~
Input 8:
no
n & (n - 1) == 0 means n & ((n - 1) == 0), which is 8 & 0 = 0 for 8, so it prints no.
Complexity: O(1) time and space.
Complexity summary
| Question | Obvious attempt | Fixed | Extra space |
|---|---|---|---|
| Decimal to binary | overflows at 1024 | O(log n) with a char array | O(1) (32 chars) |
| Binary to decimal | O(length) | O(1) | |
| Count set bits | never ends for negatives | O(set bits) with u & (u - 1) |
O(1) |
| Power of two | never ends for 0 | O(1) with n > 0 && (n & (n - 1)) == 0 |
O(1) |
Common mistakes (and the real messages)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
bin = bin + (n % 2) * place; |
no warning: 1410065408 for 1024 |
11 decimal digits overflow an int (UB) |
store the bits in a char array |
while (n > 0) loop for the bits of 0 |
an empty line | 0 still has one bit | a do-while loop |
n = n >> 1; with n = -1 |
Time Limit Exceeded |
gcc copies the sign bit: -1 stays -1 | unsigned int u = (unsigned int)n; |
while (n % 2 == 0) n /= 2; with 0 |
Time Limit Exceeded |
0 is even and 0 / 2 is 0 | n > 0 && (n & (n - 1)) == 0 |
if (n & (n - 1) == 0) |
warning: suggest parentheses around comparison in operand of '&' [-Wparentheses] |
== binds tighter than & |
(n & (n - 1)) == 0 |
1 << 31 with a signed int |
undefined behaviour | the result doesn't fit in an int |
1u << 31 |
printf("%d", u) for a big unsigned |
a negative number | wrong format | %u |
Your turn: Hamming distance (solution)
Problem. Read two ints a b and print in how many bit positions they differ: the Hamming distance. 1 4 → 2 (001 vs 100), 7 7 → 0, 0 -1 → 32.
Idea. a ^ b has a 1 exactly where the bits differ; count its set bits (Q2), as an unsigned int.
Show the solution
#include <stdio.h>
int main() {
int a, b, count = 0;
scanf("%d %d", &a, &b);
unsigned int u = (unsigned int)a ^ (unsigned int)b;
while (u != 0) {
u = u & (u - 1);
count++;
}
printf("%d\n", count);
return 0;
}
Input 1 4:
2
Input 7 7:
0
Input 0 -1:
32
Input 12 10:
2
Time O(32) = O(1), space O(1).
Practice questions (with solutions)
1. Is the k-th bit of n set? Set it, clear it and toggle it. A mask is a number with only the bits you care about set: 1u << k.
Solution
#include <stdio.h>
int main() {
unsigned int n;
int k;
scanf("%u %d", &n, &k);
if (k < 0 || k > 31) {
printf("k must be from 0 to 31\n");
return 0;
}
unsigned int mask = 1u << k;
printf("bit %d is %s\n", k, (n & mask) ? "set" : "not set");
printf("set: %u\n", n | mask);
printf("clear: %u\n", n & ~mask);
printf("toggle: %u\n", n ^ mask);
return 0;
}
Input 10 1:
bit 1 is set
set: 10
clear: 8
toggle: 8
Input 10 2:
bit 2 is not set
set: 14
clear: 10
toggle: 14
Input 0 31:
bit 31 is not set
set: 2147483648
clear: 0
toggle: 2147483648
Input 10 32:
k must be from 0 to 31
2. Swap two ints with XOR, and why xor_swap(&c, &c) breaks.
Solution
#include <stdio.h>
void xor_swap(int *x, int *y) {
*x = *x ^ *y;
*y = *x ^ *y;
*x = *x ^ *y;
}
int main() {
int a = 5, b = 9;
xor_swap(&a, &b);
printf("a = %d, b = %d\n", a, b);
int c = 7;
xor_swap(&c, &c); /* both pointers point at c */
printf("c = %d\n", c);
return 0;
}
Output:
a = 9, b = 5
c = 0
When both pointers point at the same variable, the first line computes c ^ c = 0, and every later line keeps it 0. In real code just use a temporary variable; it is clearer and just as fast.
3. Print all 32 bits of an int, with leading zeros, in groups of 8.
Solution
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
unsigned int u = (unsigned int)n;
for (int k = 31; k >= 0; k--) {
printf("%u", (u >> k) & 1u);
if (k % 8 == 0 && k != 0) printf(" ");
}
printf("\n");
return 0;
}
Input 13:
00000000 00000000 00000000 00001101
Input -1:
11111111 11111111 11111111 11111111
Input -2147483648:
10000000 00000000 00000000 00000000
Input 1073741824:
01000000 00000000 00000000 00000000
Quick quiz
printf("%d %d %d\n", 12 & 10, 12 | 10, 12 ^ 10);
(A) 8 14 6 (B) 2 22 6 (C) 8 14 2 (D) 0 22 22
Answer
(A) 8 14 6. 12 = 1100, 10 = 1010. AND keeps the bits both have: 1000 = 8. OR keeps either: 1110 = 14. XOR keeps the ones that differ: 0110 = 6. (The output above is real.)
Interview questions
- How do you check whether n is a power of two in O(1)?
n > 0 && (n & (n - 1)) == 0. - What does
n & (n - 1)do? It switches off the lowest set bit. - How do you count set bits efficiently? Brian Kernighan's loop:
while (u) { u &= u - 1; count++; }, one turn per set bit. - What is the difference between
>>on signed and unsigned values? Unsigned shifts in zeros; for a negative signed value the result is implementation-defined (gcc copies the sign bit). - How is -1 stored in a 32-bit int? In two's complement: all 32 bits set.
- How do you get, set, clear and toggle bit k?
n & (1u << k),n | (1u << k),n & ~(1u << k),n ^ (1u << k). - Why might
if (x & 1 == 0)be wrong?==binds tighter than&; write(x & 1) == 0. - What is XOR useful for? Finding differing bits (Hamming distance), toggling bits, and finding the one unpaired number in an array.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Bit | A binary digit: 0 or 1 | an int has 32 bits |
| Binary (base 2) | A number system where each place is worth twice the one to its right | 1101 = 13 |
| Place value | What a position is worth | 1, 2, 4, 8 in binary |
| Set bit | A bit that is 1 | 7 has 3 set bits |
| Population count | The number of set bits | popcount(7) = 3 |
Bitwise AND & |
1 where both bits are 1 | 12 & 10 = 8 |
Bitwise OR | |
1 where either bit is 1 | 12 | 10 = 14 |
Bitwise XOR ^ |
1 where the bits differ | 12 ^ 10 = 6 |
Bitwise NOT ~ |
Flips every bit | ~mask |
Left shift << |
Moves bits left; each place doubles | 1u << 3 = 8 |
Right shift >> |
Moves bits right; each place halves | 12 >> 2 = 3 |
| Arithmetic shift | A right shift that copies the sign bit | gcc's -1 >> 1 = -1 |
| Sign bit | The leftmost bit of a signed int; 1 means negative | INT_MIN is only the sign bit |
| Two's complement | How negative ints are stored; -1 is all ones | -1 → 32 ones |
unsigned int |
No negatives, 0 to 4,294,967,295; shifts bring in zeros | (unsigned int)n |
| Implementation-defined | The compiler chooses the behaviour and must document it | >> of a negative int |
| Undefined behaviour (UB) | The C standard doesn't define the result | signed overflow, 1 << 31 |
| Mask | A number with only the bits you want set | 1u << k |
| Brian Kernighan's trick | u & (u - 1) switches off the lowest set bit |
counting set bits |
| Power of two | 2ᵏ: exactly one set bit | 1, 2, 4, 8, 1024 |
| Short-circuit evaluation | && skips the right side when the left side is false |
n > 0 && (n & (n - 1)) == 0 |
| Operator precedence | Which operator binds tighter | == before & |
| Hamming distance | The number of positions where two values differ | 1 vs 4 → 2 |
do-while loop |
Runs its body once before checking | the bits of 0 |
| Time Limit Exceeded (TLE) | The judge stopped a program that ran too long | 8 seconds here |
| Edge case | An input at the boundary | 0, -1, INT_MIN, INT_MAX |
Summary
n % 2is the last bit andn / 2drops it; bits come out backwards, so keep them in achararray and print in reverse.- Binary to decimal:
value = value * 2 + bit, in anunsigned int, rejecting anything but 0 and 1. - Do bit work on
unsigned int: right-shifting a negative int can loop forever. u & (u - 1)switches off the lowest set bit: count set bits in O(set bits), and test a power of two withn > 0 && (n & (n - 1)) == 0.- Brackets around
&comparisons;-Wallwarns when they are missing.
Next episode: Array questions I: the largest and second largest element (with duplicates), min and max in one pass, sum and average (the integer division trap).