找到序列最高位的1和最高位的0并输出位置-Toy模板网

这篇具有很好参考价值的文章主要介绍了找到序列最高位的1和最高位的0并输出位置。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言：

该题为睿思芯科笔试题，笔试时长20分钟。

题目描述

接口如下：

module first_1_and_0#(
    parameter WIDTH = 8
)(
    input   [WIDTH-1:0]         data_in ,
    input                       target  ,
    output                      exist   ,
    output  [$clog2(WIDTH):0]   pos
);

target可以等于1，也可以等于0。当target等于1时，检测data_in最高位的1，并输出其位置，位置计数从0开始。举例：当target=1时，序列4'b0101，存在1，所以输出exist = 1，检测1的位置pos=1。

题目解析

找到序列第一个1的位置，可以参考笔者本篇博客：不用循环和分治，仅用“按位”操作，找到序列第一个1和最后一个1

找到第一个0的位置，可以利用同样的思想。首先给pre最高位赋1，然后pre的低7位等于pre的高7位和data的高7位相与，这里可能会产生一个疑问，明明pre的低7位都没赋值，都是x，怎么能直接取高7位来和data做或，那输出不都是x吗？

是这样的，pre[7]=1，在比较的时候，是1bit 1bit比较，因此组合逻辑会先计算pre[6]=pre[7] & data[7]。得到pre[6]的结果后，再计算pre[6] & data[6]，以此类推。这个方法妙就妙在当算出1bit的pre为0时，后面的所有pre都为0，譬如data=8'b1110_1101

pre[7]=1

pre[6]=pre[7] & data[7]=1

pre[5]=pre[6] & data[6]=1

pre[4]=pre[5] & data[5]=1

pre[3]=pre[4] & data[4]=0

pre[2]=pre[1]=pre[0]=0

这样，再对pre进行按位取反的时候：

data=8'b1110_1101

pre =8'b1111_0000

这时候，我们再利用性质：一个数和它自身的补码相与，结果为最低位的1。

找到pre的最低位的1：pre & ~(pre - 1)=8'b0001_0000，这时候one_hot码1的位置就是data中最高位0的位置了。

利用(WIDTH-$clog2(one_hot_0)-1)就可以输出0的position了，代码如下：

代码

module first_1_and_0#(
    parameter WIDTH = 8
)(
    input   [WIDTH-1:0]         data_in ,
    input                       target  ,
    output                      exist   ,
    output  [$clog2(WIDTH):0]   pos
);

// signal defination
wire [WIDTH-1:0] find_1_pre,find_0_pre;
wire [WIDTH-1:0] one_hot_1,one_hot_0;
wire             exist_1,exist_0;
wire [$clog2(WIDTH):0] pos_0,pos_1; 

//find first 1
assign find_1_pre[WIDTH-1] = 0;
assign find_1_pre[WIDTH-2:0] = find_1_pre[WIDTH-1:1] | data_in[WIDTH-1:1];

assign one_hot_1 = data_in & (~find_1_pre);
assign exist_1 = |data_in;
assign  pos_1 = exist_1 ? (WIDTH-$clog2(one_hot_1)-1): 0;

//find first 0
assign find_0_pre[WIDTH-1] = 1;
assign find_0_pre[WIDTH-2:0] = find_0_pre[WIDTH-1:1] & data_in[WIDTH-1:1];

assign one_hot_0 = find_0_pre & ~(find_0_pre-1);
assign exist_0 = !(&data_in);
assign pos_0 = exist_0 ? (WIDTH-$clog2(one_hot_0)-1): 0;

//output 
assign exist = target ? exist_1 : exist_0;
assign pos   = target ? pos_1   : pos_0  ;

endmodule

testbench

module tb#(
    parameter WIDTH = 8
)();

reg target;
reg [WIDTH-1:0] data_in;
wire exist;
wire [$clog2(WIDTH):0] pos;

initial begin 
    target  =  1'b0;
    data_in =  8'd0;
#10
    target  =  1'b1;
#10
    data_in =  8'b11111111;
    target  =  1'b1;
#10
    target  =  1'b0;
    data_in =  8'b10110110;
    target  =  1'b0;
#10
    target  =  1'b1;
#10
    data_in =  8'b00110101;
    target  =  1'b0;
#10
    target  =  1'b1;
#10
    $finish();
end

first_1_and_0 u_first(
    .target (target     ),
    .data_in(data_in    ),
    .exist  (exist      ),
    .pos    (pos        )
);

initial begin
    $fsdbDumpfile("first_1_and_0.fsdb");
    $fsdbDumpvars(0);
end
endmodule