Convert x >= y into 1 or 0 without branching or Boolean expressions

Question

I need to implement the following function without branching or Boolean expressions:

uint8_t func(uint32_t num, uint8_t shl)
{
    if (num >= (1 << shl))
    {
        return shl;
    }
    else
    {
        return 0;
    }
}

The first step I did was to notice that the else part is easy:

return num / (1 << shl);

Of course, doing this in the if part will not necessarily yield the desired result.

So I guess I need something a little more "clever" than num / (1 << shl).

If I could come up with an expression that would give me 1 or 0, then I'm done.

Is there some sort of way to do this using only arithmetic/bitwise operations (i.e., no branching or Boolean expressions)?

Thank you.

Answer 1

You could treat the condition as a boolean expression that evaluates to TRUE (1) or FALSE (0), so you can go with something like this:

return (num >= (1 << shl)) * shl;

This code is generally not a good idea, but under the no-branching constraint, it does the job.

Answer 2

If you would like to avoid comparison operators, you can use subtractions and bit shifts to probe the sign bit:

uint8_t func(uint32_t num, uint8_t shl) {
    return shl * (1 - ((num-(1<<shl)) >> (sizeof(num) * CHAR_BIT -1)));
} 

Demo.

Answer 3

Assuming, that your implementation does arithmetic shift (which is usually the case) as well as two's complement arithmetic, you could take advantage of sign bit propagation:

uint8_t func(uint32_t num, uint8_t shl)
{
    return (-(int32_t)(num >> shl) >> 31) & shl;
}

which may translate into branch-less x86 assembly code:

func(unsigned int, unsigned char):
  mov eax, edi
  mov ecx, esi
  shr eax, cl
  neg eax
  sar eax, 31
  and eax, esi
  ret

The main idea is that left operand of & is either all ones or all zeros, which means that value of shl is either preserved or zeroed.

Most tricky part is -(int32_t)(num >> shl). It builds on facts, that:

• num / (1 << shl) expression is essentially the same as num >> shl
• right-shifting of unsigned value always pads left bits with zeros
• when shl == 0, the result is always 0 (i.e. value of &'s left operand is meanignless, as it will be discarded by shl anyway)