CODEWITHSUNDEEP
cif-statement
gruszczy
gruszczy

Reputation: 42228

How can I rewrite this if-else statement so that it doesn't use a jump?

I am not trying to optimize anything, so please don't tell me, that premature optimization is root of all evil. I am trying to solve a problem and I can't find the third solution.

The problem goes like this:

if (x)
    y = a;
else
    y = b;

x can only be 0 or 1. How to write this condition without a jump?

One solution, with a data structure, is:

int temp[2] = {b, a};
y = temp[x];

Another arithmetic solution is:

y = x * a + (1 - x) * b;

There is supposed to be a third one, a logical solution. Do you know how it looks like? Please give a solution in C.

Upvotes: 4

Views: 591

Answers (10)

evnu
evnu

Reputation: 6690

EDIT: I misread the question which states that the C code shouldn't use a jump at all.

I think I'd go with

y = b;
if (x)
    y = a;

If I read the following disassembled code right, there should be only one jump:

0000000000400474 <main>:
  400474:   55                      push   %rbp
  400475:   48 89 e5                mov    %rsp,%rbp
  400478:   8b 45 fc                mov    -0x4(%rbp),%eax
  40047b:   89 45 f8                mov    %eax,-0x8(%rbp)
  40047e:   83 7d f4 00             cmpl   $0x0,-0xc(%rbp)
  400482:   74 06                   je     40048a <main+0x16>
  400484:   8b 45 f0                mov    -0x10(%rbp),%eax
  400487:   89 45 f8                mov    %eax,-0x8(%rbp)
  40048a:   c9                      leaveq
  40048b:   c3                      retq
  40048c:   90                      nop
  40048d:   90                      nop
  40048e:   90                      nop
  40048f:   90                      nop

Upvotes: -3

Michael Chinen
Michael Chinen

Reputation: 18727

This maybe isn't the best solution, but I think it is the bitwise equivalent without jumps:

y = (~(x*UINT_MAX) & a) | (~(1 - x) & b);

Upvotes: 2

Thomas Matthews
Thomas Matthews

Reputation: 57749

For processors that allow conditional execution of statements:

y = a;
if (x != 0) y = b;

On an ARM processor in 32 bit mode, this should translate into the following pseudo instructions:

mov y, a; move a into y.
test x; (or XOR X, X ; to set condition codes)
MOVNZ y, b ; move b into y if condition is non-zero.

No jumps involved here, at least at the assembly language level.

Note: platform specific solution, may not be valid for processors without conditional instruction execution capabilities.

Upvotes: 0

Lindydancer
Lindydancer

Reputation: 26164

The following code use the trick that, as x is either 1 or 0, x-1 is either 0 or -1 (a.k.a. 0xFFFFFFFF, assuming 32 bit int:s). If x is 1, the result of the & is zero, so the result is a. When x is zero, the result of the & will be b-a, the total result will then be a+(b-a) or simply b.

int test(int x, int a, int b)
{
  return a + ( (((unsigned int)x)-1) & (b - a) );
}

On a fictitious micro-controller (without any fancy conditional move instructions) this will result in four instructions:

ADD   #-1 R12
SUB   R13, R14
AND   R14, R12
ADD   R13, R12

Admittedly, this is very similar to the XOR solution posted by @6502.

Upvotes: 0

rajah9
rajah9

Reputation: 12339

I agree with Jens; a ternary operator will do the trick without a jump.

y = x ? a : b

BTW, there is a sister site, Code Golf, where people ask questions of the nature "How can I solve problem x with the shortest amount of code while maintaining constraint y?"

Upvotes: 0

Jens Gustedt
Jens Gustedt

Reputation: 79003

Use the ternary ?: operator. It is made for this.

Upvotes: 0

jcoder
jcoder

Reputation: 30055

Something like the choose function here then?

#include <stdio.h>

int choose(unsigned int x, int a, int b)
{
    unsigned int selector = -x;    

    return (a & selector) | (b & ~selector);
}

int main()
{
    printf("%d\n", choose(0, 123, 200));
    printf("%d\n", choose(1, 123, 200));
}

Upvotes: 0

6502
6502

Reputation: 114609

y = a ^ ((x - 1U) & (a ^ b));

This uses bitwise x-or

Upvotes: 9

dgnorton
dgnorton

Reputation: 2247

switch (x) {
   case 1:
      y = a;
      break;
   default:
      y = b;
      break;
}

EDIT: the original question said "with jumps" ... not "without"

Upvotes: -1

jcoder
jcoder

Reputation: 30055

Are you saying you don't want a jump in the source code or at the CPU level?

On my compiler 

int choose(int x, int a, int b)
{
    int y;

    if (x)
        y = a;
    else
        y = b;

    return y;
}

compiles to this -

test    ecx, ecx
cmovne  r8d, edx
mov eax, r8d
ret 0

Although I've written a jump at the C code level there isn't one in the generated machine code as the compiler is able to use a conditional move instruction.

Upvotes: 4

Related Questions