15Evil
Check Evil Number in PHP
What you’ll learn
- The definition of an evil number: even count of
1-bits in binary (nonnegative integers). - A bitwise popcount helper and a division-by-two range method.
- Live preview, edge cases (
0, negatives), and related interview links.
Overview
Evil numbers classify integers by parity of Hamming weight in base 2. Check is simple: count 1 bits, then test if that count is even.
Prerequisites
Loops, % and /, and basic bitwise & and >>.
What is an evil number?
Nonnegative integer n is evil when binary n has an even number of 1 digits. Odd count means odious.
Evilpopcount(n) % 2 == 0
Odiouspopcount(n) % 2 == 1
Zeroevil (0 ones)
Hamming weight
If s2(n) is count of 1 bits, then n is evil iff s2(n) mod 2 = 0.
Intuition
7Odious
Live preview
Algorithm
📜 Pseudocode
Pseudocode
function popcount(n): // 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) = 01
Bitwise popcount (single value)
php
<?php
function countSetBitsNonneg(int $n): int
{
$count = 0;
while ($n > 0) {
$count += ($n & 1);
$n >>= 1;
}
return $count;
}
function isEvilNonneg(int $n): bool
{
if ($n < 0) return false;
return countSetBitsNonneg($n) % 2 === 0;
}
$number = 15;
echo isEvilNonneg($number)
? "{$number} is an Evil Number.\n"
: "{$number} is not an Evil Number.\n";
?>2Evil numbers in
Evil numbers in [1, 10]
php
<?php
function isEvilByDivision(int $num): bool
{
$ones = 0;
while ($num > 0) {
if ($num % 2 === 1) {
$ones++;
}
$num = intdiv($num, 2);
}
return $ones % 2 === 0;
}
echo "Evil numbers in the range 1 to 10:\n";
for ($i = 1; $i <= 10; $i++) {
if (isEvilByDivision($i)) {
echo $i . " ";
}
}
echo "\n";
?>Optimization
Kernighan trick. Clear the lowest set bit with $n &= ($n - 1); one iteration per set bit.
Built-ins. Where available, popcount/parity helpers can speed up bulk scans.
Interview: define nonnegative scope, mention 0, then show popcount parity.
❓ 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.
Yes. For nonnegative integers, ($n & 1) and right shifts are a clean way to count set bits.
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).
🔄 Input / output examples
| n | Binary | Ones | Verdict |
|---|---|---|---|
0 | 0 | 0 | Evil |
3 | 11 | 2 | Evil |
7 | 111 | 3 | Odious |
15 | 1111 | 4 | Evil |
Edge cases and pitfalls
Zero
n = 0
Popcount 0 is even, so 0 is evil.
Sign
Negative integers
This page defines evil/odious for nonnegative integers only.
Range
1 ≤ i ≤ 10
Example range starts at 1, so 0 is not printed there.
⏱️ Time and space complexity
| Operation | Time | Extra space |
|---|---|---|
Popcount of n | O(log n) bit steps | O(1) |
| Kernighan variant | O(popcount(n)) | O(1) |
Scan [a,b] | O((b-a+1) log U) | O(1) |
Summary
- Definition: evil iff binary 1-bit count is even.
- Code: count bits, then check parity of that count.
- Watch-outs: keep nonnegative convention explicit.
Did you know?
The complementary class is odious numbers: nonnegative integers whose binary expansion has an odd number of 1 bits.
About the author
8 people found this page helpful