Bit manipulation -- generate mask for first N set bits

Joseph_Garvin_50385 0
Viewed 275

I'm wondering if there is an efficient algorithm implementation for the following problem:

Given an unsigned integer U, make a mask that selects the first N bits of U that are set. (Going from right to left, low order to high order)

So for example:

f(U=1111, N=2) -> 0011
f(U=1010, N=2) -> 1010
f(U=1110, N=2) -> 0110
f(U=0111, N=2) -> 0011
f(U=0011, N=2) -> 0011

Most processors have a "find first set bit" or similar instruction, so I figure in the worst case I can invoke that N times, but is it possible to do better?

mask bitwise-operators bit-manipulation c algorithm
3 Answers

Some recent CPUs have the pdep instruction with which this is easy:

m = bitmask of n ones
return pdep(m, x)

Otherwise a stepwise approach as in @olegarch's solution is probably unavoidable. One with slightly fewer instructions is as follows:

unsigned getmask(unsigned x, int n) {
    unsigned x1 = -x;
    for (int i = 0; i < n - 1; ++i)
        x1 = x1 - (x ^ x1);
    return x & x1;
}
user_3783600

Guess the bit and use built-in popcount to test the guess. If we consider built-in popcount as O(1), then the complexity would be O(log N) (with binary search).

user_20347870 
int getmask(unsigned int U, int n) {
      unsigned int m = U;
      do {
        m &= m - 1;
      } while(m && --n);
      return U & ~m; 
}
user_3399370
Related