Есть ли способ ограничить целочисленное значение определенным диапазоном без разветвления?

Ответ 1

Есть бит-трюки, чтобы найти минимум или максимум двух чисел, поэтому вы можете использовать их для поиска min(max(x, 0), some_maximum). Из здесь:

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

По мере того как источник утверждает, что, вероятно, быстрее сделать это обычным способом, несмотря на ветвь

Ответ 2

Это будет зависимым от компилятора и процессора, но если вы используете ?:, его можно перевести на условный переход (по крайней мере, на процессоры на базе Intel), который не использует ветку.

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

Это может использовать инструкцию CMOV (см. http://www.intel.com/software/products/documentation/vlin/mergedprojects/analyzer_ec/mergedprojects/reference_olh/mergedProjects/instructions/instruct32_hh/vc35.htm), целью которой является избежать ветвления (и, таким образом,).

Изменить: этот поток может вас заинтересовать. Тесты показывают, что условные ходы будут давать вам прирост скорости только на ветвях, которые не очень предсказуемы, тогда как высоко прогнозируемые ветки (например, длинные петли) предпочитают стандартный подход.

Ответ 3

Используя тернарный оператор:)

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

Ответ 4

Зависит от вашей архитектуры. По крайней мере, для ARM компилятор, вероятно, испустил бы условно исполняемые инструкции, и полученный машинный код не содержал бы ветку. Я не могу придумать хороший способ сделать это явным в программе C. Однако.

Ответ 5

Если возможно ограничить степени 2 (не включительно), то просто переходим к

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

не совсем уверенно обрабатывать (если x < 0 case) или общий (x < n case)

Ответ 6

Для будущих проблем, подобных этому, может быть полезно использовать страницу бит-хака: http://graphics.stanford.edu/~seander/bithacks.html.

Поскольку битак для min и max уже был отправлен, здесь другой:

// 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;

Я только что попробовал, и это сработало для нескольких тестовых случаев, которые у меня были.

Вот код сборки с моего компьютера (intel arch), который не показывает никаких ветвей.

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              

Ответ 7

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

Разветвление хорошо скрывается внутри функций с обычными именами.

Предлагаем создать шаблон clip_by.

Ответ 8

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