Software Development

# Position of rightmost set bit

Write a one-line function to return the position of the first 1 from right to left, in the binary representation of an Integer.

Examples:

Input: n = 18
Output: 2
Explanation: Binary Representation of 18 is 010010, hence position of first set bit from right is 2.

Input:  n = 19
Output: 1
Explanation: Binary Representation of 19 is 010011, hence position of first set bit from right is 1.

## Position of rightmost set bit using two’s complement:

(n&~(n-1)) always return the binary number containing the rightmost set bit as 1. if N = 12 (1100) then it will return 4 (100). Here log2 will return, the number of times we can express that number in a power of two. For all binary numbers containing only the rightmost set bit as 1 like 2, 4, 8, 16, 32…. Find that position of rightmost set bit is always equal to log2(Number) + 1.

Follow the steps to solve the given problem:

• Let input be 12 (1100)
• Take two’s complement of the given no as all bits are reverted except the first ‘1’ from right to left (0100)
• Do a bit-wise & with original no, this will return no with the required one only (0100)
• Take the log2 of the no, you will get (position – 1) (2)

Below is the implementation of the above approach:

## C++

 `#include ` `#include ` `using` `namespace` `std;`   `class` `gfg {`   `public``:` `    ``unsigned ``int` `getFirstSetBitPos(``int` `n)` `    ``{` `        ``return` `log2(n & -n) + 1;` `    ``}` `};`   `int` `main()` `{` `    ``gfg g;` `    ``int` `n = 18;` `    ``cout << g.getFirstSetBitPos(n);` `    ``return` `0;` `}`

## C

 `#include ` `#include `   `int` `main()` `{` `    ``int` `n = 18;` `    ``int` `ans = log2(n & -n) + 1;` `    ``printf``(``"%d"``, ans);` `    ``getchar``();` `    ``return` `0;` `}`

## Java

 `import` `java.io.*;`   `class` `GFG {`   `    ``public` `static` `int` `getFirstSetBitPos(``int` `n)` `    ``{` `        ``return` `(``int``)((Math.log10(n & -n)) / Math.log10(``2``))` `            ``+ ``1``;` `    ``}`   `    ` `    ``public` `static` `void` `main(String[] args)` `    ``{` `        ``int` `n = ``18``;` `        ``System.out.println(getFirstSetBitPos(n));` `    ``}` `}`

## Python3

 `import` `math`     `def` `getFirstSetBitPos(n):`   `    ``return` `math.log2(n & ``-``n)``+``1`       `n ``=` `18` `print``(``int``(getFirstSetBitPos(n)))`

## C#

 `using` `System;`   `class` `GFG {` `    ``public` `static` `int` `getFirstSetBitPos(``int` `n)` `    ``{` `        ``return` `(``int``)((Math.Log10(n & -n)) / Math.Log10(2))` `            ``+ 1;` `    ``}`   `    ` `    ``public` `static` `void` `Main()` `    ``{` `        ``int` `n = 18;` `        ``Console.WriteLine(getFirstSetBitPos(n));` `    ``}` `}`

## PHP

 ``

## Javascript

 ``

Time Complexity: O(log2N), Time taken by log2 function.
Auxiliary Space: O(1)

## Position of rightmost set bit using ffs() function:

ffs() function returns the index of first least significant set bit. The indexing starts in ffs() function from 1.
Illustration:

Input: N = 12

Binary Representation of 12 is 1100

ffs(N) returns the rightmost set bit index which is 3

Below is the implementation of the above approach:

## C++

 `#include ` `using` `namespace` `std;`   `int` `getFirstSetBitPos(``int` `n) { ``return` `ffs(n); }`   `int` `main()` `{` `    ``int` `n = 18;` `    ``cout << getFirstSetBitPos(n) << endl;` `    ``return` `0;` `}`

## Java

 `import` `java.util.*;`   `class` `GFG {`   `    ` `    ` `    ``static` `int` `getFirstSetBitPos(``int` `n)` `    ``{` `        ``return` `(``int``)((Math.log10(n & -n)) / Math.log10(``2``))` `            ``+ ``1``;` `    ``}`   `    ` `    ``public` `static` `void` `main(String[] args)` `    ``{` `        ``int` `n = ``18``;` `        ``System.out.print(getFirstSetBitPos(n));` `    ``}` `}`

## Python3

 `import` `math`       `def` `getFirstSetBitPos(n):`   `    ``return` `int``(math.log2(n & ``-``n) ``+` `1``)`     `if` `__name__ ``=``=` `'__main__'``:`   `    ``n ``=` `18` `    ``print``(getFirstSetBitPos(n))`

## C#

 `using` `System;` `public` `class` `GFG {`   `    ` `    ` `    ``static` `int` `getFirstSetBitPos(``int` `n)` `    ``{` `        ``return` `(``int``)((Math.Log10(n & -n)) / Math.Log10(2))` `            ``+ 1;` `    ``}`   `    ` `    ``public` `static` `void` `Main(String[] args)` `    ``{` `        ``int` `n = 18;` `        ``Console.Write(getFirstSetBitPos(n));` `    ``}` `}`

## Javascript

 ``

