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 <iostream>, int main(), std::cout.
  • 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 <iostream>

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

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

    return count;
}

bool isEvil(unsigned int n) {
    return countSetBits(n) % 2 == 0;
}

int main() {
    int number = 15;

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

    if (isEvil((unsigned int)number)) {
        std::cout << number << " is an Evil Number.\n";
    } else {
        std::cout << number << " is not an Evil Number.\n";
    }

    return 0;
}

Explanation

countSetBits 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 <iostream>

bool isEvilNonNegative(int num) {
    int ones = 0;

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

    return ones % 2 == 0;
}

int main() {
    std::cout << "Evil numbers in the range 1 to 10:\n";

    for (int i = 1; i <= 10; ++i) {
        if (isEvilNonNegative(i)) {
            std::cout << i << " ";
        }
    }

    std::cout << "\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 in C++.

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