If order of the cyclic group on which discrete logarithm is done is $2q$ where $q$ is a prime such that $2q+1$ is a prime, then using square root identification we can get the lsb.
Two things:
That's true only if the 'base' your compute the discrete log on is a quadratic nonresidue (for example, a generator). If your case is, say, 4 (which is obviously not a quadratic nonresidue to any base), then computing whether $4^x$ is a quadratic residue will reveal nothing about $x$.
This remains true no matter if $q$ is prime or not.
How about if the order is $2^rq$ where $r\in\mathbb Z_{\geq1}$, can we extract the least significant $r$ bits in polynomial time?
You sure can! (assuming, of course, the base cooperates; for now, I'll assume that value $g$ is a generator of the entire group).
The most straight-forward way to proceed is to use the general property that if $s | p-1$, then a value $x$ is within the subgroup of size $s$ iff $x^{s} = 1$
So, if we are given $x = g^y$ (for some unknown $y$), and we want to determine whether $y \equiv k \pmod {2^r}$, then we just compute
$$(x \cdot g^{-k}) ^ {q}$$
That is 1 iff $y \equiv k \pmod {2^r}$
And, if $r$ is so huge to make going through the possibilities prohibitive, it is easy to break up the problem into smaller chunks (and I'll leave how to do that as an exercise for the reader).
Here's how it works, the value $y-k \equiv 0 \pmod {2^r}$ iff the lower $r$ bits of $y$ are precisely $k$. In addition, the value $g^{y-k}$ is a member of the subgroup of size $q$ iff $y-k \equiv 0 \pmod {2^r}$, and by the general property, that can be tested by checking $(g^{y-k})^q$.
(Actually, this can be converted into a way to extract one bit at a time; that would be more efficient - I found this approach the easiest way to explain it)
This extends in the obvious way if $p-1$ has small odd factors...
