§ Медленный поиск

Часто в жизни возникает ситуация, когда хочется найти первый значимый бит. Сделать это можно двумя методами — быстрым и медленным. Но сначала я расскажу, что я собираюсь искать. Представим, что есть некоторое двоичное число:
00001010101000010
Видно, что первые 4 бита у него — нули, это означает, что они ничего не значат. Как найти количество нулевых битов? Очень просто, надо лишь только их подсчитать. Для подсчета 4 битов потребуется 4 такта, а на 5-м такте будет ясно видно, что там 1, и счет закончен. Это медленный поиск, который дает результат, но слишком медленно. Есть гораздо более быстрый поиск.

§ Быстрый поиск

Теперь берем еще один пример числа, 16 битное:
0000000000010110
Вместо того, чтобы считать все, делим число пополам (шаг 1):
00000000 00010110
Легко заметить, что первые 8 бит нули, и потому гарантированно 8 первых бит будут учтены как незначимые.
Удаляем эти нули из выдачи и делим правый остаток на 2 части (шаг 2):
0001 0110
А вот теперь первые 4 бита не все нули, так что теперь надо разделить на 2 части левое значение 0001 (шаг 3):
00 01
И появились нули, отчего можно добавить +2 к тому +8, что было раньше. Удаляем эти два нуля и делим на 2 то, что осталось (шаг 4):
0 1
А осталось то с гулькин нос, то есть, еще один незначимый нуль. +1 в карму.
Итого, за 4 шага определилось, что нулей впереди +8 +2 +1, аж 11 штук! Это и называется, бинарный поиск, эффективно, и всегда за 4 шага для 16 бит, за 5 шагов для 32 бита.
Есть один интересный нюанс. После того как все шаги были пройдены, может остаться последний 0, 16-й, который тоже можно учесть.

§ Код на верилоге

Теперь надо сделать так, чтобы на выходе модуля был вход, а на выходе — соответственно, выход:

1module signbit
2(
3    input [31:0] a,
4    output [4:0] b
5);
6endmodule

Теперь надо выполнить несколько простых шагов, а именно проверить левую часть a и в случае чего, получить необходимый результат:

1assign b[4] = ~|a[31:16];
2wire [15:0] t1 = b[4] ? a[15:0] : a[31:16];

В b[4] будет 1, если все нули в битах 31..15. На проводе t1 берется правая или левая часть в зависимости от того, есть ли полностью все нули в левой части или нет.
Второй этап будет выглядеть следующим образом.

1assign b[3] = ~|t1[15:8];
2wire [7:0] t2 = b[3] ? t1[7:0] : t1[15:8];

Третий этап:

1assign b[2] = ~|t2[7:4];
2wire [3:0] t3 = b[2] ? t2[3:0] : t2[7:4];

Четвертый этап:

1assign b[1] = ~|t3[3:2];
2wire [1:0] t4 = b[1] ? t3[1:0] : t3[3:2];

И наконец, для пятого этапа ничего не требуется, кроме разве что подсчета оставшегося бита:

1assign b[0] = ~t4[1];

Если он будет 0, то учитывается, иначе не учитывается.
Несмотря на то, что метод получился гораздо быстрее, все же требуется каскад из 5 слоев для того, чтобы подсчитать количество нулевых бит вначале. Аналогично можно считать и количество единиц, для этого нужно переделать функцию определения с ~| на &.

§ Полный код модуля

For Commercial Purposes Only — гласит надпись на вывеске, но я просто оставлю это здесь.

1module signbit
2(
3    input [31:0] a,
4    output [4:0] b
5);
6
7wire [ 4:0] b  = {~|a[31:16], ~|t1[15:8], ~|t2[7:4], ~|t3[3:2], ~t4[1]};
8wire [15:0] t1 = b[4] ? a[15:0] : a[31:16];
9wire [ 7:0] t2 = b[3] ? t1[7:0] : t1[15:8];
10wire [ 3:0] t3 = b[2] ? t2[3:0] : t2[7:4];
11wire [ 1:0] t4 = b[1] ? t3[1:0] : t3[3:2];
12
13endmodule

Такова жизнь, ничего не поделаешь. Я даже не проверял эту схему, а надо бы.