Find First Set (FFS) in Verilog: Lowest Set-Bit Index with Code

module ffs #(parameter W = 8) (
    input  [W-1:0]         data,
    output reg [$clog2(W)-1:0] index,
    output                 valid
);
    wire [W-1:0] lowest = data & (~data + 1'b1);
    assign valid = |data;
    integer i;
    always @(*) begin
        index = 0;
        for (i = 0; i < W; i = i + 1)
            if (lowest[i]) index = i[$clog2(W)-1:0];
    end
endmodule

module tb;
    reg  [7:0] d;
    wire [2:0] idx;
    wire       v;
    integer    k, exp, found;

    ffs #(.W(8)) dut (.data(d), .index(idx), .valid(v));

    task check;
        input [7:0] vec;
        begin
            d = vec;
            #1;
            exp = 0; found = 0;
            for (k = 0; k < 8; k = k + 1)
                if (!found && vec[k]) begin exp = k; found = 1; end
            if (found) begin
                if (v === 1'b1 && idx === exp[2:0])
                    $display("PASS data=%b index=%0d valid=1", vec, idx);
                else
                    $display("FAIL data=%b got idx=%0d v=%b exp idx=%0d v=1", vec, idx, v, exp);
            end else begin
                if (v === 1'b0)
                    $display("PASS data=%b valid=0 (all-zero)", vec);
                else
                    $display("FAIL data=%b got v=%b exp v=0", vec, v);
            end
        end
    endtask

    integer n;
    initial begin
        check(8'b0000_0000);
        for (n = 0; n < 8; n = n + 1) check(8'b1 << n);
        check(8'b0000_1100);
        check(8'b1010_0000);
        check(8'b1111_1111);
        check(8'b1000_0001);
        check(8'b0110_0000);
        $display("ALL TESTS PASSED");
        $finish;
    end
endmodule

PASS data=00000000 valid=0 (all-zero)
PASS data=00000001 index=0 valid=1
PASS data=00000010 index=1 valid=1
PASS data=00000100 index=2 valid=1
PASS data=00001000 index=3 valid=1
PASS data=00010000 index=4 valid=1
PASS data=00100000 index=5 valid=1
PASS data=01000000 index=6 valid=1
PASS data=10000000 index=7 valid=1
PASS data=00001100 index=2 valid=1
PASS data=10100000 index=5 valid=1
PASS data=11111111 index=0 valid=1
PASS data=10000001 index=0 valid=1
PASS data=01100000 index=5 valid=1
ALL TESTS PASSED
The log proves the module returns the correct lowest-set index for all eight single-bit inputs and for multi-bit vectors like 11111111 and 10000001 (both index 0), while asserting valid=0 only for the all-zero bus. Each line is checked against a golden index the testbench computes independently, so any off-by-one or priority error would print FAIL.

This variant finds the last (most-significant) set bit using a casez priority ladder. The ? wildcards let the first matching high-to-low pattern win, which is exactly priority-encoder behaviour; the default arm handles the all-zero case by clearing valid.
fls8.vSimulation log
module fls8 (
    input  [7:0]     data,
    output reg [2:0] index,
    output reg       valid
);
    always @(*) begin
        valid = 1'b1;
        casez (data)
            8'b1???????: index = 3'd7;
            8'b01??????: index = 3'd6;
            8'b001?????: index = 3'd5;
            8'b0001????: index = 3'd4;
            8'b00001???: index = 3'd3;
            8'b000001??: index = 3'd2;
            8'b0000001?: index = 3'd1;
            8'b00000001: index = 3'd0;
            default:     begin index = 3'd0; valid = 1'b0; end
        endcase
    end
endmodule

module tb;
    reg  [7:0] d;
    wire [2:0] idx;
    wire       v;
    integer    k, exp, found;

    fls8 dut (.data(d), .index(idx), .valid(v));

    task check;
        input [7:0] vec;
        begin
            d = vec;
            #1;
            exp = 0; found = 0;
            for (k = 7; k >= 0; k = k - 1)
                if (!found && vec[k]) begin exp = k; found = 1; end
            if (found) begin
                if (v === 1'b1 && idx === exp[2:0])
                    $display("PASS data=%b MSB-index=%0d valid=1", vec, idx);
                else
                    $display("FAIL data=%b got idx=%0d v=%b exp idx=%0d", vec, idx, v, exp);
            end else begin
                if (v === 1'b0)
                    $display("PASS data=%b valid=0 (all-zero)", vec);
                else
                    $display("FAIL data=%b got v=%b exp v=0", vec, v);
            end
        end
    endtask

    integer n;
    initial begin
        check(8'b0000_0000);
        for (n = 0; n < 8; n = n + 1) check(8'b1 << n);
        check(8'b0000_1100);
        check(8'b1010_0000);
        check(8'b0010_1010);
        check(8'b1000_0001);
        check(8'b0001_1111);
        $display("ALL TESTS PASSED");
        $finish;
    end
endmodule
PASS data=00000000 valid=0 (all-zero)
PASS data=00000001 MSB-index=0 valid=1
PASS data=00000010 MSB-index=1 valid=1
PASS data=00000100 MSB-index=2 valid=1
PASS data=00001000 MSB-index=3 valid=1
PASS data=00010000 MSB-index=4 valid=1
PASS data=00100000 MSB-index=5 valid=1
PASS data=01000000 MSB-index=6 valid=1
PASS data=10000000 MSB-index=7 valid=1
PASS data=00001100 MSB-index=3 valid=1
PASS data=10100000 MSB-index=7 valid=1
PASS data=00101010 MSB-index=5 valid=1
PASS data=10000001 MSB-index=7 valid=1
PASS data=00011111 MSB-index=4 valid=1
ALL TESTS PASSED
The log shows the casez encoder returning the most-significant set index: 10100000 and 10000001 both resolve to 7, 00101010 to 5, and the all-zero bus drives valid=0. The testbench's golden loop scans from bit 7 downward, so it would catch any mis-ordered casez arm.

FFS vs find-last-set vs count-leading-zeros
These three operations are easy to confuse, so pin down the definitions before you write RTL:
Find first set (FFS) / count-trailing-zeros (CTZ): the index of the least-significant '1'. For 0b0010_1000 that is bit 3.
Find last set (FLS): the index of the most-significant '1'. For the same value that is bit 5. This equals floor(log2(x)).
Count leading zeros (CLZ): the number of zeros above the most-significant '1'. It is a simple transform of FLS: for a W-bit bus, CLZ = (W-1) - FLS_index.
Example 1 computes FFS; Example 2 computes FLS. Note the index is only meaningful when the bus is non-zero, which is why every version carries a valid output.

The x & -x isolation identity
Example 1 leans on a classic bit-twiddling identity: x & (-x) clears every set bit except the lowest. In two's complement, -x = ~x + 1. Negation flips all bits up to and including the lowest '1' and leaves the trailing zeros unchanged, so ANDing with the original keeps exactly one bit.
x        = 0010_1000
~x       = 1101_0111
~x + 1   = 1101_1000   (= -x)
x & -x   = 0000_1000   (only the lowest set bit)
After isolation you have a one-hot vector, and the one-hot-to-binary loop just records the index of the single surviving bit. The same isolated vector is also handy if you want to clear the lowest pending request in an arbiter: x & (x - 1) removes it.
Uses in schedulers, allocators, and arbiters
FFS is everywhere a design must pick the lowest-numbered active item in one cycle:
Fixed-priority arbiters: the request bus feeds FFS, and the index selects the grant. Lower bit = higher priority.
Free-list allocators: a bitmap of free buffers or registers; FFS returns the next free slot, and x & (x-1) marks it taken.
Round-robin schedulers: mask off requests below the last grant, run FFS on the masked bus, and fall back to the unmasked bus when the masked result is invalid.
Interrupt controllers: FFS over a pending-interrupt vector yields the highest-priority IRQ number.
Because these sit on the critical path, large buses are usually implemented as a balanced tree of priority encoders rather than the linear loop shown here, trading a little area for shorter logic depth.
The all-zero corner case
An all-zero input has no set bit, so the index is undefined. The robust contract is a separate valid output that is 0 in that case, letting downstream logic ignore the index. Both examples do exactly this: Example 1 uses valid = |data and Example 2 uses the casez default arm.
A common bug is returning index 0 for all-zeros and letting a consumer treat it as a real hit on bit 0 — indistinguishable from a genuine 0b0000_0001. Always test the all-zero vector explicitly, which is why it is the first case in both testbenches.
Synthesis notes and common mistakes
Synthesis
The for loop in Example 1 is a static, unrolled loop — the synthesizer flattens it into combinational priority logic, not a sequential loop. Keep the bound a parameter/constant so it elaborates. The casez ladder in Example 2 synthesizes directly to a priority encoder.
Common mistakes
Latch inference: in an always @(*) block, assign index a default before the loop or case so every path drives it. Both examples initialize first.
casez and X/Z: casez treats ?/z as don't-care in the pattern; it can also match z in the data, which is rarely intended. For don't-cares driven by real logic this is fine, but prefer explicit patterns over wide wildcards.
Index width: a W-bit bus needs a $clog2(W)-bit index. Truncating to too few bits silently wraps high indices.
Signedness of x & -x: compute ~data + 1 on an unsigned vector of the same width so the carry wraps cleanly; do not promote to a wider signed integer mid-expression.
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