I need to use logic gates to calculate the floor of binary logarithm of a binary number $x_{n-1}, ..., x_0$.
I know that this can be computed when I find the position of the most significant bit set to 1.
So how do I find this bit and return it's position using only binary logic gates (AND, OR, XOR, NOR, NAND, NOT)?
You start by building a circuit for two input bits. It has two outputs: the position of the highest bit, either 0 or 1, and a bit indicating that the input is not zero. This is easy: The position is equal to bit 1 of the input, “non-zero” is bit 1 or bit 0.
Now you build a circuit with four input bits. You feed bits 3 and 2 into one two-bit circuit, and bits 1 and 0 into a second one. There are two bits for the bit position with a value from 0 to 3. The higher bit is set if the higher two bits are non-zero. The lower bit is equal to the position from the higher two bit circuit if it is non-zero, and taken from the lower two bit circuit otherwise. The inputs are non-zero if one of the two bit pairs is non-zero.
So if we have two 2-bit circuits C1 and C2, then pos1 = C1.nonzero, non-zero = C1.non-zero or C0.non-zero, and pos0 = (C1.nonzero and C1.pos) or (not C1.nonzero or C0.pos).
Now you build a circuit with eight input bits. Output is three bits position with a value 0 to 7 and a “nonzero” bit. Bits 7 to 4 go into one four-bit circuit, bits 3 to 0 into a second one. Again bit 2 of the position is taken from the non-zero bit of the first circuit, you OR the two non-zero bits together, and select the lower two bits from one of the two four bit circuits.
And then you create a 16, 32 and 64 bit circuit in the same way. So if you have 64 input bits, you need two 32-bit, four 16-bit, eight 8-bit, sixteen 4-bit, and thirty-two 2-bit circuits.
As pointed out in the comments, your question was already answered in Arithmetic network to compute floor of binary logarithm. If you turn that answer into a circuit diagram, it looks like this:
The 32 bit logarithm block shown here is build from two 16 bit logarithm blocks and a few extra gates. The AND-OR bank is simply a multiplexer. The output of the 0..15 sub-block is normally ignored (by the AND gates) unless the 16..31 sub-block produces an invalid result (input = output = all zeros, indicated by the zero flag). In this case, the output of the 0..15 sub-block becomes the overall output. The high bit (bit 4) of the overall output is set when any of bit 16..31 of the input is non-zero.
