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?

12 comments:


  1. I like your blog, I read this blog please update more content on python, further check it once at python online course

    ReplyDelete
  2. If any student needs help with their corporate finance assignment then visit the Best Assignment Experts for getting affordable and quality assignment help. Corporate Finance Assignment Writing

    ReplyDelete
  3. You have a lot of interesting content on your blog. No doubt I'm having fun here, and it looks like there are others! Good job, keep it up. For more information about Increase your clicking, please refer to the article click counter. Thank you so much for taking the time to read this.

    ReplyDelete
  4. Thanks for sharing this blog! it’s good to read. It's a nice place to visit. A QWERTY keyboard is a popular keyboard layout. By Referring to the qwerty keyboard profile you can easily find your keyboard key problem.

    ReplyDelete
  5. Explore premier hosting solutions at our cutting-edge data center in Cyprus! Enjoy unparalleled reliability and security for your online operations.

    ReplyDelete