# 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: 4

**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 => 2^{nd}bit

**Code**:

**Output**:

Right most set bit for 1 is : 1 Position: 1.0