# Find the right most set bit of a number

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

Example:

```Number : 1
Binary representation: 1
Position of right most set bit: 1

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

Number : 11
Binary representation: 1 0 1 1
Position of right most set bit: 1

Number : 24
Binary representation:  1 1 0 0 0
Position of right most set bit: 3
```

Approach:

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

`N & ~ (N -1)`
• Let’s dig little deep to see how this expression will work.
• We know that N & ~N = 0
• If we subtract 1 from the number, it will be subtracted from the right most set bit and that bit will be become 0.
• So if we negate the remaining number from step above then that bit will become 1.
• Now N & ~(N-1) will make all the bits 0 but the right most set bit of a number.

Example:

```Say N =10, so N = 1 0 1 0, then ~N = 0 1 1 0 => N & ~ N =0

N – 1 = 1 0 1 0 – 0 0 0 1 = 1 0 0 1

~(N-1) = 0 1 1 0

N & ~(N-1) = 0 0 1 0 => 2nd bit
```

Code:

Output:

```Right most set bit for 1 is : 1
Position: 1.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.
__________________________________________________

#### You may also like...

• lipsa patel

The position for number 24 should be “4” not “3”.