SyntaxPilot
Courses/C++ Coding Questions/Lesson 4
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

C++ Coding Questions · Lesson 4 of 30

Bits and number bases

decimal to binary (bitset)count set bits (__builtin_popcount)power of two with n & (n-1)the 1 << 31 trap

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>); cout prints 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 = 100101100 needs 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

  1. How do you check if a number is odd using bits? n & 1 is 1 for odd numbers.
  2. What does n & (n - 1) do? It clears the lowest set bit.
  3. Check a power of two in O(1). n > 0 && (n & (n - 1)) == 0.
  4. Count set bits efficiently. Kernighan's loop (one step per set bit) or __builtin_popcount / std::popcount (C++20).
  5. How are negative integers stored? Two's complement: flip the bits of |n| and add 1; the top bit is the sign.
  6. Why is 1 << 31 dangerous? 1 is an int; the result hits the sign bit, and shifting by ≥ 32 is undefined behaviour. Use 1LL << i or 1u << i.
  7. Why use unsigned types for bit manipulation? Shifts and overflow are fully defined, and right shifts bring in zeros.
  8. Find the single number when every other appears twice. XOR everything.
  9. 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 any int, 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 (popcountll for long long).
  • Power of two: n > 0 && (n & (n - 1)) == 0. Always bracket bitwise operators (== binds tighter than &).
  • 1 << i is computed in int: use 1LL << 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.