How can I use bit shifting to replace integer division?

Question

I understand how to do it for powers of 2 so that's not my question.

For example, if I want to find 5% of a number using a bit shift instead of an integer divide, how would i calculate that?

So instead of (x * 20 / 19), I could do (x * 100 >> 11). Now this isn't right but it's close and I arrived at it using trial and error. How would I determine the most possible precise shift to use?

Answer 1

Best approach is to let the compiler do it for you. You simply write

a/b

in your language of choice, and the compiler generates the bit twiddling.

EDIT (I hope you don't mind, i'm adding reinforcement to your answer:

#include <stdio.h>

int main(int argc, char **argv) {
  printf("%d\n", argc/4);
}

Obviously, the fastest thing to do is argc>>2. Lets see what happens:

        .file   "so3.c"
        .section        .rodata
.LC0:
        .string "%d\n"
        .text
.globl main
        .type   main, @function
main:
        pushl   %ebp
        movl    %esp, %ebp
        andl    $-16, %esp
        subl    $16, %esp
        movl    8(%ebp), %eax
        movl    %eax, %edx
        sarl    $31, %edx
        shrl    $30, %edx
        leal    (%edx,%eax), %eax
        sarl    $2, %eax
        movl    %eax, %edx
        movl    $.LC0, %eax
        movl    %edx, 4(%esp)
        movl    %eax, (%esp)
        call    printf
        leave
        ret
        .size   main, .-main
        .ident  "GCC: (Ubuntu 4.4.3-4ubuntu5) 4.4.3"
        .section        .note.GNU-stack,"",@progbits

yup, there it is, sarl $2, %eax

EDIT 2 (Sorry to pile on, but 20/19 is a bit more complicated…)

I just substituted argc*20/19 for argc/4 and this is the math that comes out:

0000000100000f07        shll    $0x02,%edi
0000000100000f0a        movl    $0x6bca1af3,%edx
0000000100000f0f        movl    %edi,%eax
0000000100000f11        imull   %edx
0000000100000f13        sarl    $0x03,%edx
0000000100000f16        sarl    $0x1f,%edi
0000000100000f19        subl    %edi,%edx

So, the process is

• Multiply input by 4 (shll)
• Load (movl 0x...) and multiply by (imull) a fixed-point fraction obtaining a 64-bit result (this is 32-bit code)
• Divide high-order 32 bits of result by 8 (sarl), note how this handles negative numbers
• Divide low-order 32 bits of result by INT_MAX (sarl) to obtain either 0 or -1
• Correctly round the high-order result by adding 1 (subtracting -1) if necessary.