Algorithmic Reasoning

What Is Population Count?

POPULATION COUNT, often shortened to POPCOUNT, means:

Count how many bits in a binary vector are equal to 1.

Example:

data = 8'b10110100

The 1 bits are:

There are:

4 ones

Therefore:

popcount(data) = 4

Population Count Is Different From Counting Consecutive Ones

This distinction is extremely important.

Consider:

8'b00101111

The total number of 1 bits is:

So:

population count = 5

But the number of consecutive 1 bits starting from the least-significant side is:

because:

bit 0 = 1

bit 1 = 1

bit 2 = 1

bit 3 = 1

bit 4 = 0

Therefore:

Population count

≠

Count of trailing consecutive ones

Determining the Required Output Width

Suppose the input contains:

255 bits.

The smallest possible population count is:

The largest possible population count is:

255

Therefore, the output must be able to represent:

0 through 255

An 8-bit unsigned value can represent:

0 through 255

Therefore:

output reg [7:0] out;

is sufficient for the population count of a 255-bit input.

Why 8 Bits Are Enough for a 255-Bit Input

An unsigned N-bit value can represent:

0 through 2^N - 1

For:

N = 8

we get:

0 through 255

Therefore:

8 bits

can represent every possible population count for a 255-bit vector.

This is an important general rule:

The width of the RESULT should be based on the RANGE OF POSSIBLE RESULTS.

It does not need to match the width of the input.

Input Width and Result Width Can Be Very Different

Suppose:

input wire [254:0] in;

This input has:

255 bits.

But the output does NOT need 255 bits.

Why?

Because we are not copying the input.

We are counting how many bits are equal to 1.

The answer can only range from:

0 to 255

Therefore:

8 result bits

are sufficient.

General Result-Width Reasoning

For an input containing M bits:

minimum population count = 0

maximum population count = M

The output therefore needs enough bits to represent:

Conceptually:

Input width

↓

Determine maximum possible result

↓

Choose enough output bits to represent that maximum

This same reasoning can be useful in many other digital-design problems.

The Incorrect Algorithm

Consider code conceptually like:

i = 0;

out = 0;

