Is there a way to limit an integer value to a certain range without branching?

Question

Just out of curiosity. If I have something like:

if(x < 0)
    x = 0;
if(x > some_maximum)
    x = some_maximum;

return x;

Is there a way to not branch? This is c++.

Addendum: I mean no branch instructions in the assembly. It's a MIPS architecture.

Answer 1

Depends on your architecture. For ARM, at least, the compiler would probably emit conditionally executed instructions and the resulting machine code wouldn't contain a branch. I can't think of a good way to make that explicit in the C program though.

Answer 2

Using the ternary operator :)

return x < 0 ? 0 : x > some_maximum ? : some_maximum : x;

Answer 3

x = min(max(x,0),100);

The branching is hidden away nicely inside functions with normal names.

Suggesting to create a clip_by template.

Answer 4

This is going to be compiler- and processor-dependent, but if you use ?: it can be translated to a conditional move (at least on Intel-based processors) which does not use a branch.

x = x < 0 ? 0 : x; x = x > max ? max : x;

This can use the CMOV instruction (see http://www.intel.com/software/products/documentation/vlin/mergedprojects/analyzer_ec/mergedprojects/reference_olh/mergedProjects/instructions/instruct32_hh/vc35.htm), whose purpose is to avoid branching (and thus branch prediction penalties).

Edit: this thread may be of interest to you. Benchmarks show that conditional moves will give you speed gains only on branches that are not very predictable, whereas highly predictable branches (such as that of a long-running loop) prefer the standard approach.

Answer 5

x =   ((int)(x > some_maximum)) * some_maximum 
    + ((int)(x > 0 && x <= some_maximum)) * x;

Answer 6

There are bit-tricks to find the minimum or maximum of two numbers, so you could use those to find min(max(x, 0), some_maximum). From here:

y ^ ((x ^ y) & -(x < y)); // min(x, y)
x ^ ((x ^ y) & -(x < y)); // max(x, y)

As the source states though, it's probably faster to do it the normal way, despite the branch

Answer 7

If it's possible to limit to powers of 2 (non inclusive), then just go with

int newx = x & ((highest power of 2) - 1)

not quite sure to handle the (if x < 0 case) or the generic (x < n case)

Answer 8

For future problems like this, the bit hack page might be useful: http://graphics.stanford.edu/~seander/bithacks.html.

Since the bithack for min and max was already posted, here is a different one:

// CHAR_BIT is number of bits per byte.
// sign = 1 if x < 0, sign = 0 otherwise (according to the page above)
int sign = (int)((unsigned int)((int)x) >> (sizeof(int) * CHAR_BIT - 1));

int y = (1-sign)*x; // if x < 0, then y = 0, else y = x.

// Depending on arch, the below _might_ cause a branch.
// (on x64 it does not cause a branch, not sure about MIPS)

int z = !(y/some_maximum); // if 0 <= y < some_maximum, z = 1, else z = 0

int ret = z*y + (1-z)*some_maximum; // if z =1, then ret = y; else ret = some_maximum.

return ret;

I just tried it out, and it worked for the few test cases i had.

Here is the assembly code from my computer (intel arch) which shows no branches.

int cap(int x)
{
00F013A0  push        ebp  
00F013A1  mov         ebp,esp 
00F013A3  sub         esp,0FCh 
00F013A9  push        ebx  
00F013AA  push        esi  
00F013AB  push        edi  
00F013AC  lea         edi,[ebp-0FCh] 
00F013B2  mov         ecx,3Fh 
00F013B7  mov         eax,0CCCCCCCCh 
00F013BC  rep stos    dword ptr es:[edi] 

    int some_maximum = 100;

00F013BE  mov         dword ptr [some_maximum],64h 

    // CHAR_BIT is number of bits per byte. 
    // sign = 1 if x < 0, sign = 0 otherwise (according to the page above) 
    int sign = (int)((unsigned int)((int)x) >> (sizeof(int) * CHAR_BIT - 1)); 

00F013C5  mov         eax,dword ptr [x] 
00F013C8  shr         eax,1Fh 
00F013CB  mov         dword ptr [sign],eax 

    int y = (1-sign)*x; // if x < 0, then y = 0, else y = x. 

00F013CE  mov         eax,1 
00F013D3  sub         eax,dword ptr [sign] 
00F013D6  imul        eax,dword ptr [x] 
00F013DA  mov         dword ptr [y],eax 

    // Depending on arch, the below _might_ cause a branch. 
    // (on x64 it does not cause a branch, not sure about MIPS) 

    int z = !(y/some_maximum); // if 0 <= y < some_maximum, z = 1, else z = 0 

00F013DD  mov         eax,dword ptr [y] 
00F013E0  cdq              
00F013E1  idiv        eax,dword ptr [some_maximum] 
00F013E4  neg         eax  
00F013E6  sbb         eax,eax 
00F013E8  add         eax,1 
00F013EB  mov         dword ptr [z],eax 

    int ret = z*y + (1-z)*some_maximum; // if z =1, then ret = y; else ret = some_maximum. 

00F013EE  mov         eax,dword ptr [z] 
00F013F1  imul        eax,dword ptr [y] 
00F013F5  mov         ecx,1 
00F013FA  sub         ecx,dword ptr [z] 
00F013FD  imul        ecx,dword ptr [some_maximum] 
00F01401  add         eax,ecx 
00F01403  mov         dword ptr [ret],eax 

    return ret; 

00F01406  mov         eax,dword ptr [ret] 
}
00F01409  pop         edi  
00F0140A  pop         esi  
00F0140B  pop         ebx  
00F0140C  mov         esp,ebp 
00F0140E  pop         ebp  
00F0140F  ret