Regex (ECMAScript), 85 73 71 bytes
^((?=(x*?)\2(\2{4})+$|(x*?)(\4\4xx)*$)(\2\4|(x*)\5\7\7(?=\4\7$\2)\B))*$
Try it online!
explanation by Deadcode
The earlier 73 byte version is explained below.
^((?=(x*?)\2(\2{4})+$)\2|(?=(x*?)(\4\4xx)*$)(\4|\5(x*)\7\7(?=\4\7$)\B))+$
Because of the limitations of ECMAScript regex, an effective tactic is often to transform the number one step at a time while keeping the required property invariant at every step. For example, to test for a perfect square or a power of 2, reduce the number in size while keeping it a square or power of 2 (respectively) at every step.
Here is what this solution does at every step:
If the rightmost bit is not a 1
, the rightmost 1
bit (if it is not the only 1
bit, i.e. if the current number is not a power of 2) is moved one step to the right, effectively changing a 10
to a 01
(for example, 11011000 → 11010100 → 11010010 → 11010001), which has no effect on the number's binary-heaviness. Otherwise, the rightmost 01
is deleted (for example 10111001 → 101110, or 1100111 → 11011). This also has no effect on the number's heaviness, because the truth or falsehood of \$ones>zeroes\$ will not change if \$1\$ is subtracted from both; that is to say,
\$ones>zeroes⇔ones-1>zeroes-1\$
When these repeated steps can go no further, the end result will either be a contiguous string of 1
bits, which is heavy, and indicates that the original number was also heavy, or a power of 2, indicating that the original number was not heavy.
And of course, although these steps are described above in terms of typographic manipulations on the binary representation of the number, they're actually implemented as unary arithmetic.
# For these comments, N = the number to the right of the "cursor", a.k.a. "tail",
# and "rightmost" refers to the big-endian binary representation of N.
^
( # if N is even and not a power of 2:
(?=(x*?)\2(\2{4})+$) # \2 = smallest divisor of N/2 such that the quotient is
# odd and greater than 1; as such, it is guaranteed to be
# the largest power of 2 that divides N/2, iff N is not
# itself a power of 2 (using "+" instead of "*" is what
# prevents a match if N is a power of 2).
\2 # N = N - \2. This changes the rightmost "10" to a "01".
| # else (N is odd or a power of 2)
(?=(x*?)(\4\4xx)*$) # \4+1 = smallest divisor of N+1 such that the quotient is
# odd; as such, \4+1 is guaranteed to be the largest power
# of 2 that divides N+1. So, iff N is even, \4 will be 0.
# Another way of saying this: \4 = the string of
# contiguous 1 bits from the rightmost part of N.
# \5 = (\4+1) * 2 iff N+1 is not a power of 2, else
# \5 = unset (NPCG) (iff N+1 is a power of 2), but since
# N==\4 iff this is the case, the loop will exit
# immediately anyway, so an unset \5 will never be used.
(
\4 # N = N - \4. If N==\4 before this, it was all 1 bits and
# therefore heavy, so the loop will exit and match. This
# would work as "\4$", and leaving out the "$" is a golf
# optimization. It still works without the "$" because if
# N is no longer heavy after having \4 subtracted from it,
# this will eventually result in a non-match which will
# then backtrack to a point where N was still heavy, at
# which point the following alternative will be tried.
|
# N = (N + \4 - 2) / 4. This removes the rightmost "01". As such, it removes
# an equal number of 0 bits and 1 bits (one of each) and the heaviness of N
# is invariant before and after. This fails to match if N is a power of 2,
# and in fact causes the loop to reach a dead end in that case.
\5 # N = N - (\4+1)*2
(x*)\7\7(?=\4\7$) # N = (N - \4) / 4 + \4
\B # Assert N > 0 (this would be the same as asserting N > 2
# before the above N = (N + \4 - 2) / 4 operation).
)
)+
$ # This can only be a match if the loop was exited due to N==\4.