8

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)?

halfer
  • 19,824
  • 17
  • 99
  • 186
goodvibration
  • 5,980
  • 4
  • 28
  • 61
  • Is this a homework assignment? Why do you need to avoid branching? – lurker Jul 31 '17 at 10:14
  • 1
    @lurker: No homework assignment (and what does that matter anyway?????). I need to avoid branching in order to optimize performance. I'm actually invoking this code from inside a loop, not in a function (depicted here in order to simplify the question and focus on the problem). – goodvibration Jul 31 '17 at 10:15
  • 1
    @goodvibration What compiler are you using? What does the generated asm look like? – melpomene Jul 31 '17 at 10:15
  • 3
    Depending upon the alternatives, branching may not be less optimal. Why not just ask what the most optimal way to implement that function would be? The answer might also depend upon the platform and compiler. – lurker Jul 31 '17 at 10:15
  • @lurker: I'll make you a deal. You give me whatever alternatives you can think of, and I'll let you know if they are better than my current branch solution. – goodvibration Jul 31 '17 at 10:17
  • 7
    @goodvibration That's not how this site works. Questions should be as clear and precise as possible to be easily answerable and searchable for future readers. – user694733 Jul 31 '17 at 10:19
  • @user694733: What's not clear about my question, and how exactly did my comment above lead you to imply that I want an answer regardless of the **alleged** ill-phrasing of my question????? – goodvibration Jul 31 '17 at 10:24
  • 7
    Premature optimization is *evil*. You have to *prove* that there's a performance issue in your code before attempting manual optimizations. And then, please fix your `?` key. –  Jul 31 '17 at 10:29
  • would (x - y) >> 31 work? – Theo Walton Jul 31 '17 at 10:30
  • 1
    As stated by others, answers can wary greatly depending your platform and compiler which haven't been specified, and you also haven't shown generated asm like was asked. As a result several answers (3 so far I think) have been deleted. Question is unclear to people. Please [edit] to provide clarifications and make sure they are they are not wasting their time for nothing. – user694733 Jul 31 '17 at 10:32
  • @TheoWalton: Counterexample: `x = 1<<29` and `y = 1<<28`. – goodvibration Jul 31 '17 at 10:44
  • to work faster you can make an array with the precomputed values of `1< – alinsoar Jul 31 '17 at 11:37
  • `(1 << shl)` is not portable due shifting into the sign bit . Better to use `((uint32_t)1 << shl)`. – chux - Reinstate Monica Jul 31 '17 at 13:52
  • 1
    @goodvibration what's unclear is your actual intent. You said in an early comment, *I need to avoid branching in order to optimize performance.*. But your original question says nothing about performance, nor what aspect of performance you're referring to (time? space?). Also, it's unclear that avoiding branching will, indeed, optimize performance since this can depend upon platform and compiler. So do you just want to avoid branching, or do you want to optimize some aspect of performance? The first doesn't necessarily imply the latter. – lurker Aug 03 '17 at 14:12

4 Answers4

6

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.

Eran Zimmerman Gonen
  • 4,375
  • 1
  • 19
  • 31
  • 4
    @goodvibration branching is a *conditional jump*. Those instructions do not produce any conditional branch. Instead, a *comparison* operation is done. In case, you should specify you don't want comparison operations, but only arithmetic and shifting – BiagioF Jul 31 '17 at 10:16
  • @BiagioFesta: Didn't I say "using only arithmetic/bitwise operations"??? – goodvibration Jul 31 '17 at 10:19
  • 3
    @goodvibration yeah, but you said "without branching". This answer is, indeed, without branching. – BiagioF Jul 31 '17 at 10:20
  • @BiagioFesta: Unfortunately, I cannot convert `bool` to `uint` on my platform, so that doesn't help much. But you're right, I should add "no comparison operations"). – goodvibration Jul 31 '17 at 10:20
  • @goodvibration You said "*without branching (`if`/`else`)*". This answer doesn't use `if` or `?:`. – melpomene Jul 31 '17 at 10:21
  • 5
    "*I cannot convert `bool` to `uint` on my platform*" <- when using C, you can. –  Jul 31 '17 at 10:22
  • 1
    ? : is the same branching in the resulting code as if. Your comment\s are wrong https://godbolt.org/g/3xV1C3 – 0___________ Jul 31 '17 at 10:25
  • 2
    @PeterJ What are you even talking about? No one's using `?:`. – melpomene Jul 31 '17 at 10:26
  • 3
    Unless the machine has conditional execution of instructions to assign a value, I doubt that you can evaluate the `>=` without conditional branch instructions. For the compiler this is not much different from `if ... else ...`. While you can avoid the `if` in C, the compiler cannot avoid creating instructions to fetch either one of the result values. – Gerhardh Jul 31 '17 at 11:04
  • @Gerhardh of course the assembly code generated from this expression *probably* contains some branch instruction. But that's outside of the scope of C and impossible to know for sure without the target machine and the compiler used. If OP is interested in this, the question should be asked differently. –  Jul 31 '17 at 11:26
  • @BiagioFesta The point is, that, until very recently *all* conditional expressions were compiled to conditional branch instructions. So, `if(i < 42) return 1; return 0;`, `return i < 42 ? 1 : 0;`, and `return i < 42` all produced branching instructions on all platforms. Only recently (around five years ago?) have CPUs added conditional moves to their instruction sets. And now, modern compilers should be able to compile all these three code snippets to the same code. This answer includes as much branches as the OP. – cmaster - reinstate monica Jul 31 '17 at 20:52
4

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.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • 2
    And the `31` stands for `sizeof(num) * CHAR_BIT -1`? – goodvibration Jul 31 '17 at 10:34
  • 1
    Btw, this is wrong in general. Unsigned types might contain padding bits. [Here's a safe way to know the number of value bits](https://stackoverflow.com/a/4589384/2371524). And then, I wouldn't talk about a *sign bit* in an unsigned type. –  Jul 31 '17 at 10:39
  • Yes, the `num-(1< – goodvibration Jul 31 '17 at 10:40
  • But then, as `uint32_t` is an exactly-sized type, we **know** that it has 32 value bits. So just hard-coding `31` here would be safe, while `sizeof(num) * CHAR_BIT -1` has the slight possibility of returning some larger number. –  Jul 31 '17 at 10:42
  • 1
    Using a `(uint32_t) 1 << shl` makes more sense than an `(int)` with `1< – chux - Reinstate Monica Jul 31 '17 at 13:57
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)
Grzegorz Szpetkowski
  • 36,988
  • 6
  • 90
  • 137
-3

What about?

bool func( int32_t num, int8_t shl)
{
  return (num>=(1<<shl));
}
  • Return 1 if x>=(1<<y)
  • Return 0 if x<(1<<y)
Suraj Rao
  • 29,388
  • 11
  • 94
  • 103
Sumerin
  • 1