Time Complexity: O(log2N), Time taken by ffs() function.
Auxiliary Space: O(1)

## Position of rightmost set bit using  & operator:

Follow the steps below to solve the problem:

• Initialize m as 1 as check its XOR with the bits starting from the rightmost bit.
• Left shift m by one till we find the first set bit
• as the first set bit gives a number when we perform a & operation with m.

Below is the implementation of above approach:

## C++

 `#include ` `using` `namespace` `std;`   `int` `PositionRightmostSetbit(``int` `n)` `{` `    ``if` `(n == 0)` `        ``return` `0;` `    ` `    ` `    ``int` `position = 1;` `    ``int` `m = 1;`   `    ``while` `(!(n & m)) {`   `        ` `        ``m = m << 1;` `        ``position++;` `    ``}` `    ``return` `position;` `}` `int` `main()` `{` `    ``int` `n = 18;` `    ` `    ``cout << PositionRightmostSetbit(n);` `    ``return` `0;` `}`

## Java

 `class` `GFG {`   `    ` `    ` `    ``static` `int` `PositionRightmostSetbit(``int` `n)` `    ``{` `        ` `        ` `        ` `        ``int` `position = ``1``;` `        ``int` `m = ``1``;`   `        ``while` `((n & m) == ``0``) {`   `            ` `            ``m = m << ``1``;` `            ``position++;` `        ``}` `        ``return` `position;` `    ``}`   `    ` `    ``public` `static` `void` `main(String[] args)` `    ``{` `        ``int` `n = ``18``;`   `        ` `        ``System.out.println(PositionRightmostSetbit(n));` `    ``}` `}`

## Python3

 `def` `PositionRightmostSetbit(n):`   `    ` `    ` `    ` `    ``position ``=` `1` `    ``m ``=` `1`   `    ``while` `(``not``(n & m)):`   `        ` `        ``m ``=` `m << ``1` `        ``position ``+``=` `1`   `    ``return` `position`     `n ``=` `18`   `print``(PositionRightmostSetbit(n))`

## C#

 `using` `System;`   `class` `GFG {`   `    ` `    ` `    ``static` `int` `PositionRightmostSetbit(``int` `n)` `    ``{` `        ` `        ` `        ` `        ``int` `position = 1;` `        ``int` `m = 1;`   `        ``while` `((n & m) == 0) {`   `            ` `            ``m = m << 1;` `            ``position++;` `        ``}` `        ``return` `position;` `    ``}`   `    ` `    ``static` `public` `void` `Main()` `    ``{` `        ``int` `n = 18;`   `        ` `        ``Console.WriteLine(PositionRightmostSetbit(n));` `    ``}` `}`

## PHP

 ``

## Javascript

 ``

Time Complexity: O(log2N), Traversing through all the bits of N, where at max there are logN bits.
Auxiliary Space: O(1)

## Position of rightmost set bit using Left Shift(<<):

Follow the steps below to solve the problem:

• Initialize pos with 1
• iterate up to INT_SIZE(Here 32)
• check whether bit is set or not
• if bit is set then break the loop
• else increment the pos.

Below is the implementation of the above approach:

## C++

 `#include ` `using` `namespace` `std;` `#define INT_SIZE 32`   `int` `Right_most_setbit(``int` `num)` `{` `    ``if` `(num == 0) ` `    ``{` `        ``return` `0;` `    ``}` `    ``else` `{` `        ``int` `pos = 1;` `        ` `        ``for` `(``int` `i = 0; i < INT_SIZE; i++) {` `            ``if` `(!(num & (1 << i)))` `                ``pos++;` `            ``else` `                ``break``;` `        ``}` `        ``return` `pos;` `    ``}` `}` `int` `main()` `{` `    ``int` `num = 18;` `    ``int` `pos = Right_most_setbit(num);` `    ``cout << pos << endl;` `    ``return` `0;` `}`

## Java

 `public` `class` `GFG {`   `    ``static` `int` `INT_SIZE = ``32``;`   `    ``static` `int` `Right_most_setbit(``int` `num)` `    ``{` `        ``int` `pos = ``1``;` `        ` `        ``for` `(``int` `i = ``0``; i < INT_SIZE; i++) {` `            ``if` `((num & (``1` `<< i)) == ``0``)` `                ``pos++;`   `            ``else` `                ``break``;` `        ``}` `        ``return` `pos;` `    ``}`   `    ` `    ``public` `static` `void` `main(String[] args)` `    ``{`   `        ``int` `num = ``18``;` `        ``int` `pos = Right_most_setbit(num);` `        ``System.out.println(pos);` `    ``}` `}`

## Python3

 `INT_SIZE ``=` `32`     `def` `Right_most_setbit(num):`   `    ``pos ``=` `1`   `    ` `    ``for` `i ``in` `range``(INT_SIZE):` `        ``if` `not``(num & (``1` `<< i)):` `            ``pos ``+``=` `1` `        ``else``:` `            ``break`   `    ``return` `pos`     `if` `__name__ ``=``=` `"__main__"``:`   `    ``num ``=` `18` `    ``pos ``=` `Right_most_setbit(num)` `    ``print``(pos)`

