CODEWITHSUNDEEP
javabitwise-operators
sasorihuriko
sasorihuriko

Reputation: 209

get position of leftmost 0 bit of a number

I'm trying to get the leftmost position of number 0 of an integer

    int a = 83

For example, binary of 83 is 1010011 so we have have position of leftmost bit 0 is 6th. I wonder is there a way only using bitwise operator to find the answer?

Upvotes: 0

Views: 1946

Answers (3)

Andreas
Andreas

Reputation: 159086

TL;DR

private static int leftmostZeroBit(int a) {
    int b = Integer.highestOneBit(a);
    return (b == 0 ? -1 : 31 - Integer.numberOfLeadingZeros(a ^ b ^ (b - 1)));
}

private static int leftmostZeroBit(long a) {
    long b = Long.highestOneBit(a);
    return (b == 0 ? -1 : 63 - Long.numberOfLeadingZeros(a ^ b ^ (b - 1)));
}

Explanation

Don't know if this is efficient compared to a simple search loop over the bits, but you can use the following methods to help:
Integer.highestOneBit(int i)
Integer.numberOfLeadingZeros(int i)

They each use bit-manipulation, so they take less than 32 iterations (or 64 iterations if using the Long versions).

Given an example input value of 1101011, we want to invert it to 0010100.

Remember, an int has 32 bits, so there are 25 0-bits to the left of those, so to invert it we need to XOR with the mask 1111111.

That mask can be calculated by calling highestOneBit(), which gives us 1000000, subtracting 1 gives 0111111, and combining them gives the mask.

Once we've done the XOR and gotten 0010100, we calculate 31 - numberOfLeadingZeros() to find the position of the leading 1-bit, which is 4 in this example.

We can then define that we want result to be -1 for invalid input:

  • 000 is invalid, since there are no leftmost 0-bit without a 1-bit
  • 111 is invalid, since there are no 0-bits after 1-bits

That gives us the code at the top of the answer.

Test

public static void main(String[] args) {
    test(0x6B); // example in answer
    test(0x53); // example in question (83)
    test(0x29);
    test(0x14);
    test(0x0A);
    test(0x05);
    test(0x02);
    test(0x01);
    test(0x00);
    test(0x80000000);
    test(0xFFFFFFFE);
}
private static void test(int a) {
    System.out.printf("%32s: %d%n", Integer.toBinaryString(a), leftmostZeroBit(a));
}

Output

                         1101011: 4
                         1010011: 5
                          101001: 4
                           10100: 3
                            1010: 2
                             101: 1
                              10: 0
                               1: -1
                               0: -1
10000000000000000000000000000000: 30
11111111111111111111111111111110: 0

Upvotes: 2

Ted Cassirer
Ted Cassirer

Reputation: 364

You could do something like this:

    int a = 83
    int mask = 1;
    // This loop finds the leftmost 1 bit
    while(a > mask) 
        mask <<= 1;
    mask >>= 1;
    // This loop starts from the leftmost 1 bit and searches for the first 0 going right
    while((a & mask) != 0) 
        mask >>= 1;

    System.out.println(Math.log(mask) / Math.log(2) + 1); // 6

The last "log" part is necessary to give the position index of the leftmost 0 bit

Upvotes: 0

Dibakar Bose
Dibakar Bose

Reputation: 100

As far as I can understand you can use Bitwise operator but alone won't do it. You have to use Conditional Operator to get the output since program has to check the last occurrence of 0 from right to left or first occurrence of 0 from left to right.

Upvotes: -1

Related Questions