CODEWITHSUNDEEP
javadata-structuresbit-manipulationtime-complexity
vikash srivastava
vikash srivastava

Reputation: 413

Best way to check that in a binary representation of number all set bits are followed by unset bits only

Could you please let me know is there any best way to find that in binary representation of this number set bits are followed by unset bits only like - 4 - 100 6 - 110 8 - 1000 12 - 1100

private static boolean setBitFollowedByUnsetBits(int num) {
    String str = Integer.toBinaryString(num);
    int len = str.length();
    int countof1 = str.indexOf('0');
    int lastIndOf0 = str.lastIndexOf('0');
    int countof0 = lastIndOf0 -countof1;
    int lastIndOf1 = str.lastIndexOf('1');

    if((!(lastIndOf1 > countof1) && (lastIndOf1 < lastIndOf0))) {
        return ((num >> countof0+1)==((2 << countof1-1)-1));
    }   
    return false;
}

This is what the logic i have written but i am looking for better solution which is much efficient .

Upvotes: 2

Views: 808

Answers (4)

Ralf Kleberhoff
Ralf Kleberhoff

Reputation: 7290

Elaborating on @Alberto's hint:

You are looking for a bit pattern like 0000 0000 0111 1111 1100 0000 0000 0000 (I assume 32-bit integers):

  • some leading zero-bits (none is also OK)
  • a block of one-bits (at least one)
  • a block of zero-bits (at least one)

Special cases can be all zero-bits (N==0), or a number ending with a one-bit (having no trailing zero-bits). Let's first look at the generic case:

Having a binary number like N=xxxx1000, then N-1 is xxxx0111, replacing all the trailing zero-bits by one-bits, the rightmost one-bit by a zero-bit, and leaving the higher bits unchanged.

ORing N with N-1 like int K = N | (N-1); replaces trailing zero-bits with one-bits:

N   = xxxx1000
N-1 = xxxx0111
      --------
K   = xxxx1111

We want the xxxx part to be something like 0001. Now, let's invert K:

~K  = yyyy0000

where yyyy is the bitwise inverse of xxxx, and should look like 1110. So, once again, we can check for the trailing zero-bits and set them with int L = (~K) | ((~K)-1);. The result sould now be all one-bits if there was only one block of one-bits in the original number.

Now the special cases:

  • If there was no one-bit at all in N, the result will also give all ones. As the one-bits block is missing, the result should be false, needing a special handling.

  • A number consisting of just one block of one-bits will also result in all ones. But as the trailing zero-bits are missing, it should return false, needing a special handling as well, which just has to look at the last bit being zero.

So the code code look like:

private static boolean setBitFollowedByUnsetBits(int num) {
    if (num == 0) return false;
    if ((num & 1) == 1) return false;
    int invK = ~ (num | (num-1));
    int indicator = invK | (invK-1);
    return indicator == 0xffffffff;
}

Upvotes: 1

bcsb1001
bcsb1001

Reputation: 2907

This is how I would do it.

private static boolean setBitFollowedByUnsetBits(int num) {
    int withoutTrailingZeros = num >>> Integer.numberOfTrailingZeros(num);
    return num != 0 && (withoutTrailingZeros & withoutTrailingZeros + 1) == 0;
}

This works because your problem is really to shift out the trailing zeros, which Java has a fast built in function for, then to test if the remaining number has all bits set (up to the most significant bit). You can do this with a bitwise and, as for any number n, n & n + 1 is only 0 if n has all bits set (see below). I assume you don't want 0 to return true because it has no bits set, but you can remove the num != 0 && if this isn't the case.

   111 // 7
& 1000 // 8
= 0000 // 0, so 7 has all bits set

   101 // 5
&  110 // 6
=  100 // 4, so 5 does not have all bits set

Edit: if the number must have some trailing zeros, you can also check for withoutTrailingZeros != num to be true.

Upvotes: 0

Beastmaster
Beastmaster

Reputation: 386

I think that more efficient way is to do bitwise checking instead of string -> integer transformation and operating with strings.

private static boolean check(int value) {
    int h = SIZE - numberOfLeadingZeros(value);
    boolean one = false;
    boolean zero = false;
    for (int i = h - 1; i >= 0; i--) {
        int mask = 1 << i;
        if ((value & mask) == mask) {
            if (!zero) {
                one = true;
            } else {
                return false;
            }
        } else {
            if (one) {
                zero = true;
            } else {
                return false;
            }
        }
    }
    return one && zero;
}

Upvotes: 0

Alberto L. Bonfiglio
Alberto L. Bonfiglio

Reputation: 1835

You could adapt Brian Kernigan's Algorithm https://www.geeksforgeeks.org/count-set-bits-in-an-integer/

a) Initialize count: = 0
b) If integer n is not zero

  1. Do bitwise & with (n-1) and assign the value back to n

    { n: = n&(n-1) }

  2. Increment count by 1

  3. go to step b

c) Else return count

As explained in the link above Subtraction of 1 from a number toggles all the bits (from right to left) till the rightmost set bit(including the rightmost set bit). So if we subtract a number by 1 and do bit-wise & with itself (n & (n-1)), we unset the rightmost set bit. If we do n & (n-1) in a loop and count the no of times loop executes we get the set bit count.

Upvotes: 0

Related Questions