Algorithm Bit Algorithms: C Programming Coding

C Programming – Compute modulus division by a power of 2 number

Compute modulus division by a power of 2 number - Bit Algorithm - operators, where d is a power of 2 number.Let it bit from right is set in d. For getting n

Compute n modulo d without division(/) and modulo(%) operators, where d is a power of 2 number.

Let ith bit from right is set in d. For getting n modulus d, we just need to return 0 to i-1 (from right) bits of n as they are and other bits as 0.

For example if n = 6 (00..110) and d = 4(00..100). Last set bit in d is at position 3 (from right side). So we need to return last two bits of n as they are and other bits as 0, i.e., 00..010.

Now doing it is so easy, guess it….

Yes, you have guessing it right. See the below program.

C Program
#include<stdio.h>
 
/* This function will return n % d.
   d must be one of: 1, 2, 4, 8, 16, 32, … */
unsigned int getModulo(unsigned int n, unsigned int d)
{
  return ( n & (d-1) );
}         
 
/* Driver program to test above function */
int main()
{
  unsigned int n = 6;
  unsigned int d = 4; /*d must be a power of 2*/
  printf("%u moduo %u is %u", n, d, getModulo(n, d));
 
  getchar();
  return 0;
} 
See also  C Programming - Matrix Chain Multiplication

About the author

Venkatesan Prabu

Wikitechy Founder, Author, International Speaker, and Job Consultant. My role as the CEO of Wikitechy, I help businesses build their next generation digital platforms and help with their product innovation and growth strategy. I'm a frequent speaker at tech conferences and events.

Add Comment

Click here to post a comment