Population Count in Verilog: Counting 1s (Hamming Weight)

// popcount.v : Population count (Hamming weight) via for-loop accumulate
module popcount #(parameter W = 8) (
    input  [W-1:0]              in,
    output [$clog2(W+1)-1:0]    count
);
    integer i;
    reg [$clog2(W+1)-1:0] acc;
    always @(*) begin
        acc = 0;
        for (i = 0; i < W; i = i + 1)
            acc = acc + in[i];   // add each bit
    end
    assign count = acc;
endmodule

module tb;
    localparam W = 8;
    reg  [W-1:0] vec;
    wire [$clog2(W+1)-1:0] cnt;
    integer k, expct;
    reg ok;

    popcount #(.W(W)) dut (.in(vec), .count(cnt));

    // reference: software popcount
    function integer ref_pop;
        input [W-1:0] v;
        integer j, s;
        begin
            s = 0;
            for (j = 0; j < W; j = j + 1) s = s + v[j];
            ref_pop = s;
        end
    endfunction

    task check;
        input [W-1:0] v;
        begin
            vec = v; #1;
            expct = ref_pop(v);
            if (cnt === expct[$clog2(W+1)-1:0]) begin
                $display("PASS in=%b count=%0d (expected %0d)", v, cnt, expct);
            end else begin
                $display("FAIL in=%b count=%0d (expected %0d)", v, cnt, expct);
                ok = 1'b0;
            end
        end
    endtask

    initial begin
        ok = 1'b1;
        check(8'h00); // 0
        check(8'hFF); // 8
        check(8'h0F); // 4
        check(8'hA5); // 4
        check(8'h80); // 1
        if (ok) $display("ALL PASS");
        else    $display("SOME FAILED");
        $finish;
    end
endmodule

PASS in=00000000 count=0 (expected 0)
PASS in=11111111 count=8 (expected 8)
PASS in=00001111 count=4 (expected 4)
PASS in=10100101 count=4 (expected 4)
PASS in=10000000 count=1 (expected 1)
ALL PASS
The testbench sweeps 0x00→0, 0xFF→8, 0x0F→4, 0xA5→4 and 0x80→1, each checked against a reference loop, then prints ALL PASS.

Kernighan's trick: v & (v−1)
This 16-bit variant counts set bits by repeatedly clearing the lowest 1. Subtracting 1 flips the lowest set bit and sets all bits below it; ANDing with the original removes exactly that bit. The loop runs W times (the worst case) so it stays statically bounded and synthesizable.
popcount_trick.vSimulation log
// popcount_trick.v : Hamming weight via repeated v & (v-1) clear-lowest-set-bit
module popcount_kernighan #(parameter W = 16) (
    input  [W-1:0]            in,
    output [$clog2(W+1)-1:0]  count
);
    integer n;
    reg [W-1:0] tmp;
    reg [$clog2(W+1)-1:0] acc;
    always @(*) begin
        acc = 0;
        tmp = in;
        for (n = 0; n < W; n = n + 1) begin
            if (tmp != 0) begin
                tmp = tmp & (tmp - 1'b1); // clear lowest set bit
                acc = acc + 1'b1;
            end
        end
    end
    assign count = acc;
endmodule

module tb;
    localparam W = 16;
    reg  [W-1:0] vec;
    wire [$clog2(W+1)-1:0] cnt;
    integer expct;
    reg ok;

    popcount_kernighan #(.W(W)) dut (.in(vec), .count(cnt));

    function integer ref_pop;
        input [W-1:0] v;
        integer j, s;
        begin
            s = 0;
            for (j = 0; j < W; j = j + 1) s = s + v[j];
            ref_pop = s;
        end
    endfunction

    task check;
        input [W-1:0] v;
        begin
            vec = v; #1;
            expct = ref_pop(v);
            if (cnt === expct[$clog2(W+1)-1:0]) begin
                $display("PASS in=%016b count=%0d (expected %0d)", v, cnt, expct);
            end else begin
                $display("FAIL in=%016b count=%0d (expected %0d)", v, cnt, expct);
                ok = 1'b0;
            end
        end
    endtask

    initial begin
        ok = 1'b1;
        check(16'h0000); // 0
        check(16'hFFFF); // 16
        check(16'h00FF); // 8
        check(16'hA5A5); // 8
        check(16'h8000); // 1
        check(16'h1234); // 5
        if (ok) $display("ALL PASS");
        else    $display("SOME FAILED");
        $finish;
    end
endmodule
PASS in=0000000000000000 count=0 (expected 0)

PASS in=1111111111111111 count=16 (expected 16)

PASS in=0000000011111111 count=8 (expected 8)

PASS in=1010010110100101 count=8 (expected 8)

PASS in=1000000000000000 count=1 (expected 1)

PASS in=0001001000110100 count=5 (expected 5)

ALL PASS
Six vectors from 0 to 16 set bits are checked against the reference loop; the run ends with ALL PASS.
How the designs work
Both modules are purely combinational: the always @(*) block has no clock, so the output count settles after the input propagates. The width of the result is computed as $clog2(W+1) bits. Why W+1 and not W? An 8-bit input can hold values 0 through 8, and 8 needs four bits, so $clog2(9) = 4. Using $clog2(W) would be off by one for powers of two — a classic rounding bug worth memorizing.
In the first design, the loop acc = acc + in[i] simply treats each 1-bit slice as a 0 or 1 addend. The second design's expression tmp & (tmp - 1) is the Brian Kernighan idiom: because tmp - 1 borrows through the trailing zeros up to the lowest set bit, ANDing wipes that one bit and leaves the rest intact. Iterate until tmp is zero and the iteration count equals the Hamming weight.
Synthesis and timing notes
Despite the sequential appearance of the for loop, synthesis fully unrolls it — loop bounds are constant — into pure combinational logic. The accumulation version maps to a tree of small adders (a Wallace-style reduction), giving a delay that grows roughly as log(W). That is the recommended structure for wide inputs on an FPGA or ASIC because tools balance it well.
The Kernighan version, by contrast, has a data-dependent carry chain through W conditional stages. It will synthesize, but it produces a longer critical path and more area than the adder tree, since each stage needs a full subtractor plus a comparator. Prefer it for clarity or when you want a small iterative/FSM implementation that processes one bit per clock; for a flat combinational popcount, use the adder tree. For very wide vectors, a generate-based adder tree or compressor counters (3:2 CSAs) outperform both.
Common pitfalls
The most frequent mistake is sizing the output register too narrowly — truncating a 16-bit popcount to four bits silently drops the value 16. Always derive the width from $clog2(W+1). A second trap is writing the loop variable as a reg inside the vector width; use an integer for loop counters in Verilog-2005. Third, remember the accumulator must be reset to 0 at the top of every combinational evaluation, otherwise simulation shows a latch and synthesis infers one.
Also note the subtraction tmp - 1'b1 is done on an unsigned vector, so when tmp is zero it would wrap — which is exactly why the if (tmp != 0) guard matters.
Interview angle
Interviewers love popcount because it tests both bit-manipulation fluency and hardware intuition. Expect follow-ups like: “What is the output width for a 32-bit input?” (answer: 6 bits, since $clog2(33) = 6), “Which implementation has the shortest critical path?” (the balanced adder tree), and “How would you pipeline a 256-bit popcount?” (split into byte-wise lookups or 3:2 compressor stages with registers between levels). Being able to explain why v & (v-1) clears the lowest set bit — and that its loop count equals the Hamming weight — signals real low-level understanding. Mentioning that hardware favors a logarithmic adder tree over an iterative software-style loop shows you think in gates, not instructions.
Have questions about this topic?
Share your question in comments or talk to our mentor team for batch guidance.
▶ Try it in the ChipXpert Lab
Open this design in the free in-browser simulator — edit, compile and see the waveform/log instantly.
Run it in the Lab
Learn Verilog with mentors, labs and placement support
This free series is maintained by the ChipXpert training team in Hyderabad & Bengaluru. Go deeper with instructor-led courses on real EDA tools.
Explore VLSI Courses