当前位置： 文江博客话题详情

有没有办法将整数值限制在一定范围内而不分支？

发布于 2024-09-02 01:09:15 字数 195 浏览 9 评论 0原文

只是出于好奇。如果我有类似的问题：

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

return x;

有没有办法不分支？这是c++。

附录：我的意思是程序集中没有分支指令。这是一个MIPS 架构。

原文

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.

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（9）

谁许谁一生繁华 2024-09-09 01:09:15

有一些位技巧可以查找两个数字的最小值或最大值，因此您可以使用它们来查找 min(max(x, 0), some_maximum)。来自此处：

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

正如消息来源所述，这样做可能会更快正常方式，尽管有分支

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

回复 原文
暖阳 2024-09-09 01:09:15

这将取决于编译器和处理器，但如果您使用 ?: 它可以转换为不使用分支的条件移动（至少在基于 Intel 的处理器上）。

<代码>x = x < 0 ? 0：x；
x＝x＞最大限度 ？ max : x;

这可以使用 CMOV 指令（请参阅http://www.intel.com/software/products/documentation/vlin/mergedprojects/analyzer_ec/mergedprojects/reference_olh/mergedProjects/instructions /instruct32_hh/vc35.htm），其目的是避免分支（从而避免分支预测惩罚）。

编辑：此帖子 您可能感兴趣。基准测试表明，条件移动只会在不太可预测的分支上为您带来速度增益，而高度可预测的分支（例如长时间运行的循环）更喜欢标准方法。

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.

回复 原文
怂人 2024-09-09 01:09:15

在 C++17 中，您可以使用 std::clamp

在标头中定义

模板
constexpr const T&钳位( const T& v, const T& lo, const T& hi ); (1)（自 C++17 起）
模板<类T，类比较>
constexpr const T&夹（const T＆amp; v，const T＆amp; lo，const T＆amp; hi，比较comp）; (2) (C++17 起)
  1. 如果 v 比较小于 lo，则返回 lo；否则如果 hi 比较
    小于 v，返回 hi；否则返回 v。使用运算符<到
    比较值。
  2. 与 (1) 相同，但使用 comp 来比较值。

In C++17 you can use std::clamp

Defined in header <algorithm>

template<class T>
constexpr const T& clamp( const T& v, const T& lo, const T& hi );   (1)   (since C++17)
template<class T, class Compare>
constexpr const T& clamp( const T& v, const T& lo, const T& hi, Compare comp );    (2)    (since C++17)
  1. If v compares less than lo, returns lo; otherwise if hi compares
    less than v, returns hi; otherwise returns v. Uses operator< to
    compare the values.
  2. Same as (1), but uses comp to compare the values.
回复 原文
夜清冷一曲。 2024-09-09 01:09:15

使用三元运算符:)

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

Using the ternary operator :)

return x < 0 ? 0 : x > some_maximum ? : some_maximum : x;
回复 原文
野生奥特曼 2024-09-09 01:09:15

取决于你的架构。至少对于 ARM，编译器可能会发出条件执行指令，并且生成的机器代码不会包含分支。但我想不出一个好方法来在 C 程序中明确这一点。

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.

回复 原文
空‖城人不在 2024-09-09 01:09:15

对于未来类似的问题，位黑客页面可能有用：http://graphics.stanford .edu/~seander/bithacks.html。

由于 min 和 max 的 bithack 已经发布，这里有一个不同的：

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

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
回复 原文
浅听莫相离 2024-09-09 01:09:15

如果可以限制为 2 的幂（不包括在内），那么只需使用

int newx = x & ((2 的最高次方) - 1)

不太确定处理（如果 x < 0 情况）或通用（x < n 情况）

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)

回复 原文
趁年轻赶紧闹 2024-09-09 01:09:15
x = min(max(x,0),100);

分支很好地隐藏在具有正常名称的函数内。

建议创建一个clip_by模板。

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

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

Suggesting to create a clip_by template.

回复 原文
贪了杯 2024-09-09 01:09:15
x =   ((int)(x > some_maximum)) * some_maximum 
    + ((int)(x > 0 && x <= some_maximum)) * x;

x =   ((int)(x > some_maximum)) * some_maximum 
    + ((int)(x > 0 && x <= some_maximum)) * x;
回复 原文
~没有更多了~

关于作者

沫尐诺

暂无简介

文章
评论
26 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

知足的幸福

文章 0 评论 0

我一向站在原地

文章 0 评论 0

慕烟庭风

文章 0 评论 0

秉忠贞之诚 守退让之实

文章 0 评论 0

小兔几

文章 0 评论 0

mb_3y7WUgWY

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文