Bit hacks

Power of 2 detector

( x & (x-1) ) == 0

E.g.:

x = 8'b0100_0000

x-1 = 8'b0011_1111

& = 8'b0000_0000 <- So "x" is a valid power of 2 number.

Hunt for 1

( x & ~(x-1) )

E.g.:

x = 8'b0101_0000

x-1 = 8'b0100_1111

~(x-1) = 8'b1011_0000

& = 8'b0101_0000 & 8'b1011_0000

8'b0001_0000 <- Hunt for 1 from LSB

Square root - Newton-Raphson method

Not good for implementation - division

Checkout the Goldschmidt's algorithm

This algorithm finds an approximate root of a number with better result on sucessive iteration.

Algorithm:

xn+1 = (0.5) (xn + a/xn)

  • First you take a approximate value of the root for a unsigned integer "a", which will be X0

  • Now compute the X1 based on the formula

  • On sucessive iteration, the result will move closer to squere root of "a"


Wikipedia screenshot below:

https://en.wikipedia.org/wiki/Newton%27s_method