## C#

 `using` `System;`   `class` `GFG {`   `    ``static` `int` `INT_SIZE = 32;`   `    ``static` `int` `Right_most_setbit(``int` `num)` `    ``{` `        ``int` `pos = 1;`   `        ` `        ` `        ``for` `(``int` `i = 0; i < INT_SIZE; i++) {` `            ``if` `((num & (1 << i)) == 0)` `                ``pos++;`   `            ``else` `                ``break``;` `        ``}` `        ``return` `pos;` `    ``}`   `    ` `    ``static` `public` `void` `Main()` `    ``{` `        ``int` `num = 18;` `        ``int` `pos = Right_most_setbit(num);` `        ``Console.WriteLine(pos);` `    ``}` `}`

## PHP

 ``

## Javascript

 ``

Time Complexity: O(log2n), Traversing through all the bits of N, where at max there are logN bits.
Auxiliary Space: O(1)

## Position of rightmost set bit using Right Shift(>>):

Follow the steps below to solve the problem:

• Initialize pos=1.
• Iterate till number>0,  at each step check if the last bit is set.
• If last bit is set, return current position
• else increment pos by 1 and right shift n by 1.

Below is the implementation of the above approach:

## C++

 `#include ` `using` `namespace` `std;`   `int` `PositionRightmostSetbit(``int` `n)` `{` `    ``int` `p = 1;`   `    ` `    ``while` `(n > 0) {`   `        ` `        ``if` `(n & 1) {` `            ``return` `p;` `        ``}`   `        ` `        ``p++;` `        ``n = n >> 1;` `    ``}`   `    ` `    ``return` `-1;` `}`   `int` `main()` `{` `    ``int` `n = 18;`   `    ` `    ``int` `pos = PositionRightmostSetbit(n);`   `    ``if` `(pos != -1)` `        ``cout << pos;` `    ``else` `        ``cout << 0;`   `    ``return` `0;` `}`

## Java

 `import` `java.io.*;`   `class` `GFG {`   `    ` `    ` `    ``public` `static` `int` `Last_set_bit(``int` `n)` `    ``{` `        ``int` `p = ``1``;`   `        ` `        ``while` `(n > ``0``) {`   `            ` `            ``if` `((n & ``1``) > ``0``) {` `                ``return` `p;` `            ``}`   `            ` `            ` `            ``p++;` `            ``n = n >> ``1``;` `        ``}`   `        ` `        ``return` `-``1``;` `    ``}`   `    ` `    ``public` `static` `void` `main(String[] args)` `    ``{` `        ``int` `n = ``18``;`   `        ` `        ``int` `pos = Last_set_bit(n);`   `        ``if` `(pos != -``1``)` `            ``System.out.println(pos);` `        ``else` `            ``System.out.println(``"0"``);` `    ``}` `}`

## Python3

 `def` `PositionRightmostSetbit(n):` `    ``p ``=` `1`   `    ` `    ``while``(n > ``0``):`   `        ` `        ``if``(n & ``1``):` `            ``return` `p`   `        ` `        ``p ``+``=` `1` `        ``n ``=` `n >> ``1`   `    ` `    ``return` `-``1`     `n ``=` `18` `pos ``=` `PositionRightmostSetbit(n)` `if``(pos !``=` `-``1``):` `    ``print``(pos)` `else``:` `    ``print``(``0``)`

## C#

 `using` `System;`   `class` `GFG {`   `    ` `    ` `    ``public` `static` `int` `Last_set_bit(``int` `n)` `    ``{` `        ``int` `p = 1;`   `        ` `        ``while` `(n > 0) {`   `            ` `            ``if` `((n & 1) > 0) {` `                ``return` `p;` `            ``}`   `            ` `            ` `            ``p++;` `            ``n = n >> 1;` `        ``}`   `        ` `        ``return` `-1;` `    ``}`   `    ` `    ``public` `static` `void` `Main(``string``[] args)` `    ``{` `        ``int` `n = 18;`   `        ` `        ``int` `pos = Last_set_bit(n);`   `        ``if` `(pos != -1)` `            ``Console.WriteLine(pos);` `        ``else` `            ``Console.WriteLine(``"0"``);` `    ``}` `}`

## Javascript

 ``

## C

 `#include `   `int` `Last_set_bit(``int` `n)` `{` `    ``int` `p = 1;`   `    ` `    ``while` `(n > 0) {`   `        ` `        ``if` `((n & 1) > 0) {` `            ``return` `p;` `        ``}`   `        ` `        ` `        ``p++;` `        ``n = n >> 1;` `    ``}`   `    ` `    ``return` `-1;` `}`   `int` `main(``void``)` `{` `    ``int` `n = 18;`   `    ` `    ``int` `pos = Last_set_bit(n);`   `    ``if` `(pos != -1)` `        ``printf``(``"%d\n"``, pos);` `    ``else` `        ``printf``(``"0\n"``);`   `    ``return` `0;` `}`

Time Complexity: O(log2n), Traversing through all the bits of N, where at max there are logN bits.
Auxiliary Space: O(1)

Last Updated :
14 Apr, 2023

Like Article

Save Article