Существует ли способ ограничить целочисленное значение определенным диапазоном без ветвления?
Только из любопытства. Если у меня есть что-то как:
if(x < 0)
x = 0;
if(x > some_maximum)
x = some_maximum;
return x;
Существует ли способ не перейти? Это - C++.
Приложение: Я не имею в виду команд перехода в блоке. Это - архитектура MIPS.
8 ответов
Существуют битовые уловки для нахождения минимума или максимума из двух чисел, поэтому вы можете использовать их для нахождения min (max (x, 0), some_maximum) . Из здесь :
y ^ ((x ^ y) & -(x < y)); // min(x, y)
x ^ ((x ^ y) & -(x < y)); // max(x, y)
Однако, как указано в источнике, вероятно, быстрее сделать это обычным способом, несмотря на ветвь
Для будущих проблем, подобных этой, может быть полезна страница битового взлома: 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
Использование тернарного оператора :)
return x < 0 ? 0 : x > some_maximum ? : some_maximum : x;
Это будет зависеть от компилятора и процессора, но если вы используете ?: , его можно преобразовать в условное перемещение (по крайней мере, на процессорах на базе Intel) который не использует ветку.
х = х <0? 0: х;
х = х> макс? max: x;
Здесь можно использовать инструкцию CMOV (см. http://www.intel.com/software/products/documentation/vlin/mergedprojects/analyzer_ec/mergedprojects/reference_olh/ mergedProjects / instructions / Instruct32_hh / vc35.htm ), цель которого - избежать ветвления (и, следовательно, штрафов за предсказание ветвлений).
Правка : эта ветка может вас заинтересовать. Тесты показывают, что условные перемещения дадут вам прирост скорости только в тех ветвях, которые не очень предсказуемы, тогда как в сильно предсказуемых ветвях (например, в длительном цикле) предпочтение отдается стандартному подходу.
Зависит от вашей архитектуры. По крайней мере, для ARM компилятор, вероятно, будет выдавать условно выполняемые инструкции, и полученный машинный код не будет содержать ветвь. Однако я не могу придумать хороший способ сделать это явным в программе C.
x = min(max(x,0),100);
Ветвление красиво скрыто внутри функций с обычными именами.
Предлагаем создать шаблон clip_by.
x = ((int)(x > some_maximum)) * some_maximum
+ ((int)(x > 0 && x <= some_maximum)) * x;
Если возможно ограничить степенью 2 (не включительно), тогда просто используйте
int newx = x & ((наибольшая степень 2) - 1)
not вполне уверен, что обработает (если x <0 случай) или общий (x