How to replace modulo operator by using bitwise AND operator?

Modulo operation on a and b returns a reminder from dividing a by b. It can be implemented by using bitwise AND operator if b is a power of two.

Following samples in C and Python illustrate it.

#include <stdio.h>

int main() {
    // 8(dec) = 1000(bin)
    // 7(dec) =  111(bin)
    printf("19 mod 8 (with %%) %d\n", 19 % 8);
    printf("19 mod 8 (with &) %d\n",  19 & 7);

    // 16(dec) = 10000(bin)
    // 15(dec) =  1111(bin)
    printf("16 mod 16 (with %%) %d\n", 16 % 16);
    printf("16 mod 16 (with &) %d\n",  16 & 15);
}

bash-3.2$ llvm-gcc modulo.c && ./a.out
19 mod 8 (with %) 3
19 mod 8 (with &) 3
16 mod 16 (with %) 0
16 mod 16 (with &) 0
bash-3.2$ python
Python 2.6.1 (r261:67515, Feb 11 2010, 00:51:29) 
[GCC 4.2.1 (Apple Inc. build 5646)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 19 % 8
3
>>> 19 & 7
3
>>> 

Why do we need to decrease b?

0 commentaires:

Post a Comment