CODEWITHSUNDEEP
mathbit-manipulation
akg
akg

Reputation: 670

How to find out if first x bits are set in a binary representation of an integer effectively?

In a recent interview, I was asked this question. I gave the solution by running a loop and checking every one of the x bits by right-shifting 1 every time.

Then he asked if I can do this without running a loop. I tried various approaches but could not find a solution. Can here any bit-fiddling expert help me out?

Example - if num = 15 and x = 2 then result should be true because 1st 2 bits are set in 15(01111).

Thanks

Upvotes: 2

Views: 424

Answers (1)

Kedar Mhaswade
Kedar Mhaswade

Reputation: 4695

I think following (Java implementation) should work:

 /** Returns true if the least significant x bits in n are set */
 public static boolean areLSBSet(int n, int x) {
    // validate x, n
    int y = (1<<x) - 1;
    return (n & y) == y;
}

The idea is to quickly find out the number that is 2^x - 1 (this number has all the x least significant bits set) and then taking the bitwise-and with given number n which will give the same number only if exactly that many bits in n are set.

Upvotes: 5

Related Questions