SyntaxPilot
Courses/C Coding Questions/Lesson 25
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 25 of 30

Bit manipulation questions

swap without a temp (XOR, and its trap)odd/even with &set/clear/toggle the k-th bitthe single number that appears once

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 << k is a single 1 at bit k.
  • Use unsigned for bit work: shifts and ~ behave simply, and there's no sign bit. 1 << 31 with a signed int overflows (undefined behaviour); 1u << 31 is 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, but a + b can 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

  1. How do you check odd or even without %? n & 1 (1 = odd).
  2. Set, clear, toggle and check bit k? n | (1u << k), n & ~(1u << k), n ^ (1u << k), (n >> k) & 1u.
  3. Why does n & 1 << k == 0 not work? == has higher precedence than &.
  4. 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.
  5. Why prefer a temp in real code? Clear, always correct, and just as fast.
  6. Find the element that appears once when every other appears twice? XOR all of them: O(n) time, O(1) space.
  7. What does x & (x - 1) do? Clears the lowest set bit; x & (x - 1) == 0 means x is a power of two (or 0).
  8. What does x & -x (or x & (~x + 1)) give? The lowest set bit alone.
  9. Is right-shifting a negative number defined? It's implementation-defined (gcc does an arithmetic shift, copying the sign bit). Use unsigned.
  10. Why is 1 << 31 dangerous? It overflows a 32-bit signed int: undefined behaviour. Use 1u << 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 & 1 tells odd from even for any sign; n % 2 == 1 fails for negatives.
  • A mask 1u << k touches 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).