Efficient way to round n/4 upward

Question

I have an integer number n and I need to rounds n/4 upward. For performance reason I need to find out a fast way in C. The division by 4 can be done using a >> 2 shift operation but I don't know about the round. I could use ceil but I am worried about performance.

Answer 1

If your operand is non-negative, how about:

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

Note that any sensible compiler will compile /4 of an unsigned int as >>2 anyway.

I can confirm that by compiling the above with gcc -O3 -S:

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

and noting the output is exactly the same if I substitute >>2 by /4.

Also note that I've used unsigned int as >> is implementation defined for negative signed left operands (i.e. shifting negative values right). If you want a working one that rounds up (strictly up) for signed values:

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

because integer division uses truncation rounding, i.e. rounds up for negative numbers (towards zero) anyway. (That's for C99 onwards; it's implementation defined in C89).

If by round up you meant 'round away from zero' then:

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

Answer 2

This optimizes into 7 instructions including the return on my x86_64 machine with gcc -O3.

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

disassembly:

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    $0x2,%eax
   7:   83 e7 03                and    $0x3,%edi
   a:   0f 95 c2                setne  %dl
   d:   01 d0                   add    %edx,%eax
}
   f:   c3                      retq   

Compared with abligh's equivalent solution:

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    $0x2,%eax
}
   f:   c3                      retq   

Compared with abligh's alternate solution:

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    $0x2,%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    $0x3,%eax
  15:   0f 48 c7                cmovs  %edi,%eax
  18:   c1 f8 02                sar    $0x2,%eax
}
  1b:   c3                      retq   

EDIT: Thought I came up with something faster than the other answer then realized I was comparing two slightly different computations. Our two "rounds strictly up" functions are equal in instruction count, but slightly different. Haven't analyzed disassembly enough to know which is faster.