# Location of Most Significant ‘ON’ Bit

This algorithm is little complex and is based on binary seach mechanism, mainly hardware version of the binary search. This algorithm is explained in brief here. Please post your question if you need more information. Basic operation in the algorithm is that number of bits can be divided into two sub sections and operations on these two subsections can be performed in parallel.

This algorithm performs following steps

• Divide 32 bit number in 2 16-bit numbers
• Determine if Significant portion [31:16] is zero or not. If [31:16] is zero, perform search on [15:0] and else perform search on [31:16].
• If search is being performed on [31:16], Add 16 to index in the number.
• Repeat above operation, i.e. divide 32 bit into 2 16-bit, divide 16-bit into 2 8-bit number, & so on.

 Proposed Binary Search Based Algorithm module only1 (       input wire [31:0] inb,       input wire clk,       input wire rst_n,       output reg [4:0] loc,       output reg val       );       reg if_1;       reg [4:0] nval;       integer i;       always @(*) begin          if_1 = 0;          nval = 0;          if (inb[31:16] == 0) begin             if (inb[15:8] == 0) begin                if (inb[7:4] == 0) begin                   if (inb[3:2] == 0) begin                      if (inb[1:0] == 0) begin                         if_1 = 0;                      end else begin                         nval = inb;                         if_1 = 1;                      end                   end else begin                      nval = inb + 'b10;                      if_1 = 1;                   end                end else begin                   if (inb[7:6] == 0) begin                      nval = inb + 'b100;                      if_1 = 1;                   end else begin                      nval = inb + 'b110;                      if_1 = 1;                   end                end             end else begin                if (inb[15:12] == 0) begin                   if (inb[11:10] == 0) begin                      nval = inb + 'b1000;                      if_1 = 1;                   end else begin                      nval = inb + 'b1010;                      if_1 = 1;                   end                end else begin                   if (inb[15:14] == 0) begin                      nval = inb + 'b1100;                      if_1 = 1;                   end else begin                      nval = inb + 'b1110;                      if_1 = 1;                   end                end             end          end else begin                if (inb[31:24] == 0) begin                   if (inb[23:20] == 0) begin                      if (inb[19:18] == 0) begin                         nval = inb + 'b10000;                         if_1 = 1;                      end else begin                         nval = inb + 'b10010;                         if_1 = 1;                      end                   end else begin                      if (inb[23:22] == 0) begin                         nval = inb + 'b10100;                         if_1 = 1;                      end else begin                         nval = inb + 'b10110;                         if_1 = 1;                      end                   end                end else begin                   if (inb[31:28] == 0) begin                      if (inb[27:26] == 0) begin                         nval = inb + 'b11000;                         if_1 = 1;                      end else begin                         nval = inb + 'b11010;                         if_1 = 1;                      end                   end else begin                      if (inb[31:30] == 0) begin                         nval = inb + 'b11100;                         if_1 = 1;                      end else begin                         nval = inb + 'b11110;                         if_1 = 1;                      end                   end                end             end       end       always @(posedge clk or negedge rst_n) begin          if (~rst_n)                loc <= 1'b0;          else                loc <= nval;       end       always @(posedge clk or negedge rst_n) begin          if (~rst_n)                val <= 1'b0;          else                val <= if_1;       end endmodule

HW performance is

• Complexity – 6/10 on simplicity scale. (More the better – Little Subjective)
• Basic Gate Count & Timing –  Area is 1300.6 micron2 (Less the better), Critical Path Delay 2.74ns(Less the better)
• Optimizable – Area is 1862 micron2(Less the better), Critical Path Delay 0.85ns (Less the better)

Next: Conclusion