while ((i < 8) && (in[i] == 1'b1)) begin

out = out + 1;

i = i + 1;

end

At first glance, this may look like it is counting 1 bits.

But it does NOT implement population count correctly.

There are two separate problems.

Problem #1: The Loop Examines Only 8 Bits

The condition contains:

i < 8

Therefore, the code can only examine:

in[0]

through

in[7]

But suppose the input is:

input wire [254:0] in;

That contains:

255 bits.

Therefore, the loop is ignoring:

in[8]

through

in[254]

Even if everything else were correct, this loop could not calculate the full population count.

Problem #2: The Current Bit Is Part of the Loop Condition

The condition also contains:

in[i] == 1'b1

This means:

Continue looping ONLY while the current bit is 1.

Therefore, the moment the loop encounters:

in[i] = 0

the loop terminates.

This is not what population count requires.

Population count must continue examining the remaining bits even after encountering a zero.

What Does the Incorrect Algorithm Actually Count?

The broken loop:

while ((i < 8) && (in[i] == 1'b1))

starts at:

in[0]

and continues only while the bits remain 1.

Therefore, it counts:

the number of CONSECUTIVE 1s beginning at the least-significant bit.

Example:

in = 8'b00101111

Starting from the LSB:

bit 0 = 1

bit 1 = 1

bit 2 = 1

bit 3 = 1

bit 4 = 0

The loop stops at bit 4.

Therefore:

broken algorithm result = 4

But the total population count is:

because there is another 1 at bit 5.

The Central Algorithm Rule

This is one of the most important ideas from this Unit.

LOOP / TRAVERSAL CONDITION

↓

Determines WHICH elements are examined

LOGIC INSIDE THE LOOP

↓

Determines WHAT happens with each examined element

For population count:

Traversal should examine:

EVERY relevant bit

Then:

inside the loop

↓

decide whether the current bit contributes 1 to the count

Incorrect Way to Think

Incorrect idea:

"Keep looping while the current bit is 1."

This produces:

Stop at first 0

That means:

only an initial run of 1s is examined.

Correct Way to Think

Correct idea:

"Visit every bit."

Then for each bit:

If bit = 1

↓

increase count

If bit = 0

↓

do not increase count

Then continue to the next bit either way.

Conceptually:

bit 0

↓

inspect

↓

bit 1

↓

inspect

↓

bit 2

↓

inspect

↓

...

↓

final bit

Correct Conceptual Algorithm

Conceptually:

count = 0

for every bit in the input:

if current bit = 1

count = count + 1

At the end:

count = number of 1 bits in the entire vector

The important point is:

A zero changes the amount added.

A zero does NOT terminate the traversal.

Why a Zero Should Not Stop the Loop

Suppose:

data = 8'b10001001

Starting from the least-significant side:

Population count:

If the loop stopped at the first zero:

it would return:

which is clearly wrong.

Therefore:

0 bit

↓

contributes zero

NOT:

0 bit

↓

stop examining the rest of the vector

Directly Adding the Bit

Because each individual binary bit is numerically either:

or:

we can use:

count = count + in[i];

Conceptually:

If:

in[i] = 0

then:

count = count + 0

So the count does not change.

If:

in[i] = 1

then:

count = count + 1

So the count increases by one.

Why count = count + in[i] Works

Each bit already represents exactly the amount it should contribute.

Bit = 0

↓

contribution = 0

Bit = 1

↓

contribution = 1

Therefore:

count = count + in[i];

is a compact way to express:

"Add one if the current bit is 1; otherwise add zero."

Explicit 'if' vs Direct Bit Addition

These two approaches can express the same counting idea.

EXPLICIT FORM:

if (in[i])

count = count + 1;

DIRECT ADDITION:

count = count + in[i];

The first may be easier to understand initially.

The second is more compact.

The important algorithm is the same:

every bit is examined

and

each 1 contributes one

A Correct Population-Count Structure

A clean conceptual structure is:

count = 0

↓

Visit every input bit

↓

For each bit:

add its value to count

↓

Final count

The exact HDL syntax is less important than understanding this algorithmic structure.

Why Some Incorrect Test Cases Can Still Pass

This is a very important debugging lesson.

Suppose the broken algorithm counts consecutive 1s starting at the LSB.

Now test:

Binary:

0001

Population count = 1

Trailing consecutive ones = 1

So the wrong algorithm passes.

Now test:

Binary:

0011

Population count = 2

Trailing consecutive ones = 2

Again, the wrong algorithm passes.

Now test:

Binary:

0111

Population count = 3

Trailing consecutive ones = 3

The wrong algorithm passes again.

Passing Tests Does Not Necessarily Mean the Algorithm Is Correct

If several test inputs happen to have the same result under:

the intended algorithm

and:

the incorrect algorithm

then passing those tests proves very little.

For:

the set bits form one uninterrupted run beginning at the least-significant side.

Therefore:

population count

and:

count trailing consecutive ones

happen to agree.

A Better Test Case

Use a value whose 1s are separated by zeros.

Example:

10101

Population count:

But consecutive ones from the LSB:

bit 0 = 1

bit 1 = 0

So the broken algorithm returns:

Now the error becomes obvious.

Another Strong Test Case

Consider:

10000001

Population count:

But the incorrect trailing-one algorithm sees:

bit 0 = 1

then:

bit 1 = 0

and stops.

Result:

Therefore, this test distinguishes the algorithms immediately.

Good Tests Target Likely Failure Modes

A good test set should not merely include:

easy values

or:

values that look different numerically.

It should include patterns that challenge the assumptions of the algorithm.

For population count, useful patterns include:

- all zeros

- all ones

- isolated one

- separated ones

- alternating bits

- one high-order 1

- combinations of low-order and high-order 1s

This helps expose incorrect traversal logic.

Edge Case: All Zeros

Suppose:

input = all zeros

Expected population count:

A correct algorithm should:

examine every bit

but never increase the count.

Final result:

Edge Case: All Ones

For a 255-bit input containing all ones:

Expected population count:

255

This is also why the output must be able to represent:

255

An 8-bit unsigned output is exactly sufficient.

Edge Case: One High-Order One

Suppose only:

in[254] = 1

and every other bit is 0.

Population count:

A correct algorithm must still detect that high-order 1.

Any algorithm that only examines:

the first 8 bits

will incorrectly return:

Why i < 8 Is Especially Misleading

The input may have originally reminded the programmer of:

an 8-bit quantity

or:

an 8-bit output

But the traversal limit must correspond to:

the number of INPUT ELEMENTS that need to be examined.

For:

input [254:0] in

the relevant index range is:

0 through 254

not:

0 through 7

Output Width Does Not Determine Loop Bound

This is another important distinction.

The output is:

8 bits wide.

But that does NOT mean:

the loop should execute 8 times.

Why?

The output width tells us:

how many bits are needed to REPRESENT the count.

The loop bound tells us:

how many input elements must be EXAMINED.

For a 255-bit input:

output width = 8 bits

but:

number of input bits to inspect = 255

Input Count vs Result Representation

Keep these separate:

INPUT SIZE

↓

How many elements exist?

RESULT RANGE

↓

What is the largest possible answer?

OUTPUT WIDTH

↓

How many bits are needed to represent that answer?

For the 255-bit population-count problem:

Input size = 255 bits

Maximum result = 255

Output width = 8 bits

Population Count Is a Reduction-Like Operation

Population count takes:

many individual input bits

and produces:

one numerical result

Conceptually:

many bits

↓

count contributions

↓

single count value

This makes it a type of vector-reduction operation, but unlike XOR/AND/OR reduction operators, the result can require multiple bits.

Population Count vs Reduction XOR

Reduction XOR answers:

"Is the number of 1s odd or even?"

Population count answers:

"Exactly how many 1s are present?"

For example:

data contains 5 ones

Then:

population count = 5

reduction XOR = 1

because 5 is odd.

These are different operations.

Population Count vs Leading/Trailing-One Count

POPULATION COUNT:

Count all 1 bits anywhere in the vector.

TRAILING-ONE COUNT:

Count consecutive 1 bits beginning from the least-significant side.

LEADING-ONE COUNT:

Count consecutive 1 bits beginning from the most-significant side.

These operations can return very different answers for the same vector.

Example Comparing the Three

Consider:

8'b11010111

Population count:

Trailing consecutive ones from the LSB:

Leading consecutive ones from the MSB:

Therefore:

popcount = 6

trailing-one count = 3

leading-one count = 2

This demonstrates why the algorithm's termination condition matters.

Debugging by Asking "What Does This Code Actually Compute?"

When code fails, do not only ask:

"Why isn't my population count working?"

Instead ask:

"What function does this code actually implement?"

For:

while ((i < 8) && in[i])

the answer is:

"Count consecutive low-order ones, up to 8 positions."

Once the actual function is identified, the mismatch becomes much easier to diagnose.

Separate the Specification From the Implementation

SPECIFICATION:

Count every 1 bit in the 255-bit vector.

IMPLEMENTATION:

The Verilog code written to achieve that.

If the implementation instead:

stops at the first zero

then:

the implementation does not match the specification.

This is an important general hardware-design debugging principle.

A Correct Result on One Input Does Not Prove Correct Hardware

Suppose:

input = 7

and the output is correctly:

This shows only:

The circuit behaves correctly for that particular input.

It does NOT prove:

The circuit implements population count for all possible inputs.

Digital logic must be judged against the complete intended function.

Why Adversarial Tests Matter

An ADVERSARIAL TEST is designed to expose a likely weakness or incorrect assumption.

If you suspect the algorithm stops at the first zero:

choose a test containing:

1s after a zero.

Example:

10101

That directly challenges the suspected failure mode.

This is much stronger than repeatedly testing:

which all have consecutive low-order ones.

Population Count and Hardware

A population-count description must ultimately become hardware capable of combining contributions from many bits.

The exact FPGA implementation is determined by synthesis.

We should therefore avoid assuming that the source code must become one literal sequential chain exactly matching the procedural order.

The important requirement is:

the final hardware must produce the correct count.

Source Algorithm vs Physical Structure

Suppose the source uses a loop that conceptually accumulates:

count = count + in[i];

That does not guarantee that the FPGA physically contains one adder repeatedly reused 255 times during one combinational evaluation.

As learned previously:

SOURCE-CODE STRUCTURE

≠

GUARANTEED PHYSICAL FPGA STRUCTURE

Synthesis may restructure the logic while preserving the required result.

Common Mistake: Using the Current Data Value to Control Traversal

For population count:

Current bit value should determine:

CONTRIBUTION

not:

whether all later bits are visited.

Incorrect:

Continue only while current bit = 1

Correct mental model:

Always continue through the required input range

and use current bit to decide whether the count increases.

Common Mistake: Matching the Loop Bound to the Output Width

Output:

8 bits

does NOT imply:

8 iterations.

The output width exists because:

255 requires 8 bits to represent.

The loop must still examine:

255 input bits.

Common Mistake: Trusting Only Convenient Tests

Values such as:

all have contiguous 1s beginning at the LSB.

They are therefore poor tests for distinguishing:

population count

from:

trailing-one count.

A correct verification strategy needs structurally different bit patterns.

Common Mistake: Forgetting the Maximum Result

If the input contains M bits:

population count can equal M.

Therefore, when sizing the result, always ask:

"Can the output represent the case where every input bit is 1?"

For 255 bits:

maximum result = 255

An 8-bit unsigned result can represent exactly that.

Final Comparison

POPULATION COUNT

Meaning:

Count every bit equal to 1 in the complete vector.

TRAILING CONSECUTIVE ONES

Meaning:

Count consecutive 1 bits beginning at the least-significant side until the first 0 appears.

TRAVERSAL CONDITION

Purpose:

Determines which elements are examined.

CONTRIBUTION LOGIC

Purpose:

Determines whether/how each examined element affects the result.

RESULT WIDTH

Purpose:

Provides enough bits to represent every possible answer.

WEAK TEST CASE

A test that does not distinguish the correct algorithm from a plausible incorrect algorithm.

ADVERSARIAL TEST CASE

A test deliberately chosen to expose a suspected failure mode.

Final Mental Model

For population count:

STEP 1

Determine what must be examined.

For a 255-bit vector:

ALL 255 BITS

STEP 2

Determine how each element contributes.

bit = 0

↓

add 0

bit = 1

↓

add 1

STEP 3

Determine the result range.

minimum = 0

maximum = 255

STEP 4

Choose enough output bits.

8 unsigned bits

↓

0 through 255

STEP 5

Test patterns that can expose incorrect logic.

Do not only use:

0001

0011

0111

Also use:

10101

10000001

alternating patterns

high-order isolated ones

The most important ideas are:

POPULATION COUNT MEANS COUNTING ALL 1 BITS IN THE VECTOR.

THE OUTPUT WIDTH SHOULD BE BASED ON THE MAXIMUM POSSIBLE COUNT.

A 255-BIT INPUT HAS A MAXIMUM POPULATION COUNT OF 255.

AN 8-BIT UNSIGNED OUTPUT CAN REPRESENT 0 THROUGH 255.

THE WIDTH OF THE OUTPUT DOES NOT DETERMINE HOW MANY INPUT BITS MUST BE EXAMINED.

A LOOP CONDITION DETERMINES WHICH ELEMENTS ARE VISITED.

LOGIC INSIDE THE LOOP DETERMINES WHETHER AN ELEMENT CONTRIBUTES TO THE RESULT.

INCLUDING in[i] AS A LOOP-CONTINUATION CONDITION CAN CAUSE THE LOOP TO STOP AT THE FIRST ZERO.

THE BROKEN EXAMPLE COUNTS CONSECUTIVE LOW-ORDER ONES, NOT TOTAL ONES.

count = count + in[i] WORKS BECAUSE EACH BIT CONTRIBUTES EITHER 0 OR 1.

PASSING A FEW TEST CASES DOES NOT PROVE AN ALGORITHM IS CORRECT.

VALUES SUCH AS 1, 3, AND 7 CAN HIDE THE ERROR BECAUSE THEIR SET BITS ARE CONSECUTIVE FROM THE LSB.

TESTS WITH SEPARATED 1 BITS ARE MUCH BETTER FOR EXPOSING THIS FAILURE.

WHEN DEBUGGING HDL, ASK WHAT FUNCTION THE CODE ACTUALLY IMPLEMENTS RATHER THAN ONLY ASKING WHY IT FAILED THE INTENDED FUNCTION.