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

Number questions IV

decimal to binary and backcount set bitscheck power of two with n & (n-1)

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-negative int).
  • '0' + n % 2 is 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: if n > 0 is false, the right side is never evaluated, so n - 1 can't overflow for INT_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

  1. How do you check whether n is a power of two in O(1)? n > 0 && (n & (n - 1)) == 0.
  2. What does n & (n - 1) do? It switches off the lowest set bit.
  3. How do you count set bits efficiently? Brian Kernighan's loop: while (u) { u &= u - 1; count++; }, one turn per set bit.
  4. 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).
  5. How is -1 stored in a 32-bit int? In two's complement: all 32 bits set.
  6. How do you get, set, clear and toggle bit k? n & (1u << k), n | (1u << k), n & ~(1u << k), n ^ (1u << k).
  7. Why might if (x & 1 == 0) be wrong? == binds tighter than &; write (x & 1) == 0.
  8. 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 % 2 is the last bit and n / 2 drops it; bits come out backwards, so keep them in a char array and print in reverse.
  • Binary to decimal: value = value * 2 + bit, in an unsigned 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 with n > 0 && (n & (n - 1)) == 0.
  • Brackets around & comparisons; -Wall warns 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).