CODEWITHSUNDEEP
c
tok101
tok101

Reputation: 65

How to get corresponding value of a bitmask to an integer efficiently?

Given an integer I and a bitmask M, get the corresponding value of M from I. For example, If I is 0x11111 and M is 0xff0 the corresponding value is 0x11

I can do it by :

  1. Do the & operation between I and M
  2. Calculate how many bits to right shift
  3. Do the right shift

But this way is a little slow, especially step 2. I want a more efficient method for solving this problem.

Upvotes: 3

Views: 214

Answers (1)

Giovanni Cerretani
Giovanni Cerretani

Reputation: 1724

I don't know if there are more efficient ways to do it. I've always done like you. However, consider that usually the computation of how many bits to right shift (your 2nd step) can be done with a single CPU instruction. It has to be done with instinsic instructions, depending on your system.

On Windows, this operation is provided by _BitScanForward(), while on GCC it is provided by __builtin_ctz().

See this answer for more details.

For example, a possible Windows implementation of your problem could be:

#include <Windows.h>

unsigned int maskandshift(unsigned int m, unsigned int i) {
    unsigned int shift;
    // _BitScanForward returns 0 if the mask is zero.
    // You may prefer the actual number of 0, here:
    if (m == 0)
        shift = sizeof(i) * CHAR_BIT;
    else {
        DWORD trailing_zero;
        _BitScanForward(&trailing_zero, (DWORD)m);
        shift = (unsigned int)trailing_zero;
    }
    return (m & i) >> shift;
}

In Release configuration, this function is compiled to a check for zero, followed by just 3 assembly instructions in a x64 machine (BSF, AND and SHR).

Upvotes: 1

Related Questions