ARM Thumb-2 (alternative), 16 bytes
Alternative approach which mirrors this x86 answer although it is just as small to maintain the bool return value.
Since we need to mov the result to r0 anyways, we can invert the operation and use that opcode to return the sign bit.
Raw machine code:
2100 0840 bf2c 3901 3101 d1fa 0fc8 4770
Uncommented Assembly:
.syntax unified
.arch armv6t2
.globl binary_heavy
.thumb
.thumb_func
binary_heavy:
movs r1, #0
.Lloop:
lsrs r0, r0, #1
ite cs
subcs r1, #1
addcc r1, #1
bne .Lloop
.Lloop_end:
lsrs r0, r1, #31
bx lr
The explanation is the same as the original one, but instead of adding to two different variables, we are adding and subtracting from the same variable, and returning the sign bit by doing a logical right shift by 31.
ARM Thumb-2 (previous approach), 22 20 bytes
Longer but uses an original idea.
Raw machine code:
2101 2200 0840 bf2c 3201 3101 d1fa 428a
4140 4770
Uncommented Assembly:
.syntax unified
.arch armv6t2
.globl binary_heavy
.thumb
.thumb_func
binary_heavy:
movs r1, #1
movs r2, #0
.Lloop:
lsrs r0, r0, #1
ite cs
addcs r2, #1
addcc r1, #1
bne .Lloop
.Lloop_end:
cmp r2, r1
adcs r0, r0
bx lr
Explanation
We are about to do some wonky stuff with the condition codes, so you might want to look at the condition code table in this article if you aren't familiar with them.
C signature:
bool binary_heavy(uint32_t val);
First, set up r1 to count the zeros and r2 to count the ones.
Wait, why do we start with zeros = 1? You'll see.
binary_heavy:
movs r1, #1
movs r2, #0
Then, begin our loop. All the logic can be handled by how lsrs updates the flags.
lsrs does a logical right shift, stores the last bit shifted in the carry flag, and sets the zero and negative flags based on the result.
So we can basically do this logic using nothing but lsrs and some flag checking:
do {
if (val & 1) {
++ones;
} else {
++zeros;
}
} while (val >>= 1);
.Lloop:
lsrs r0, r0, #1
First, we do an IT block to add to either the ones count or the zeroes count.
ite cs
addcs r2, #1
addcc r1, #1
Thankfully, since most narrow instructions do not set flags in IT blocks, we can also use the same lsrs flags to check if the value is still non-zero and loop.
bne .Lloop
Here is why we set the zeros counter to 1.
We can do a shortcut if we can turn the condition into a greater than or equal. However, if the ones and zeros are equal, it is considered not binary heavy. That is why we need to start the zeros with 1, because we can offset it.
The shortcut? You guessed it, an add with carry!
- We know that
r0 is zero since if it wasn't, we'd be looping now.
- That means that
r0 will be 0 + 0 + carry.
- Greater than or equal means the carry flag is set
- Therefore, the carry flag being set means greater than or equal.
- Since we modified the zeros initial value, greater than or equal means that the number is binary heavy.
- Which means the carry flag is set if the number is binary heavy.
So we are essentially setting r0 to the carry flag, making it act as a boolean....and our return value.
.Lloop_end:
cmp r2, r1
adcs r0, r0
Return.
bx lr
