向上舍入 n/4 的有效方法

Question

我有一个整数 n，我需要向上舍入 n/4。出于性能原因，我需要在 C 中找到一种快速的方法。除以 4 可以使用 >> 2 移位操作来完成，但我不知道该轮次。我可以使用 ceil 但我担心性能。

Answer 1

如果你的操作数是非负的，怎么样：

unsigned int
roundupdiv4 (unsigned int n)
{
    return (n+3)>>2;
}

请注意，任何明智的编译器都会将 unsigned int 的 /4 编译为 >>2。

我可以通过 gcc -O3 -S:

编译以上内容来确认

    .file   "x.c"
    .text
    .p2align 4,,15
    .globl  roundupdiv4
    .type   roundupdiv4, @function
roundupdiv4:
.LFB0:
    .cfi_startproc
    leal    3(%rdi), %eax
    shrl    , %eax
    ret
    .cfi_endproc
.LFE0:
    .size   roundupdiv4, .-roundupdiv4
    .ident  "GCC: (Ubuntu 4.8.2-19ubuntu1) 4.8.2"
    .section    .note.GNU-stack,"",@progbits

并注意输出 完全相同 如果我用 /4 替换 >>2。

另请注意，我使用了 unsigned int，因为 >> 是为负符号左操作数定义的实现（即向右移动负值）。如果你想要一个工作的（严格向上）有符号值：

int
roundupdiv4 (int n)
{
    return ((n>0)?(n+3):n)/4;
}

因为整数除法使用截断舍入，即无论如何都会对负数（接近零）进行舍入。（那是为了 C99 onwards；它是 C89 中定义的实现）。

如果你的意思是 'round away from zero' 那么：

int
roundawayfromzerodiv4 (int n)
{
    return ((n>0)?(n+3):(n-3))/4;
}

Answer 2

这优化为 7 条指令，包括我 x86_64 机器上的 return 和 gcc -O3。

int div4roundup(int x)
{
   return (x & 3) ? (x >> 2) + 1 : (x>>2);
}

反汇编：

int div4roundup(int x)
{
  return (x & 3) ? (x >> 2) + 1 : (x>>2);
   0:   89 f8                   mov    %edi,%eax
   2:   31 d2                   xor    %edx,%edx
   4:   c1 f8 02                sar    [=11=]x2,%eax
   7:   83 e7 03                and    [=11=]x3,%edi
   a:   0f 95 c2                setne  %dl
   d:   01 d0                   add    %edx,%eax
}
   f:   c3                      retq

与abligh的等效解决方案相比：

int
roundupdiv4 (int n)
{
    return ((n>0)?(n+3):n)/4;
   0:   85 ff                   test   %edi,%edi
   2:   8d 47 03                lea    0x3(%rdi),%eax
   5:   7f 05                   jg     c <fc+0xc>
   7:   85 ff                   test   %edi,%edi
   9:   0f 49 c7                cmovns %edi,%eax
   c:   c1 f8 02                sar    [=12=]x2,%eax
}
   f:   c3                      retq

与 abligh 的替代解决方案相比：

0000000000000000 <roundawayfromzerodiv4>:
int
roundawayfromzerodiv4 (int n)
{
    return ((n>0)?(n+3):(n-3))/4;
   0:   85 ff                   test   %edi,%edi
   2:   7e 0c                   jle    10 <roundawayfromzerodiv4+0x10>
   4:   8d 47 03                lea    0x3(%rdi),%eax
   7:   c1 f8 02                sar    [=13=]x2,%eax
   a:   c3                      retq   
   b:   0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
  10:   89 f8                   mov    %edi,%eax
  12:   83 e8 03                sub    [=13=]x3,%eax
  15:   0f 48 c7                cmovs  %edi,%eax
  18:   c1 f8 02                sar    [=13=]x2,%eax
}
  1b:   c3                      retq

编辑： 以为我想出了比其他答案更快的东西然后意识到我正在比较两个略有不同的计算。我们的两个 "rounds strictly up" 函数在指令数上是相等的，但略有不同。还没有足够的分析反汇编来知道哪个更快。

向上舍入 n/4 的有效方法

Efficient way to round n/4 upward

c

algorithm

math

optimization

rounding