Definition
Even popcount
Even number of 1-bits → evil; odd → odious.
Check Evil Number in Java
Overview
What You’ll Learn
An evil number has an even count of 1 bits in binary; an odd count means odious. This tutorial covers Hamming weight, Integer.bitCount, manual loops, a live preview, worked Java examples, edge cases, and complexity.
Classic 15
1111
Four ones (even) so 15 is evil.
Integer.bitCount
Built-in
Fastest readable Java one-liner for popcount.
Zero Is Evil
0 ones
Zero has popcount 0, and 0 is even.
Live Preview
Try any n
See popcount and evil/odious instantly.
O(bits)
Single check
Kernighan can reduce work to O(popcount).
Introduction
Evil numbers are nonnegative integers whose binary form has an even number of 1 bits. If the count is odd, the number is called odious. Example: 15 is 1111 (four ones) → evil; 7 is 111 (three ones) → odious.
The count of 1-bits is the Hamming weight (popcount). Evil means even Hamming weight; odious means odd.
Why it matters?
It turns even/odd thinking into bit-level parity — a bridge from simple modulo checks to popcount and bit tricks.
Key Highlights
Even Ones
Only the parity of the 1-bit count matters.
Zero Counts
0 is evil (zero ones is even).
Odious Pair
Odd popcount means odious, not evil.
Nonnegative
This page scopes the definition to n ≥ 0.
In short: count the 1-bits; if that count is even, n is evil.
Foundation
📝 Problem & Approach
Given a nonnegative integer n, decide whether its binary popcount is even.
java
// 15 → 1111 → 4 ones → evil
// 7 → 111 → 3 ones → odious
// 0 → 0 → 0 ones → evilInputs & Outputs
| Item | Type | Description |
|---|---|---|
n | int | Nonnegative integer (this page rejects negatives). |
| Return / print | bool / text | true if n is evil (even popcount). |
Minimal workflow
Pseudocode
function isEvil(n): // n >= 0
ones = count_ones_in_binary(n)
return (ones mod 2) == 0Method comparison
| Method | Idea | Notes |
|---|---|---|
Integer.bitCount | Built-in popcount, then % 2 | Best default in modern Java |
| Divide by 2 | % 2 / // 2 to read bits | Great for teaching binary |
| Kernighan | n &= n - 1 clears one set bit | O(popcount) steps |
Cheat Sheet
⚡ Quick Reference
| Goal | Pattern |
|---|---|
| Popcount | Integer.bitCount(n) |
| Evil test | Integer.bitCount(n) % 2 == 0 |
| Binary string | Integer.toBinaryString(n) |
| Clear lowest set bit | n &= n - 1 |
| Classic evil | 0, 3, 5, 6, 9, 10, 15 |
| Classic odious | 1, 2, 4, 7, 8 |
Compare
📋 Evil vs Odious vs Even
Related parity ideas — different levels of abstraction.
Evil
popcount evenEven count of 1-bits
Odious
popcount oddOdd count of 1-bits
Even (decimal)
n % 2 == 0Value parity, not bit count
Interview tip
say nonnegativeScope the definition before coding
Context
When This Problem Shows Up
Reach for evil/odious checks when popcount parity matters.
Interview bit warm-ups
Tests binary understanding without heavy algorithms.
After even-number
Natural next step: parity of bits instead of the value.
Range listing tasks
Print all evil numbers in 1…N for small N.
Teaching popcount
Makes Hamming weight concrete with 15 vs 7.
Not for negatives by default
State nonnegative scope before coding.
Key benefit: one short boolean check that teaches popcount parity and pairs cleanly with even/odd value parity.
Interactive
🔮 Live Preview
Nonnegative integers only for this definition (within JavaScript safe range).
Hands-On
Examples Gallery
Three complete Java programs — Integer.bitCount, range scan with division, and Kernighan popcount. Click View Output to reveal sample console results.
📚 Getting Started
Built-in popcount with a parity check.
Example 1 — Single Check with Integer.bitCount
Java has built-in Integer.bitCount for integers.
java
public class Main {
static boolean isEvil(int n) {
if (n < 0) {
return false;
}
return Integer.bitCount(n) % 2 == 0;
}
public static void main(String[] args) {
int number = 15;
if (isEvil(number)) {
System.out.println(number + " is an Evil Number.");
} else {
System.out.println(number + " is not an Evil Number.");
}
}
}How It Works
Integer.bitCount(15) is 4, and 4 is even — so 15 is evil. Negatives return false under this page’s nonnegative policy.
⚡ Range Output
Manual bit reading by dividing by 2.
Example 2 — Evil Numbers in [1, 10]
Range output matches the classic sample.
java
public class Main {
static boolean isEvilByDivision(int num) {
int ones = 0;
while (num > 0) {
if (num % 2 == 1) {
ones++;
}
num /= 2;
}
return ones % 2 == 0;
}
public static void main(String[] args) {
System.out.println("Evil numbers in the range 1 to 10:");
for (int i = 1; i <= 10; i++) {
if (isEvilByDivision(i)) {
System.out.print(i + " ");
}
}
}
}How It Works
The loop counts ones in binary by repeatedly taking % 2 and dividing by 2. Use for (int i = 1; i <= 10; i++) for an inclusive end.
⚙️ Kernighan Style
Clear one set bit per step for O(popcount) work.
Example 3 — Kernighan Set-Bit Loop
n &= n - 1 removes the lowest set bit each iteration.
java
public class Main {
static int popcountKernighan(int n) {
int ones = 0;
while (n != 0) {
n &= n - 1;
ones++;
}
return ones;
}
static boolean isEvilKernighan(int n) {
if (n < 0) {
return false;
}
return popcountKernighan(n) % 2 == 0;
}
public static void main(String[] args) {
int[] samples = {15, 7, 0, 3};
for (int n : samples) {
String label = isEvilKernighan(n) ? "evil" : "odious";
System.out.println(n + ": " + label + " (ones=" + popcountKernighan(n) + ")");
}
}
}How It Works
Each n &= n - 1 clears exactly one set bit, so the loop runs once per 1-bit. Prefer Integer.bitCount in production; mention Kernighan as an interview follow-up.
🧠 How the Algorithm Decides
1
Count ones
Use Integer.bitCount, a divide-by-2 loop, or Kernighan.
Popcount
2
Check count parity
Even ones → evil; odd ones → odious.
Parity
3
Reuse in a range
Apply the same helper for each value in 1…N.
Scan
=
Evil or odious
Even popcount → evil; otherwise odious.
Trace
🔎 Worked Walkthrough — n = 15
Trace popcount for the classic evil example.
| Step | Binary / action | Ones so far |
|---|---|---|
| 1 | 15 = 1111 | — |
| 2 | Integer.bitCount / four 1s | 4 |
| 3 | 4 % 2 == 0 | Evil |
For contrast, 7 = 111 has 3 ones → odious.
Use Cases
Where evil/odious checks show up beyond the interview prompt.
1. Interview Warm-Ups
Popcount parity without heavy bit algorithms.
Example: write isEvil(n).
2. Teaching Binary
Connect decimal values to 1-bit counts.
Example: chalkboard 15 vs 7.
3. After Even Number
Contrast value parity with bit-count parity.
Example: 6 is even and evil.
4. Range Filters
List evil numbers in a classroom interval.
Example: 1 to 10 → 3 5 6 9 10.
5. Bit Trick Follow-Ups
Kernighan loop and hardware popcount.
Example: n &= n - 1.
6. Zero Trivia
Confirm 0 is evil before harder bit problems.
Example: ask “is zero evil?” first.
Pro Tip: say “evil = even popcount; odious = odd” before coding — it prevents mixing with decimal even/odd.
Advantages
Why this pattern works well in interviews and classwork.
1. Clear Definition
One sentence: even count of 1-bits.
2. Multiple Styles
Integer.bitCount, divide-by-2, and Kernighan all work.3. Famous Test Cases
15 vs 7 makes verification quick.
4. Rich Follow-Ups
Odious, zero, and Kernighan are natural next questions.
Pro Tip: lead with Integer.bitCount; offer a manual loop if asked to avoid builtins.
Usage Tips
Small habits that keep evil-number solutions interview-ready.
1. State Nonnegative Scope
Say n ≥ 0 before coding.
2. Call Out Zero
State that 0 is evil (zero ones).
3. Spot-Check 15 and 7
Evil and odious classics catch parity mistakes.
4. Prefer Integer.bitCount
Use the builtin unless asked for a manual loop.
5. Name Odious Too
Mention the odd-popcount complement in interviews.
Pro Tip: do not confuse “evil” with “even value” — 7 is odd but odious; 6 is even and evil.
Common Pitfalls
Mistakes that commonly break evil-number solutions.
1. Confusing with Decimal Even
Checking
n % 2 == 0instead of popcount parity.→ Count 1-bits, then check that count’s parity.
2. Calling Zero Odious
Thinking zero has no classification.
→ Zero ones is even → evil.
3. Silent Negatives
Applying popcount to negatives without a policy.
→ Reject or define two’s-complement rules explicitly.
4. Counting All Bits Including Leading Zeros
Padding to a fixed width and counting zeros as ones.
→ Only count 1-bits in the canonical nonnegative form.
5. Exclusive Range End
Using
i < 10when 10 should be included.→ Use
i <= 10for inclusive 1…10.
Edge Cases
Most definitions use nonnegative integers. Keep that policy clear in your code.
Zero
n = 0
Evil because ones count is 0 (even).
Negative
Policy needed
This page rejects negatives for clarity.
Representation
Binary form
Use canonical nonnegative binary representation.
Range
Include bounds
Use inclusive loops when required by the question.
Odious
Odd popcount
7, 1, 2, 4, 8 are common odious examples.
Big ints
Built-in OK
Arbitrary-precision ints still support Integer.bitCount.
Math
⚖️ Facts Worth Knowing
Handy follow-ups interviewers sometimes ask.
- Hamming weight. Evil numbers are exactly those with even Hamming weight.
- Odious. The complement class: odd number of 1-bits.
- Zero. popcount(0) = 0 → evil.
- Not value parity. An even decimal can be odious (e.g. 2 = 102).
Drill
🎯 Practice Problems
Try these variations to lock in the pattern.
1. Classify classics
- 0, 3, 15 → evil
- 1, 7, 8 → odious
2. Match all three styles
- Integer.bitCount vs divide vs Kernighan
- Assert identical booleans
3. Range 1 to 20
- List all evil numbers
- Also list odious separately
4. Show the binary
- Print Integer.toBinaryString(n) and popcount
- Then the evil/odious label
Important
Notes
- Rule: evil means an even number of 1-bits.
- Code: use
Integer.bitCountor manual bit loops. - Remember: 0 is evil; negatives need an explicit policy.
- Single check is O(bits); Kernighan is O(popcount).
Quick Takeaway: count the 1-bits; if that count is even, the number is evil.
Analysis
⏱️ Time and Space Complexity
| Operation | Time | Extra space |
|---|---|---|
| Single number popcount | O(bits) | O(1) |
| Kernighan method | O(popcount) | O(1) |
| Range scan | O(range · bits) | O(1) |
🎉 Conclusion
An evil number has an even count of 1-bits in binary; an odd count means odious. Prefer Integer.bitCount, keep a nonnegative policy, and remember that zero is evil.
Practice the three examples above, then continue to factorial for a classic loop-and-product warm-up.
Do not confuse popcount parity with decimal even/odd — and mention odious as the complement.
Pro Tips
💡 Best Practices
✅ Do
- Define nonnegative scope first
- Prefer
Integer.bitCount - Test 0, 15, and 7
- Name odious as the complement
- Mention Kernighan as a follow-up
❌ Don’t
- Use
n % 2as the evil test - Call zero odious
- Ignore negatives without a policy
- Count padded leading zeros as ones
- Drop inclusive range ends
Summary
Key Takeaways
Knowledge Unlocked
Five things to remember about evil numbers
Check popcount parity the interview-friendly way.
5
Core concepts 01
Rule
Even 1-bits
Definition 02
Zero
0 is evil
Trivia 03
Builtin
Integer.bitCount
Code 04
Complement
Odious = odd
Pair 05
Complexity
O(bits)
Analysis❓ Frequently Asked Questions
A nonnegative integer is evil if its binary form has an even number of 1 bits.
If the binary 1-bit count is odd, the number is odious.
Yes. Zero has zero 1-bits, and 0 is even.
15 in binary is 1111, which has 4 ones. Four is even.
Yes. Integer.bitCount(n) (or Long.bitCount(n)) gives popcount directly.
For one number, bit counting is O(number of bits). For a range, multiply by number of values.
Integer.bitCount is clearest in Java. A division or Kernighan loop shows you understand popcount.
Most definitions use nonnegative integers. This page rejects negatives for clarity.
Did you Know? 🔊
The opposite of an evil number is an odious number. Evil means an even count of 1 bits; odious means odd.
Continue to Factorial of a Number
Learn iterative and recursive ways to compute n! in Java.
About the author
9 people found this page helpful