# Find the right most unset bit OR zero bit of a number

Objective: Given a number, write and algorithm to find the right most unset bit or zero bit in it (In binary representation).

This problem is similar to: Find the right most set bit of a number

Example:

```Number : 11
Binary representation: 1 0 1 1
Position of right most unset bit: 2

Number : 6
Binary representation: 1 1 0
Position of right most unset bit: 0

Number : 13
Binary representation: 1 1 0 1
Position of right most unset bit: 1
```

Approach:

If N is a number then the expression below will give the right most unset bit.

`~N &  (N +1)`
• Let’s dig little deep to see how this expression will work.
• We know that N & ~N = 0
• If we add 1 from the number, it will make most unset bit to 1, if there are any set bits in the right side of unset bit, those bit will become zero.
• (example : 1 0 1 1 + 0 0 0 1 = 1 1 0 0)
• So if we negate the original number it will make the right most unset bit to 1.
• Now ~N & (N+1) will make all the bits 0 but the right most unset bit of a number.

Example:

```Say N =11, so N = 1 0 1 1
N + 1 = 1 1 0 0
~N = 0 1 0 1
~N & (N+1) = 0 1 0 0 => 2nd bit (assuming right most index is 0)
```

Code:

Output:

```Right most Unset bit :2.0
```

__________________________________________________
Top Companies Interview Questions..-

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}