C Evil Number Program

What Is an Evil Number?

An evil number is a nonnegative integer whose binary form has an even number of 1 bits. That count is called the popcount (Hamming weight). An odd popcount means the number is odious.

n is evil  ⇔  (count of 1-bits in binary n) is even

Examples:
  15 → 1111 → 4 ones → evil
   7 → 111  → 3 ones → odious
   0 → 0    → 0 ones → evil
   3 → 11   → 2 ones → evil

How to Check an Evil Number in C

Four clear steps — then pick a teaching loop or Brian Kernighan’s popcount.

1. Require n >= 0 (this page rejects negatives).
2. Count how many 1 bits appear in binary n.
3. If that count is even, n is evil; otherwise it is odious.
4. Use a divide-by-2 loop to learn the idea, or Kernighan’s n & (n - 1) trick for a shorter count.

Pseudocode

function IsEvil(n):
    if n < 0:
        return false

    ones = 0
    while n > 0:
        if (n mod 2) == 1:
            ones = ones + 1
        n = n / 2

    return (ones mod 2) == 0

Cheat Sheet

Keep these facts handy while writing the program.

Live Preview

Enter a nonnegative integer to see its binary form, popcount, and verdict.

n = 15
Binary = 1111
Ones = 4 (even)
Verdict: EVIL NUMBER

Worked Walkthrough — n = 15

Peel bits with % 2, count the ones, then check parity.

15 in binary = 1111

Step 1: 15 % 2 = 1 → ones = 1; n = 7
Step 2:  7 % 2 = 1 → ones = 2; n = 3
Step 3:  3 % 2 = 1 → ones = 3; n = 1
Step 4:  1 % 2 = 1 → ones = 4; n = 0

ones = 4 → even → 15 is evil

C Programs

Start with the divide-by-2 loop so you can show each bit. Then use Brian Kernighan’s popcount when you want a shorter count of set bits.

#include <stdio.h>

int is_evil(int n)
{
    int ones = 0;

    if (n < 0)
    {
        return 0;
    }

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

    return ones % 2 == 0;
}

int main(void)
{
    int number = 15;
    if (is_evil(number))
        printf("%d is an Evil Number.\n", number);
    else
        printf("%d is not an Evil Number.\n", number);
    return 0;
}

15 is an Evil Number.

#include <stdio.h>

int popcount(unsigned int n)
{
    int ones = 0;
    while (n > 0)
    {
        n &= (n - 1); /* clear lowest set bit */
        ones++;
    }
    return ones;
}

int is_evil(int n)
{
    if (n < 0)
    {
        return 0;
    }
    return popcount((unsigned int)n) % 2 == 0;
}

int main(void)
{
    printf("%s\n", is_evil(15) ? "15 is evil" : "15 is odious");
    printf("%s\n", is_evil(7) ? "7 is evil" : "7 is odious");
    printf("%s\n", is_evil(0) ? "0 is evil" : "0 is odious");
    return 0;
}

15 is evil
7 is odious
0 is evil

Time and Space Complexity

For a 32-bit int, the divide loop runs at most 32 steps. Kernighan runs once per set bit.

Key Takeaways