Find position of the only set bit

The problem, simply

You get a number n. Write it in bits. If exactly one bit is 1, give back its position, counting from 1 at the rightmost bit. If no bit is 1, or more than one bit is 1, give back -1.

For example 16 is 10000. The 1 is the fifth bit from the right, so the answer is 5.

A story to remember it

Picture it

Examples

Way 1: the simple way

First check that there is exactly one 1. Then slide the number right until the 1 reaches the end, counting the slides.

1. If n is 0, or n & (n - 1) is not 0, give back -1. The test n & (n - 1) wipes out the lowest 1, so it is 0 only when there was one 1.
2. Start at position 1. While the last bit is 0, slide right with >>> and add 1 to the position.

class Solution {
    public static int findPosition(int n) {
        if (n == 0 || (n & (n - 1)) != 0) return -1;   // zero, or more than one 1
        int pos = 1;
        while ((n & 1) == 0) {
            n >>>= 1;          // slide right until the 1 is at the end
            pos++;
        }
        return pos;
    }
}

How long it takes: one slide per bit below the 1, up to 31, O(log n). Extra room: O(1).

Way 2: the clever way

The answer is a bit index from 0 to 31, and that index has 5 bits of its own. Learn each of them with one question, like the lockers.

• 0xAAAAAAAA has 1s at every spot whose index has bit 0 on (spots 1, 3, 5, ...). If n & 0xAAAAAAAA is not 0, bit 0 of the index is 1.
• 0xCCCCCCCC covers spots whose index has bit 1 on (2, 3, 6, 7, ...).
• 0xF0F0F0F0, 0xFF00FF00 and 0xFFFF0000 answer bits 2, 3 and 4.

Add the yes answers together and add 1 to turn the index into a position. The picture below uses 8 bits and 3 stencils, the same idea in a smaller size.

class Solution {
    public static int findPosition(int n) {
        if (n == 0 || (n & (n - 1)) != 0) return -1;   // zero, or more than one 1
        int index = 0;
        if ((n & 0xAAAAAAAA) != 0) index |= 1;   // spots 1, 3, 5, 7, ...
        if ((n & 0xCCCCCCCC) != 0) index |= 2;   // spots 2, 3, 6, 7, ...
        if ((n & 0xF0F0F0F0) != 0) index |= 4;   // spots 4 to 7, 12 to 15, ...
        if ((n & 0xFF00FF00) != 0) index |= 8;   // spots 8 to 15, 24 to 31
        if ((n & 0xFFFF0000) != 0) index |= 16;  // spots 16 to 31
        return index + 1;                        // positions start at 1
    }
}

How long it takes: always 5 checks, O(1). Extra room: O(1). In real code Integer.numberOfTrailingZeros(n) + 1 gives the same answer with one machine instruction.

Watch out for

• Position or index? This problem counts from 1. The drawing and the shift amounts count from 0. Add 1 at the end.
• 1 << 31 is a negative int. If the input can be that number, check n == 0 instead of n <= 0, and slide with >>>. Both ways above handle it and give 32.
• Using Math.log(n) / Math.log(2). Floating point can land on 4.999999 and round down to the wrong answer.

What interviewers ask next

• Find the position of the rightmost 1 in any number? Keep only that bit with n & -n, then use either way above.
• Find the position of the leftmost 1? Spread it down with n |= n >> 1, n |= n >> 2, up to >> 16, then n - (n >>> 1) keeps only the top bit.
• Why do the stencils work? Each stencil asks about one bit of the index. Since only one bit of n is on, each AND is either all 0 or exactly that bit.
• How does numberOfTrailingZeros work without a loop? Modern chips have an instruction for it. Without one, a binary search over halves, quarters and so on takes 5 steps.

Remember this

Grown-up words: the lockers are bit positions, the stencils are bit masks, asking one question per answer bit is a binary search, and the built in shortcut is the count trailing zeros instruction.