n

y

x

half(y) = lsb(2y)

half(2y) = lsb(4y)

half(4y) = lsb(8y)

half(8y) = lsb(16y)

. . .

3n/4

n/4

y