3

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.

Spikatrix
  • 20,225
  • 7
  • 37
  • 83
tok101
  • 65
  • 4
  • 2
    There's no better way to do this. You must always know how many bits to shift to the right. Though if you're talking about code size, this operation can certainly be done using only one statement. – bool3max Sep 21 '18 at 09:51
  • How slow is a little slow? How slow is fast enough? What is the variability of your bitmasks - are there a fixed number you can pre-compute the right-shift distance for? Or are your bitmasks generated on the fly somewhere, and could that place generate the right-shift distance at the same time? – Useless Sep 21 '18 at 13:59

1 Answers1

1

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).

Giovanni Cerretani
  • 1,693
  • 1
  • 16
  • 30