Check Evil Number in C

Beginner
⏱️ 8 min read
📚 Updated: May 2026
🎯 2 Code Examples
Popcount parity

What you’ll learn

  • The definition of an evil number: even count of 1-bits in binary (nonnegative integers).
  • A bitwise popcount on unsigned plus a division-by-two variant for a small range.
  • Live preview, edge cases (0, negatives in C), and links to the next interview topic.

Overview

Evil numbers classify integers by the parity of their Hamming weight in base 2. The check is: count 1 bits, then test whether that count is divisible by 2.

Two programs

One value (15) and evils in 1–10 matching the classic output.

Live preview

Nonnegative safe integers; shows popcount and evil vs odious.

Rigor

unsigned shifts for bitwise counting; nonnegative definition.

Prerequisites

Loops, % and /, and basic bitwise & and >>.

  • #include <stdio.h>, int main(void), printf.
  • Comfort reading small binary expansions (e.g. 15 = 11112 in prose as 1111).

What is an evil number?

A nonnegative integer n is evil if the binary representation of n contains an even number of 1 digits. If the count is odd, n is odious.

This is pure bit-level parity, unrelated to divisibility by 2 in decimal. The smallest evil numbers are 0, 3, 5, 6, 9, 10, 12, 15, ….

Evil popcount(n) % 2 == 0
Odious popcount(n) % 2 == 1
Zero evil (0 ones)

Hamming weight

Write n = ∑ b_i 2^i with b_i ∈ {0,1}. The Hamming weight is s_2(n) = ∑ b_i. Then n is evil iff s_2(n) ≡ 0 (mod 2).

15

15 = 8+4+2+1 = 11112, so s_2(15)=4 and 15 is evil.

Intuition

15 Evil
Binary
1111 — four ones
7 Odious
Binary
111 — three ones

Takeaway: flip one bit toggles parity, so consecutive numbers are not always both evil or both odious.

Live preview

Nonnegative integers in the JavaScript safe range. Popcount matches the division-by-two mental model.

Try 0, 7, or 10.

Live result
Press “Classify” to see popcount and verdict.

Algorithm

Goal: decide whether n ≥ 0 has an even number of 1-bits.

Popcount

Repeatedly peel the least significant bit with n & 1u and n >>= 1 on unsigned, or emulate binary digits with n % 2 and n /= 2 for n ≥ 0.

Parity of the count

Evil iff count % 2 == 0. Range listing applies the predicate per index.

📜 Pseudocode

Pseudocode
function popcount(n):  // assume n >= 0
    c = 0
    while n > 0:
        c += (n mod 2)
        n = floor(n / 2)
    return c

function isEvil(n):
    return (popcount(n) mod 2) = 0
1

Bitwise popcount on unsigned

Same verdict as the reference for 15. Uses unsigned int so right shifts are well-defined while counting bits.

c
#include <stdio.h>

int count_set_bits_u(unsigned int n) {
    int count = 0;

    while (n != 0u) {
        count += (int)(n & 1u);
        n >>= 1;
    }

    return count;
}

int is_evil_u(unsigned int n) {
    return count_set_bits_u(n) % 2 == 0;
}

int main(void) {
    int number = 15;

    if (number < 0) {
        printf("Evil/odious here are defined for nonnegative n only.\n");
        return 0;
    }

    if (is_evil_u((unsigned int)number)) {
        printf("%d is an Evil Number.\n", number);
    } else {
        printf("%d is not an Evil Number.\n", number);
    }

    return 0;
}

Explanation

count_set_bits_u clears bits from the right until the value is zero. 15 has four 1 bits, so the count is even.

2

Evil numbers in [1, 10]

Matches the reference output: 3 5 6 9 10. Uses the division-and-modulo loop (equivalent for nonnegative n).

c
#include <stdio.h>

int is_evil_nonneg(int num) {
    int ones = 0;

    while (num > 0) {
        if (num % 2 == 1) {
            ones++;
        }
        num /= 2;
    }

    return ones % 2 == 0;
}

int main(void) {
    printf("Evil numbers in the range 1 to 10:\n");

    for (int i = 1; i <= 10; ++i) {
        if (is_evil_nonneg(i)) {
            printf("%d ", i);
        }
    }

    printf("\n");
    return 0;
}

Explanation

Each iteration reads the least significant binary digit of num via num % 2, then shifts right in decimal space with num /= 2.

Optimization

Kernighan trick. Clear the lowest set bit with n &= n - 1 on unsigned; each step removes one 1, so the loop runs once per set bit.

Built-ins. GCC and Clang provide __builtin_popcount and __builtin_parity for fixed-width integers when you can depend on those compilers.

Interview: define the nonnegative convention, mention 0, and prefer unsigned for portable bit walks.

❓ FAQ

A nonnegative integer n is evil if its base-2 representation contains an even number of digit 1 (equivalently, the Hamming weight or population count is even).
If the count of 1-bits is odd, n is called odious. Every nonnegative integer is either evil or odious.
Yes. Zero has no 1-bits, so the count is 0, which is even.
15 is 1111 in binary: four 1-bits. Four is even, so 15 is evil.
Right-shifting a negative signed int is implementation-defined in C. Casting to unsigned makes the bit walk well-defined for the usual two's complement representation.
Counting bits for one n costs O(log n) in the value of n (number of bits). Scanning [a,b] costs O((b-a+1) log U) where U is the largest value in the range.

🔄 Input / output examples

Change number in Example 1 or extend the loop bounds in Example 2.

nBinaryOnesVerdict
000Evil
3112Evil
71113Odious
1511114Evil

Edge cases and pitfalls

The mathematical definition is for nonnegative integers. Signed-negative bit patterns depend on representation; do not mix naive >> on negative int with portability expectations.

Zero

n = 0

Popcount 0 is even, so 0 is evil.

Sign

Negative int

Example 1 rejects n < 0 for clarity. If you must classify negatives, cast to a chosen-width unsigned type explicitly and document the mapping.

Width

Leading zeros

Infinitely many leading zeros do not change the finite count of 1 bits in the minimal binary form.

Range

1 ≤ i ≤ 10

Example 2 omits 0 by loop start; include 0 if the problem asks for nonnegative evils in the interval.

⏱️ Time and space complexity

OperationTimeExtra space
Popcount of nO(log n) bit stepsO(1)
Kernighan variantO(popcount(n))O(1)
Scan [a,b]O((b-a+1) log U)O(1)

Here U = max(|n|, 1) for a single value, or the largest value in the scanned range.

Summary

  • Definition: evil iff the binary digit sum is even; otherwise odious.
  • Code: bitwise on unsigned or % 2 with /= 2 for n ≥ 0.
  • Watch-outs: define nonnegative scope; avoid signed right-shift ambiguity.
Did you know?

The complementary class is odious numbers: nonnegative integers whose binary expansion has an odd number of 1 bits. The name “evil” vs “odious” is mathematical wordplay, not moral judgment.

About the author

Mari Selvan M P
Mari Selvan M P 🔗

Developer, cloud engineer, and technical writer

  • Experience 12 years building web and cloud systems
  • Focus Full Stack Development, AWS, and Developer Education

I write practical tutorials so students and working developers can learn by doing—from databases and APIs to deployment on AWS.

AWS Certified Developer – Associate (Credly)

8 people found this page helpful

C Program to Check Even Number C Program to Find Factorial of a Number