Compute modulus division by a power-of-2-number

In this blog post, I will teach you how to write C/C++ program to compute modulus division by a power-of-2-number without using the % (modulus operator). After reading this post you able to write an efficient program to compute modulus division by a power-of-2-number.

Let’s first understand the what the meaning of modulus it helps you to understand the code. Basically, modulus is the remainder of the euclidean division of one number by another. In C/C++ programming language % is called the modulo operator.

For example, 23 divided by 6 equals 3 but it remains 5. Here, 23 / 6 = 3 and 23 % 6 = 5.

Consider the below mentioned examples for more better understanding.

Input: 7 , 4
Output: 3
Explanation: As 7%4 = 3



Input: 27 2
Output: 1
Explanation: As 27%2 = 1



Input: 6 16
Output: 6
Explanation:As 6%16 = 6

Let’s see the problem statements for this question.

Problem Statement: Given two numbers “n” (dividend) and “d” (devisor), where d = 1U << s; (So d will be one of: 1, 2, 4, 8, 16, 32, …). Compute “n” modulo “d” without division (/) and modulo (%) operators, where “d” is a power of 2 number.

Disclaimer: Try to solve the problem yourself first otherwise it would be not worth solving this problem.

Using Bitwise AND with (d – 1):

The concept of (d-1) creates a binary number with all its bits set to 1, where d must be power of 2.

For an example d = 16,

Input : d = 16

Here's a simple ASCII representation of 8 (an 8-bit integer):

  7   6   5   4   3   2   1   0    (Bit position)
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |  (Example bit values)
+---+---+---+---+---+---+---+---+

Now, (d - 1) equals 15,

Input : d = 15

Here's a simple ASCII representation of 8 (an 8-bit integer):

  7   6   5   4   3   2   1   0    (Bit position)
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |  (Example bit values)
+---+---+---+---+---+---+---+---+

So, for getting n modulus d, you just need to return n & (d-1)

C program to compute modulus division by a power-of-2-number:

/*
C program to get position
of only set Bit:
*/
#include <stdio.h>
#include<stdint.h>


//C Function to check if num is power of 2
uint32_t isPowerOfTwo(uint32_t num)
{
    /* Zero and negative numbers
        are not powers of two*/
    uint32_t ret = (num > 0)?
                   ((num != 0)&&((num & (num-1)) == 0)):0;
    return ret ;
}

// This function will return n % d.
// d must be one of: 1, 2, 4, 8, 16, 32, …
int64_t getModulo(uint32_t n,
                  uint32_t d)
{
    int64_t ret = -1;

    //check divisor
    if(isPowerOfTwo(d))
    {
        ret = (n&(d - 1));
    }

    return ret;
}


int main()
{
    uint32_t n = 27;
    uint32_t d = 8;

    const int64_t modulos = getModulo(n,d);
    if(modulos >= 0)
    {
        printf("%u modulo %u is %u\n", n, d, (uint32_t)modulos);
    }
    else
    {
        printf("Invalid divisor\n");
    }

    return 0;
}

Output:

27 modulo 8 is 3

C++ program to compute modulus division by a power-of-2-number:

/*
C++ program to get position
of only set Bit:
*/
#include <iostream>
#include<stdint.h>


//C++ Function to check if num is power of 2
bool isPowerOfTwo(uint32_t num)
{
    /* Zero and negative numbers
        are not powers of two*/
    const bool ret = (num > 0)?
                     ((num != 0)&&((num & (num-1)) == 0)):false;
    return ret ;
}

// This function will return n % d.
// d must be one of: 1, 2, 4, 8, 16, 32, …
int64_t getModulo(uint32_t n,
                  uint32_t d)
{
    int64_t ret = -1;

    //check divisor
    if(isPowerOfTwo(d))
    {
        ret = static_cast<int64_t>(n&(d - 1));
    }

    return ret;
}


int main()
{
    uint32_t n = 27;
    uint32_t d = 8;

    const int64_t modulos = getModulo(n,d);
    if(modulos >= 0)
    {
        std::cout<< n << " modulo " << d << " is ";
        std::cout<<static_cast<uint32_t>(modulos)<<std::endl;
    }
    else
    {
        std::cout<<"Invalid divisor"<<std::endl;
    }

    return 0;
}

Output:

27 modulo 8 is 3

Using Bitwise AND with (d – 1):

C program to compute modulus division by a power-of-2-number:

C++ program to compute modulus division by a power-of-2-number:

Recommended Post