先把这个“小问题”的前因后果说清楚“找1的位置”这个需求在数字逻辑设计里出镜率高得吓人。总线仲裁器要找到最高优先级的请求者、FIFO指针管理要找到读指针之后第一个有效位置、位图扫描要找到第一个空闲块、很多公司的面试题里它又化身高频考点——本质都是同一件事给你一个 N bit 向量找出其中某个1的位置并且告诉别人你找的是最高位还是最低位如果全是0又该怎么办。刚接触 Verilog 的朋友通常第一反应是写个 for 循环等位宽一上去发现时序快崩了才意识到这里面的门道不少。这篇文章我把做过的几种实现方式、综合结构、踩过的坑一起整理出来。从最简单的 for 循环遍历到适合宽位输入的二分查找树再到资源紧张时用的多周期状态机每种都会给出可综合的代码思路和仿真验证方法。你不用纠结标题里“找到1的位置”听起来太简单——等你看完 64 bit 输入的时序分析就知道为什么有人会在这道题上栽跟头了。1. 先想明白找1的位置到底要什么1.1 三种常见需求最高位、最低位、全部位置“找到1”不是一句废话不同场景要的答案完全不一样。拿一个 8 bit 向量8b0010_1010举例里面一共有三个1分别在 bit1、bit3、bit5。如果需求是找最高位1答案应该是5如果需求是找最低位1答案是1如果需求是列出所有1的位置答案就是 {5, 3, 1} 这三个数。最高位1常用于优先级最高的请求判断最低位1常用于轮询仲裁里“从当前位置往低找下一个请求”而列出全部位置在 Cache 行替换、稀疏存储管理等场景里更常见。三种需求里前两种是基础第三种通常是在前两种的基础上做扩展所以先把最高位、最低位的查找逻辑吃透后面什么场景都能套。我自己的经验是接到这类需求先跟需求方确认两个问题一个是“位置从0开始还是从1开始编号”另一个是“全零输入时怎么办”。这两个问题看似无关紧要却是后续所有电路设计的地基。位置编号差1后面所有比较逻辑都要改全零输入怎么处理直接决定 valid 信号需不需要单独拉出来。1.2 接口定义与关键参数一个标准的“找1位置”模块接口设计一般是这样信号方向位宽说明dininputWIDTH待检测的输入向量posoutputclog2(WIDTH)找到的1所在位置validoutput1为1时表示输入中存在1pos有效WIDTH 是参数默认可以设8或者16。pos 的位宽用$clog2(WIDTH)计算意思是能表示0到WIDTH-1这 WIDTH 个位置的最小 bit 数。比如 WIDTH8pos 需要3 bitWIDTH16pos 需要4 bit。这里有个细节值得单独说如果位置编号从1开始而不是从0开始pos 位宽建议还是用$clog2(WIDTH)而不是$clog2(WIDTH1)。为什么因为最高位位置是 WIDTH为了能表示它确实需要多一位但绝大多数场景根本不需要把“位置1”映射到编码1完全可以在输出端做一次pos 1b1转换。模块内部统一用0基准比到处埋“1”要安全得多。1.3 典型应用场景仲裁、位图、指针管理这些模块到底用在哪我举三个实际例子。第一个是总线仲裁器。假设有8个主设备共享一条总线req[7:0]表示哪些设备发起了请求我们约定req[7]优先级最高。仲裁器要做的事情就是从 req 里找最高位1这个位置就是下一拍拿到总线授权的设备编号。如果你只会找最低位1那优先级就反了整个系统行为都会错。第二个是位图管理。内存管理单元里通常有一张大位图每一位表示一个内存块是否空闲1表示空闲。分配内存时需要从低位往高位找到第一个1也就是找最低位1找到之后把这一位清0返回的 pos 就是分配的块号。这个场景对延迟要求极高位图宽度动不动就是128位甚至256位for 循环方案根本扛不住。第三个是异步 FIFO 的格雷码指针。读指针和写指针经过格雷码转换后要判断空满状态需要比较指针之间的差异。很多实现里会用到“找指针差值中第一个1的位置”这类逻辑本质上还是一个优先级编码器。2. 方法一for 循环遍历最直觉也最容易踩坑2.1 循环方向决定“最高位”还是“最低位”回到核心问题用 for 循环怎么写很多人第一版写出来是这样的always (*) begin pos 0; valid |din; for (i 0; i WIDTH; i i 1) begin if (din[i]) pos i; end end这段代码找的是最高位1。理解这个结果的关键在于Verilog 的 for 循环在综合时不是一个真正的“循环执行”而是被展开成一条从低位到高位的判断链。每一次满足条件都会给 pos 重新赋值最后一次赋值会覆盖前面的值。i 从0递增最后停留在的 i 一定是最大那个为1的位所以要的是最高位。如果你把循环反过来写for (i WIDTH - 1; i 0; i i - 1) begin if (din[i]) pos i; end那最后覆盖 pos 的就是最小那个为1的位这是找最低位1。两个方向都能用但结果差一个全反转。我自己第一次写的时候就在这里翻过车需求文档写“返回优先的请求者”我按惯性从高位往低位扫结果把最低位1当成了结果。所以写代码前先在注释里写清楚“我们要的是 highest one 还是 lowest one”这行注释能在三天后救你一命。2.2 完整 RTL 代码与综合结构分析我一般会把这段逻辑封装成可参数化模块方便不同位宽复用。下面是完整代码我特意加了一个自定义 clog2 函数避免不同仿真器对$clog2支持情况不一致的问题。module find_one_high #( parameter WIDTH 8 )( input wire [WIDTH-1:0] din, output reg [CLOG2-1:0] pos, output reg valid ); localparam CLOG2 clog2(WIDTH); integer i; function integer clog2; input integer value; integer i; begin clog2 0; for (i value - 1; i 0; i i 1) clog2 clog2 1; end endfunction always (*) begin pos 0; valid |din; for (i 0; i WIDTH; i i 1) begin if (din[i]) pos i[CLOG2-1:0]; end end endmodule这段代码综合出来是什么综合工具会把 for 循环展开成一个典型的优先级编码器结构低位判断先走高位判断后走优先级从高到低。虽然代码看起来是“从低位扫描”但综合工具通常会把这个结构优化成一条由比较器和选择器组成的链逻辑级数接近 WIDTH 量级。WIDTH 不大的时候8、16这条链完全没问题。但 WIDTH 到64以上任何一个做过后端时序收敛的人都会皱眉链路太长组合逻辑延时会变得非常可观再加上驱动信号扇出很容易出现时序违例。这不是代码写法有错而是结构决定的。2.3 你最容易忽略的默认值问题for 循环版本看着简单但有一个隐藏的坑如果不在 always 块开头给 pos 赋默认值综合工具会推断出锁存器。为什么因为组合逻辑要求“任何输入条件下所有输出都有确定值”。假如你写成always (*) begin valid |din; for (i 0; i WIDTH; i i 1) begin if (din[i]) pos i; end end当 din 全为0时循环里 if 一次都不满足pos 保持上一次的值这个行为组合逻辑实现不了只能靠锁存器保存。锁存器在时序分析里很难处理容易出 glitch大部分公司的代码规范会直接禁止。解决办法就是在 always 块开头无条件赋初值pos 0;这样不需要保存历史状态综合出来的就是纯组合逻辑。如果你的模块里还带时序逻辑比如在 posedge clk 里对 pos 赋值那就是另一套写法了别把组合逻辑的 always 和时序逻辑的 always 混在一起写。3. 方法二二分查找树宽位输入的时序救星3.1 为什么位宽一大for 循环就扛不住了假设输入位宽是64for 循环展开后的判断链有64级。一级比较器延迟姑且按0.1ns算64级就是6.4ns在500MHz时钟下周期2ns完全跑不通。你可能觉得 “综合工具会不会自动优化成树形结构”大多数情况下不会因为 for 循环的展开顺序隐含了优先级工具会尊重这种顺序。那有没有办法强制缩短关键路径有核心思路是把“串行判断”改成“分而治之”。看一个64位向量先判断高32位有没有1如果有结果一定在高32位里如果没有再去低32位里找。确定方向之后把选中的32位再分成两半继续判断。每判断一次就能排除一半最终定位到具体的一位判断次数从64次降到6次。这就是二分查找树路径深度从 O(N) 降到 O(logN)。我在实际项目里用过这个思路去处理128位的 Cache 替换策略查找组合逻辑延迟比 for 循环版本下降了快一半关键是代码结构依然很清晰。3.2 二分查找树的构造思路构造过程可以这么理解把输入对半切高半部分和低半部分分别做一次“找最高位”的查找再把两个结果二选一。选谁呢如果高半部分非零就选高半的结果同时把结果的位置编码最高位置1如果高半部分是0就选低半的结果位置编码最高位置0。这种递归思路可以用代码表达。下面是一个参数化版本为了保证可读性和可综合性我用 generate 实现树的每一层。为了简化代码假设 WIDTH 是2的幂。module find_one_tree #( parameter WIDTH 8 )( input wire [WIDTH-1:0] din, output wire [$clog2(WIDTH)-1:0] pos, output wire valid ); function integer clog2; input integer value; integer i; begin clog2 0; for (i value - 1; i 0; i i 1) clog2 clog2 1; end endfunction localparam LOG2 clog2(WIDTH); generate if (WIDTH 2) begin: base assign valid |din; assign pos din[1]; end else begin: tree localparam HALF WIDTH / 2; wire [clog2(HALF)-1:0] hi_pos; wire [clog2(HALF)-1:0] lo_pos; wire hi_valid; wire lo_valid; find_one_tree #(.WIDTH(HALF)) hi_part ( .din (din[WIDTH-1:HALF]), .pos (hi_pos), .valid(hi_valid) ); find_one_tree #(.WIDTH(HALF)) lo_part ( .din (din[HALF-1:0]), .pos (lo_pos), .valid(lo_valid) ); assign valid hi_valid | lo_valid; assign pos hi_valid ? {1b1, hi_pos} : {1b0, lo_pos}; end endgenerate endmodule这个模块在 WIDTH8 时会生成三层树第一层比较高4位和低4位第二层比较两位第三层就是单个 bit。每一层只有一个二选一和一个比较器关键路径非常短。这里有一个需要特别说明的注意点递归例化在同一模块名上大多数主流综合工具如 Vivado、Quartus能正确处理是因为 WIDTH 递减到2就会终止不会产生无限递归。但如果你用的工具比较老对递归例化支持不好可以把树手工展开成多个子模块层级逻辑完全一样。3.3 参数化 RTL 实现与延迟分析二分树和 for 循环的延迟差异用一个简单模型就能算清楚。假设每一级比较和选择延迟都是 T。for 循环的延迟大约是 (WIDTH-1) 个 TWIDTH64 就是63T。二分查找树每一层只做一次比较层数是 log2(WIDTH)WIDTH64 就是6层延迟6T。两者差了将近10倍。面积方面二分树需要两个子模块的结果再拼接每一层都有额外的选择和拼接逻辑。以16位输入为例for 循环大概需要16个比较器实际上综合工具会优化成更少二分树每一层都要做两次半宽的查找总面积比 for 循环略大一些但换来的是时序大幅改善。对于时序紧张的设计这个面积代价完全值得。我也遇到过另一种情况位宽32在一个已经堆了很多组合逻辑的模块里再插一个二分树面积有点捉襟见肘。这个时候我会考虑下面要说的多周期状态机方案把组合逻辑压力转移到时钟周期上。4. 方法三多周期状态机资源和时钟的取舍4.1 什么时候必须考虑多周期看到这里你可能会问二分树已经把延迟压到 logN 了还不够吗不够这里有个前提二分树是纯组合逻辑它输入一变输出立刻要稳定。如果输入端是一个频率很高的数据流组合逻辑延迟直接卡在关键路径上再好的树形结构也有物理极限。还有一种情况位宽特别大比如512位二分树需要9层比较如果外部逻辑也很重还是会卡时序。这时候与其追求“一条组合逻辑搞定”不如换个思路把查找拆成多个时钟周期每个周期只检查一小段。状态机的组合逻辑只有一个位的比较器所以单级延迟极低主频可以拉得很高。代价是结果晚几个周期才出来但对于控制类场景比如配置寄存器、初始化流程完全不是问题。我之前做过一个以太网 MAC 的配置模块需要在几百个寄存器里找某个置1的状态位状态机跑几十个周期也没人介意因为本来就不是高速通路。4.2 状态机设计思路与代码设计思路很简单锁存输入向量到移位寄存器每个周期看最低位是否为1如果是记录当前计数值并置 valid如果不是右移一位、计数器加1。直到计数达到 WIDTH-1 还没有遇到1说明输入全0valid 置0返回空闲状态。下面是一个找最低位1的多周期版本module find_one_seq #( parameter WIDTH 8 )( input wire clk, input wire rst_n, input wire [WIDTH-1:0] din, input wire start, output reg [$clog2(WIDTH)-1:0] pos, output reg done, output reg valid ); localparam IDLE 2d0; localparam SCAN 2d1; localparam DONE 2d2; reg [1:0] state; reg [WIDTH-1:0] data_shadow; reg [$clog2(WIDTH)-1:0] idx; always (posedge clk or negedge rst_n) begin if (!rst_n) begin state IDLE; done 1b0; valid 1b0; pos 0; end else begin case (state) IDLE: begin done 1b0; if (start) begin data_shadow din; idx 0; state SCAN; end end SCAN: begin if (data_shadow[0]) begin pos idx; valid 1b1; state DONE; end else if (idx WIDTH - 1) begin valid 1b0; state DONE; end else begin data_shadow data_shadow 1; idx idx 1b1; end end DONE: begin done 1b1; state IDLE; end endcase end end endmodule这个状态机的数据通路只有一个移位寄存器、一个比较器和一个计数器组合逻辑延迟几乎可以忽略。边界处理要特别小心idx WIDTH - 1时如果当前最低位还是0说明从 bit0 到 bitWIDTH-1 全都扫描过了全是0所以直接结束valid 清0。这个判断必须在移位之前做不然扫描到最后一位时会多移一次导致结果错位。4.3 三种实现方案对比三种方案各有各的适用场景我整理了一张对比表方便以后选型直接查实现方案组合逻辑级数延迟面积适用场景for 循环遍历O(WIDTH)一个周期小位宽小8/16、要求单拍出结果二分查找树O(log2(WIDTH))一个周期中位宽大、要求单拍出结果、时序紧多周期状态机O(1)最多 WIDTH 个周期中位宽极大、主频高、允许延迟注意“多周期状态机面积中”是指总面积中等不是最小。它的组合逻辑面积最小但额外消耗了寄存器和状态机资源。如果项目里寄存器资源紧张反而前两种更合适。具体选哪个我的习惯是先问两句话第一句“这个查找结果能不能等几个周期”第二句“位宽到底多大”。如果答案都是“不能等、很大”那就老老实实二分树如果“可以等”多周期状态机往往最省心因为时序路径几乎不用管。5. 仿真验证与常见问题排查5.1 Testbench 设计随机激励 自动检查写 RTL 不仿真等于没写。找1位置这种逻辑人工盯波形太累建议直接写一个带参考模型的 Testbench自动比对所有随机输入。参考模型用高级思路实现比如用 for 循环计算期望的 pos再把 DUT 的输出和期望值做对比出错就打印详细信息。下面这段 Testbench 可以直接用module find_one_tb; parameter WIDTH 8; reg [WIDTH-1:0] din; wire [clog2(WIDTH)-1:0] pos; wire valid; integer i; integer err_cnt; function integer clog2; input integer value; integer i; begin clog2 0; for (i value - 1; i 0; i i 1) clog2 clog2 1; end endfunction function integer ref_pos; input [WIDTH-1:0] data; integer j; begin ref_pos 0; for (j 0; j WIDTH; j j 1) if (data[j]) ref_pos j; end endfunction find_one_high #(.WIDTH(WIDTH)) dut ( .din (din), .pos (pos), .valid(valid) ); initial begin err_cnt 0; // 随机向量 for (i 0; i 10000; i i 1) begin din $random; #1; if (valid (pos ! ref_pos(din))) begin $display(MISMATCH: din%b, pos%0d, ref%0d, din, pos, ref_pos(din)); err_cnt err_cnt 1; end if (!valid (din ! 0)) begin $display(VALID_ERR: din%b, valid0, din); err_cnt err_cnt 1; end end // 边界向量 din 8b0000_0000; #1; if (valid ! 1b0) begin $display(FAIL: all-zero case, valid%b, valid); err_cnt err_cnt 1; end din 8b0000_0001; #1; if (!valid || (pos ! 0)) begin $display(FAIL: din0x01, pos%0d, pos); err_cnt err_cnt 1; end din 8b1000_0000; #1; if (!valid || (pos ! 7)) begin $display(FAIL: din0x80, pos%0d, pos); err_cnt err_cnt 1; end if (err_cnt 0) $display(ALL TESTS PASSED); else $display(TOTAL ERRORS: %0d, err_cnt); $finish; end endmodule注意事项有两个。一个是#1这个延时不能省它让组合逻辑有足够时间稳定再采样避免仿真器时序竞争带来的假错。另一个是参考模型里的 ref_pos 函数方向要和 DUT 保持一致如果 DUT 找最高位1ref_pos 也要从0到WIDTH-1循环如果 DUT 找最低位1ref_pos 要从 WIDTH-1 降到0。5.2 用 Icarus Verilog 快速验证很多人入门时用的是商用仿真工具其实在验证这种小模块时开源的 Icarus Verilog 足够用了。安装方式这里不展开装好之后三条命令就能跑iverilog -o find_one_sim find_one.v find_one_tb.v vvp find_one_sim第一条命令把设计文件和 Testbench 一起编译成可执行文件第二条命令跑仿真。看到ALL TESTS PASSED就说明 DUT 行为和参考模型一致。如果没有打印就需要检查是不是代码里有语法错误或者 clog2 函数实现得不对。Icarus Verilog 对$clog2的支持跟版本有关老版本可能不认。所以我上面的 RTL 和 Testbench 里都用了自定义的 clog2 函数目的就是让这套代码在开源工具里也能直接跑通。如果你用的工具支持$clog2直接把自定义函数替换掉也完全可以。5.3 常见问题的现场排查我把自己在仿真和综合中遇到的典型问题整理成了速查表你在项目里碰到可以直接对照现象可能原因处理建议valid 恒为0但输入明明有1pos 和 valid 写成时序逻辑却没有在敏感列表里加 clk确认 always 块是(*)还是(posedge clk)别混用pos 始终是最低位1的位置循环方向写反确认要找最高位还是最低位按 2.1 节检查循环方向仿真结果对综合结果不理想for 循环展开链太长位宽大于32后建议换二分树din 全0时 pos 输出不定值没有赋默认值always 块开头加pos 0;Icarus 报 $clog2 不支持工具版本旧用自定义 clog2 函数替代多周期状态机扫描到 WIDTH-1 时多移了一次边界判断放在了移位之后先把是否到末尾的判断放在移位之前还有一个很容易被忽略的坑位置基准从1开始。如果外部协议规定位置从1开始很多人的做法是把 pos 定义成[$clog2(WIDTH)-1:0]并直接加1结果位宽不够最高位溢出。正确做法是内部仍然用0基准在输出端口再做一次pos 1b1并且把输出位宽设计成$clog2(WIDTH1)或者接受最高位溢出被截断的风险。后者在综合时很容易出警告不建议用。最后分享一个扩展思路如果你已经理解了上面三种基本方法我再补充一个实用技巧。在很多场景里你不仅要找最高位1或最低位1还要反复循环使用比如轮询仲裁。第一次找最低位1下一次要从它的下一位置开始找。这并不需要重新设计电路只需要把输入向量之前已经服务过的低位置成0再调用你手上的最低位查找模块即可。简单说就是“掩码 查找”组合拳很多成熟的仲裁器 IP 就是这么实现的。我自己在实际操作中的体会是这类基础模块代码往往写不了几行难的是搞清楚每个方案背后的时序、面积、延迟取舍。建议你拿到手别急着写先用一张纸把输入位宽、时钟频率、允许延迟三个数字列出来再决定选哪种方案。这样比写完再改要省太多时间。