Bit Manipulation Bit basics
106. Set the Lowest Zero Bit
You are given a 32-bit signed integer n. Find the lowest bit of n that is 0, set it to 1, and return
the new number. Every other bit stays as it is.
The bits are numbered from the right, starting at 0, so the lowest bit is the rightmost one. All 32 bits
of n count, as a computer stores them in two's complement. Three cases follow from that:
- The zeros in front of a small number are bits too. For 7, which is
111, the lowest 0 is bit 3, so the answer is1111, which is 15. - The top bit, bit 31, is the sign bit. When it is the only 0, as in 231 − 1, setting it makes the answer negative.
- When all 32 bits are already 1, there is nothing to set, and you return
nunchanged. Only −1 is stored that way.
In Python and JavaScript, n and the answer are ordinary numbers in the same 32-bit range.
Example 1
Input: n = 43
47Explanation: 43 is 101011. Bits 0 and 1 are 1, and bit 2 is the lowest 0. Setting it gives 101111, which is 47.
Example 2
Input: n = 2147483647
-1Explanation: 231 − 1 is 31 ones with a 0 on top. The only 0 is the sign bit, and setting it gives 32 ones, which is −1.
Example 3
Input: n = -1
-1Explanation: −1 is stored as 32 ones. No bit is 0, so n comes back unchanged.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
-231 ≤ n ≤ 231 − 1
Clarifying questions
What you would ask an interviewer before writing any code.