These are the notes for C++ Coding Questions, episode 4, placement practice for people who finished the SyntaxPilot C++ course. Bits and number bases: printing a number in binary (by hand and with std::bitset), counting the set bits (with n & 1, Brian Kernighan's n & (n - 1) and __builtin_popcount), and checking a power of two in one line, plus the famous 1 << 31 trap.
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 g++ -Wall -O2 -std=c++17 main.cpp -o main (g++ 13.3, Linux x86-64, 32-bit int, 64-bit long long), 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, TLE), like an online judge.
Real-life picture: a board of light switches
| On the switchboard | In binary / C++ |
|---|---|
| four switches worth 8, 4, 2 and 1, each on or off | bits: each bit is 1 or 0 and is worth a power of two |
| 13 = 8 + 4 + 1: on, on, off, on | 13 = 1101 in binary |
| how many lights are on? | the number of set bits (bits that are 1) |
| exactly one switch on: 1, 2, 4, 8, ... | a power of two has exactly one set bit |
Every whole number has exactly one binary pattern. Reading from the right, the places are worth 1, 2, 4, 8, 16, 32, ... (powers of two), just like decimal places are worth 1, 10, 100, ...
The bit operators used today
| Operator | Name | What it does | Example (12 = 1100, 10 = 1010) |
|---|---|---|---|
a & b |
bitwise AND | 1 where both bits are 1 | 12 & 10 = 1000 = 8 |
a | b |
bitwise OR | 1 where either bit is 1 | 12 | 10 = 1110 = 14 |
a ^ b |
bitwise XOR | 1 where the bits differ | 12 ^ 10 = 0110 = 6 |
~a |
bitwise NOT | flips every bit | ~0 = -1 (all ones) |
a << k |
left shift | moves bits k places left (× 2ᵏ) | 1 << 3 = 8 |
a >> k |
right shift | moves bits k places right (÷ 2ᵏ) | 12 >> 2 = 3 |
n & 1 is the last bit (1 if n is odd). Do not mix up & (bitwise AND, works on every bit) with && (logical AND, true or false).
Q1: Print n in binary
Problem. Read integers and print each one in binary.
| Input | Output |
|---|---|
| 13 | 1101 |
| 6 | 110 |
| 1 | 1 |
| 255 | 11111111 |
| 0 | 0 |
By hand: divide by 2 again and again and write down the remainders. 13 → remainder 1, 6 → remainder 0, 3 → remainder 1, 1 → remainder 1, 0. The remainders read from the last to the first are the bits: 1101.
Edge cases: 0, negative numbers, numbers that need many bits.
The obvious attempt: print n % 2 while dividing
#include <iostream>
using namespace std;
int main() {
int n;
while (cin >> n) {
while (n > 0) {
cout << n % 2;
n /= 2;
}
cout << "\n";
}
return 0;
}
Input 13 6 0 -5:
1011
011
Wrong. 13 printed as 1011 (it is 1101), 6 as 011, and 0 and −5 printed empty lines.
Why: dividing by 2 peels off the last bit first (the ones place), so the bits come out right to left. For 0 and for negative numbers the while (n > 0) loop never runs.
Fix: put each new bit in front of the string
#include <iostream>
#include <string>
using namespace std;
string toBinary(int n) {
if (n == 0) return "0";
string s = "";
while (n > 0) {
s = char('0' + n % 2) + s;
n /= 2;
}
return s;
}
int main() {
int n;
while (cin >> n)
cout << n << " -> " << toBinary(n) << "\n";
return 0;
}
Input 13 6 0 1 255 -5:
13 -> 1101
6 -> 110
0 -> 0
1 -> 1
255 -> 11111111
-5 ->
char('0' + n % 2) turns the number 0 or 1 into the character '0' or '1'. Every non-negative number is right; −5 is still empty.
std::bitset: how the machine really stores a number
#include <iostream>
#include <bitset>
using namespace std;
int main() {
int n;
while (cin >> n)
cout << n << " -> " << bitset<8>(n) << "\n";
return 0;
}
Input 13 6 0 255 -5 300:
13 -> 00001101
6 -> 00000110
0 -> 00000000
255 -> 11111111
-5 -> 11111011
300 -> 00101100
bitset<8>(n)is n as exactly 8 bits (from the header<bitset>);coutprints it as 0s and 1s.- −5 → 11111011. Negative integers are stored in two's complement: write 5 (
00000101), flip every bit (11111010), add 1 (11111011). The leftmost bit is the sign bit: 1 means negative. - 300 → 00101100 is wrong (that is 44). 300 =
100101100needs 9 bits;bitset<8>keeps only the last 8 and silently drops the rest.
Fix: bitset<32> and trim the leading zeros
#include <iostream>
#include <bitset>
#include <string>
using namespace std;
string toBinary(int n) {
string s = bitset<32>(n).to_string();
size_t first = s.find('1');
if (first == string::npos) return "0";
return s.substr(first);
}
int main() {
int n;
while (cin >> n)
cout << n << " -> " << toBinary(n) << "\n";
return 0;
}
Input 13 6 0 1 255 -5 300:
13 -> 1101
6 -> 110
0 -> 0
1 -> 1
255 -> 11111111
-5 -> 11111111111111111111111111111011
300 -> 100101100
All correct: every int fits in 32 bits. s.find('1') returns string::npos when there is no '1' (the number was 0).
Complexity: dividing by 2 takes one step per bit, about log₂ n steps: O(log n) time, O(log n) space for the string. bitset<32> is a fixed 32 steps.
Q2: Count the set bits
Problem. For each integer, print how many of its bits are 1 (the population count, or popcount).
| Input | Binary | Output |
|---|---|---|
| 13 | 1101 | 3 |
| 7 | 111 | 3 |
| 0 | 0 | 0 |
| 255 | 11111111 | 8 |
| −1 | 32 ones | 32 |
The obvious attempt: test the last bit, shift right
#include <iostream>
using namespace std;
int countBits(int n) {
int count = 0;
while (n != 0) {
if (n & 1) count++;
n >>= 1;
}
return count;
}
int main() {
int n;
while (cin >> n)
cout << n << " has " << countBits(n) << " set bits\n";
return 0;
}
Input 13 7 0 255:
13 has 3 set bits
7 has 3 set bits
0 has 0 set bits
255 has 8 set bits
Input -1: Time Limit Exceeded (the loop never ends).
Why: −1 is 32 ones. Shifting a negative signed number right is an arithmetic shift on this compiler: the sign bit is copied in from the left, so -1 >> 1 is still −1 and n never becomes 0. (Before C++20 the result of right-shifting a negative number is implementation-defined; g++ copies the sign bit.)
Fix: unsigned int
#include <iostream>
using namespace std;
int countBits(unsigned int n) {
int count = 0;
while (n != 0) {
if (n & 1) count++;
n >>= 1;
}
return count;
}
int main() {
int n;
while (cin >> n)
cout << n << " has " << countBits(n) << " set bits\n";
return 0;
}
Input 13 7 0 255 -1 -8:
13 has 3 set bits
7 has 3 set bits
0 has 0 set bits
255 has 8 set bits
-1 has 32 set bits
-8 has 29 set bits
An unsigned int has no sign: −1 converts to its 32 bits (4294967295), and shifting an unsigned number always brings in zeros, so the loop ends after at most 32 steps. Rule: when you work with bits, use unsigned types.
Brian Kernighan's trick: n & (n - 1) drops the lowest set bit
n = 12 = 1100
n - 1 = 11 = 1011 the lowest 1 became 0, the 0s after it became 1s
n & (n-1) = 8 = 1000 the lowest set bit is gone
Repeat n &= n - 1 until n is 0 and count the steps: one step per set bit, not per bit.
#include <iostream>
using namespace std;
int countBits(unsigned int n) {
int count = 0;
while (n != 0) {
n &= n - 1;
count++;
}
return count;
}
int main() {
int n;
while (cin >> n)
cout << n << ": " << countBits(n) << " and " << __builtin_popcount(n) << "\n";
return 0;
}
Input 13 0 255 -1 2147483647:
13: 3 and 3
0: 0 and 0
255: 8 and 8
-1: 32 and 32
2147483647: 31 and 31
__builtin_popcount is a GCC/Clang built-in (not standard C++; MSVC has __popcnt). It usually compiles to a single popcnt machine instruction. In C++20 the standard version is std::popcount in <bit>.
The trap: __builtin_popcount on a long long
#include <iostream>
#include <bitset>
using namespace std;
int main() {
long long x = 1099511627775LL; // 2^40 - 1: forty 1 bits
cout << __builtin_popcount(x) << "\n";
cout << __builtin_popcountll(x) << "\n";
cout << bitset<64>(x).count() << "\n";
return 0;
}
Output:
32
40
40
__builtin_popcount takes an unsigned int (32 bits): the 64-bit value is cut to its last 32 bits before counting, with no warning. Use __builtin_popcountll (for long long) or bitset<64>(x).count().
Complexity: shift loop O(number of bits) = O(log n); Kernighan O(number of set bits); popcount O(1). Space O(1).
Q3: Is n a power of two?
Problem. For each integer n (up to 10¹⁸, so long long) print yes if n is a power of two (1, 2, 4, 8, ...), else no.
| Input | Output |
|---|---|
| 1 | yes (2⁰) |
| 8 | yes |
| 12 | no |
| 0 | no |
| 1024 | yes |
| −8 | no |
| 1152921504606846976 | yes (2⁶⁰) |
| 1152921504606846977 | no |
The obvious attempt: divide by 2 while even
#include <iostream>
using namespace std;
bool isPow2(long long n) {
while (n % 2 == 0)
n /= 2;
return n == 1;
}
int main() {
long long n;
while (cin >> n)
cout << n << (isPow2(n) ? " yes\n" : " no\n");
return 0;
}
Input 1 8 12 1024:
1 yes
8 yes
12 no
1024 yes
Input 0: Time Limit Exceeded. 0 is even and 0 / 2 = 0, so the loop never ends.
The one-line idea: exactly one switch on
A power of two has exactly one set bit (8 = 1000). n & (n - 1) removes the lowest set bit, so the result is 0 exactly when that was the only one: 8 & 7 = 1000 & 0111 = 0, but 12 & 11 = 1100 & 1011 = 1000 ≠ 0. Add n > 0 for 0 and the negatives.
Attempt: typed without brackets
#include <iostream>
using namespace std;
bool isPow2(long long n) {
return n > 0 && n & (n - 1) == 0;
}
int main() {
long long n;
while (cin >> n)
cout << n << (isPow2(n) ? " yes\n" : " no\n");
return 0;
}
Compiler output:
main.cpp: In function 'bool isPow2(long long int)':
main.cpp:5:33: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
5 | return n > 0 && n & (n - 1) == 0;
| ~~~~~~~~^~~~
Input 1 8 12 0 1024 -8 1152921504606846976 1152921504606846977:
1 yes
8 no
12 no
0 no
1024 no
-8 no
1152921504606846976 no
1152921504606846977 no
Why: precedence. == binds tighter than &, so C++ reads n & ((n - 1) == 0). For n = 8: (7 == 0) is 0, and 8 & 0 is 0 → no. Only n = 1 says yes, by luck ((0 == 0) is 1, 1 & 1 is 1). The -Wparentheses warning pointed straight at it.
Fix: brackets
#include <iostream>
using namespace std;
bool isPow2(long long n) {
return n > 0 && (n & (n - 1)) == 0;
}
int main() {
long long n;
while (cin >> n)
cout << n << (isPow2(n) ? " yes\n" : " no\n");
return 0;
}
Same input:
1 yes
8 yes
12 no
0 no
1024 yes
-8 no
1152921504606846976 yes
1152921504606846977 no
No warning, every answer correct. O(1) time and space.
The 1 << 31 trap: making powers of two
#include <iostream>
using namespace std;
int main() {
for (int i = 28; i <= 34; i++) {
long long p = 1 << i;
cout << "2^" << i << " = " << p << "\n";
}
return 0;
}
Output:
2^28 = 268435456
2^29 = 536870912
2^30 = 1073741824
2^31 = -2147483648
2^32 = 1
2^33 = 2
2^34 = 4
Why: the literal 1 is an int, so 1 << i is computed in 32-bit int before it is stored in the long long. 1 << 31 lands on the sign bit (−2147483648), and shifting an int by 32 or more is undefined behaviour: this machine happened to use the shift count modulo 32, so 1 << 32 gave 1. No warning, because i is a variable.
Fix: 1LL << i
#include <iostream>
using namespace std;
int main() {
for (int i = 28; i <= 34; i++) {
long long p = 1LL << i;
cout << "2^" << i << " = " << p << "\n";
}
return 0;
}
Output:
2^28 = 268435456
2^29 = 536870912
2^30 = 1073741824
2^31 = 2147483648
2^32 = 4294967296
2^33 = 8589934592
2^34 = 17179869184
1LL is a long long 1, so the shift happens in 64 bits: safe up to 1LL << 62 (1ULL << 63 for an unsigned long long).
Complexity summary
| Program | Time | Extra space |
|---|---|---|
| to binary, divide by 2 | O(log n) | O(log n) |
to binary, bitset<32> |
O(32) = O(1) | O(32) |
set bits, n & 1 and shift |
O(number of bits) | O(1) |
set bits, n &= n - 1 (Kernighan) |
O(number of set bits) | O(1) |
set bits, __builtin_popcount |
O(1) | O(1) |
| power of two, divide loop | O(log n) | O(1) |
power of two, n > 0 && (n & (n - 1)) == 0 |
O(1) | O(1) |
A number n has about log₂ n bits (an int at most 32), so "walk every bit" is O(log n).
Common mistakes (and the real results)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
print n % 2 while dividing |
13 → 1011 |
last bit comes out first | put each bit in front |
| no case for 0 | empty line | the loop never runs | if (n == 0) return "0"; |
bitset<8>(300) |
00101100 (44) |
300 needs 9 bits | bitset<32> |
int n = -1; while (n) n >>= 1; |
Time Limit Exceeded | the sign bit is copied in | unsigned int |
__builtin_popcount(longLongValue) |
32 instead of 40 |
cut to 32 bits | __builtin_popcountll |
| divide by 2 while even, n = 0 | Time Limit Exceeded | 0 / 2 = 0 forever | n > 0 first |
n & (n - 1) == 0 |
warning [-Wparentheses], 8 → no |
== binds tighter than & |
(n & (n - 1)) == 0 |
long long p = 1 << i; |
2^31 = -2147483648, 2^32 = 1 |
the shift is done in int (UB) |
1LL << i |
Your turn: the single number (solution)
Problem. Every number in a list appears twice except one. Find it with O(1) extra memory. Input: n, then n numbers.
Idea: XOR. a ^ a = 0, a ^ 0 = a, and XOR does not care about order, so XOR-ing everything cancels every pair and leaves the lonely number.
#include <iostream>
using namespace std;
int main() {
int n;
while (cin >> n) {
int result = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
result ^= x; // pairs cancel: a ^ a = 0
}
cout << result << "\n";
}
return 0;
}
Input 5 / 4 1 2 1 2 / 3 / 7 3 7 / 1 / 5:
4
3
5
Time O(n), space O(1).
Practice questions (with solutions)
1. Binary string back to a number ("1101" → 13). Read left to right: for each bit, value = value * 2 + bit (shift left, add the new bit).
Solution
#include <iostream>
#include <string>
using namespace std;
long long fromBinary(const string& s) {
long long value = 0;
for (char c : s)
value = value * 2 + (c - '0'); // shift left, add the new bit
return value;
}
int main() {
string s;
while (cin >> s)
cout << s << " -> " << fromBinary(s) << "\n";
return 0;
}
Input 1101 0 11111111 100101100:
1101 -> 13
0 -> 0
11111111 -> 255
100101100 -> 300
The library way: stoll(s, nullptr, 2) or bitset<64>(s).to_ullong().
2. Swap two numbers with XOR (no third variable).
Solution
#include <iostream>
using namespace std;
int main() {
int a = 13, b = 6;
a ^= b;
b ^= a; // b = b ^ (a ^ b) = a
a ^= b; // a = (a ^ b) ^ a = b
cout << a << " " << b << "\n";
return 0;
}
6 13
A classic interview trick; in real code use std::swap(a, b), which is clearer. (If a and b are the same variable, the XOR swap sets it to 0.)
3. Count the bits of every i from 0 to n in O(n): bits[i] = bits[i >> 1] + (i & 1). i >> 1 is i without its last bit, already computed.
Solution
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> bits(n + 1, 0);
for (int i = 1; i <= n; i++)
bits[i] = bits[i >> 1] + (i & 1); // i without its last bit, plus the last bit
for (int i = 0; i <= n; i++)
cout << bits[i] << (i == n ? "\n" : " ");
return 0;
}
Input 8:
0 1 1 2 1 2 2 3 1
Mini project: a bit inspector
For each number: its 16-bit pattern, its set bits, whether it is a power of two, and its lowest set bit n & -n (in two's complement, -n is ~n + 1, which keeps only the lowest 1 in common with n).
#include <iostream>
#include <bitset>
using namespace std;
int main() {
long long n;
while (cin >> n) {
unsigned long long u = n;
cout << n << ": binary " << bitset<16>(u)
<< ", set bits " << __builtin_popcountll(u)
<< ", " << (n > 0 && (n & (n - 1)) == 0 ? "power of two" : "not a power of two")
<< ", lowest set bit " << (n & -n) << "\n";
}
return 0;
}
Input 13 64 0 96 1024:
13: binary 0000000000001101, set bits 3, not a power of two, lowest set bit 1
64: binary 0000000001000000, set bits 1, power of two, lowest set bit 64
0: binary 0000000000000000, set bits 0, not a power of two, lowest set bit 0
96: binary 0000000001100000, set bits 2, not a power of two, lowest set bit 32
1024: binary 0000010000000000, set bits 1, power of two, lowest set bit 1024
Quick quiz
#include <iostream>
using namespace std;
int main() {
int n = 22; // 10110
cout << (n & 1) << " "
<< (n >> 1) << " "
<< (n & (n - 1)) << "\n";
return 0;
}
(A) 0 11 20 (B) 1 11 20 (C) 0 44 21 (D) 0 11 16
Answer
(A) 0 11 20. 22 = 10110: the last bit is 0; 22 >> 1 = 1011 = 11; 22 & 21 = 10110 & 10101 = 10100 = 20 (the lowest set bit removed).
Output:
0 11 20
Interview questions
- How do you check if a number is odd using bits?
n & 1is 1 for odd numbers. - What does
n & (n - 1)do? It clears the lowest set bit. - Check a power of two in O(1).
n > 0 && (n & (n - 1)) == 0. - Count set bits efficiently. Kernighan's loop (one step per set bit) or
__builtin_popcount/std::popcount(C++20). - How are negative integers stored? Two's complement: flip the bits of |n| and add 1; the top bit is the sign.
- Why is
1 << 31dangerous?1is anint; the result hits the sign bit, and shifting by ≥ 32 is undefined behaviour. Use1LL << ior1u << i. - Why use unsigned types for bit manipulation? Shifts and overflow are fully defined, and right shifts bring in zeros.
- Find the single number when every other appears twice. XOR everything.
- What is the precedence of
&compared with==? Lower: always bracket bitwise expressions.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Bit | A binary digit: 0 or 1 | one light switch |
| Binary (base 2) | Writing numbers with only 0 and 1; places worth 1, 2, 4, 8, ... | 13 = 1101 |
| Decimal (base 10) | The everyday number system; places worth 1, 10, 100, ... | 13 |
| Number base | How many digits a system uses | base 2, base 10, base 16 |
| Set bit | A bit that is 1 | 1101 has 3 set bits |
| Popcount | Population count: the number of set bits | popcount(255) = 8 |
| Power of two | 2ᵏ: exactly one set bit | 1, 2, 4, 1024 |
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 |
Left shift << |
Move bits left, × 2 per place | 1 << 3 = 8 |
Right shift >> |
Move bits right, ÷ 2 per place | 12 >> 2 = 3 |
std::bitset<N> |
A fixed row of N bits, printable as 0s and 1s | bitset<8>(13) → 00001101 |
| Two's complement | How negative integers are stored: flip the bits, add 1 | −5 = 11111011 (8 bits) |
| Sign bit | The top bit of a signed integer: 1 means negative | bit 31 of an int |
| Unsigned type | An integer type with no sign, only 0 and up | unsigned int |
| Arithmetic shift | A right shift that copies the sign bit in | -1 >> 1 == -1 on g++ |
| Kernighan's trick | Clear the lowest set bit with n &= n - 1 |
12 → 8 → 0 |
__builtin_popcount |
GCC/Clang built-in: set bits of an unsigned int (ll version for 64 bits) |
__builtin_popcount(13) = 3 |
| Operator precedence | Which operator is applied first | == before & |
-Wparentheses |
A g++ warning for confusing operator mixes without brackets | n & (n - 1) == 0 |
1LL |
The number 1 as a long long |
1LL << 40 |
| Undefined behaviour (UB) | Code the standard gives no meaning; anything may happen | 1 << 32 on an int |
| Time Limit Exceeded (TLE) | The judge stopped a program that ran too long | 8 seconds here |
| O(log n) | Work grows with the number of digits/bits | 32 steps for any int |
Summary
- Binary is a row of switches worth 1, 2, 4, 8, ... Dividing by 2 gives the bits last first: put each new bit in front, and handle 0.
bitset<32>shows anyint, negatives in two's complement. - Count set bits with an unsigned shift loop, with
n &= n - 1(one step per set bit), or with__builtin_popcount(popcountllforlong long). - Power of two:
n > 0 && (n & (n - 1)) == 0. Always bracket bitwise operators (==binds tighter than&). 1 << iis computed inint: use1LL << i.
Next episode: String questions I: reverse a string with two pointers and std::reverse, a palindrome check that ignores case and spaces, counting vowels and words, and the cin >> vs getline trap.